Depending on the implementation of clock(), it can be quite coarse. Try calculating a bigger number (in the 30-40 range).

Solved

Posted on 2004-10-30

I need further help with this.

I have two functions.

1. That computes the fibonacci number with recursion.

2. The other does not use recursion.

Here they are again...

unsigned recursiveFib(unsigned num)

{

if (num <= 2)

{

return 1;

}

else

{

return recursiveFib(num - 2) + recursiveFib(num - 1);

}

}

-------------------------------------

unsigned nonRecFib(unsigned n)

{

//Variables

int previous = -1;

int result = 1;

for (unsigned int i = 0; i <= n; ++i)

{

int const sum = result + previous;

previous = result;

result = sum;

}

return result;

}

-----------------------------------

In main() I have....

int intVersion = 0;

clock_t start = clock();

int answer = recursiveFib(intVersion);

int nonRecAnswer = nonRecFib(intVersion);

long duration = clock() - start;

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

Yet, when I type in say, 15 the answers are 1 and 0 and the clock cycles are always 0. What do I need to change? Please help.

I have two functions.

1. That computes the fibonacci number with recursion.

2. The other does not use recursion.

Here they are again...

unsigned recursiveFib(unsigned num)

{

if (num <= 2)

{

return 1;

}

else

{

return recursiveFib(num - 2) + recursiveFib(num - 1);

}

}

--------------------------

unsigned nonRecFib(unsigned n)

{

//Variables

int previous = -1;

int result = 1;

for (unsigned int i = 0; i <= n; ++i)

{

int const sum = result + previous;

previous = result;

result = sum;

}

return result;

}

--------------------------

In main() I have....

int intVersion = 0;

clock_t start = clock();

int answer = recursiveFib(intVersion);

int nonRecAnswer = nonRecFib(intVersion);

long duration = clock() - start;

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

Yet, when I type in say, 15 the answers are 1 and 0 and the clock cycles are always 0. What do I need to change? Please help.

15 Comments

Depending on the implementation of clock(), it can be quite coarse. Try calculating a bigger number (in the 30-40 range).

I'm reading in that value based upon user input...that is being done in main...

while (!getNumber(intVersion))

{

cout << "Not an integer\n";

}

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

return 0;

}

I have tried bigger numbers also, but the result is the same. What am I doing wrong here?

2. sum has to be defined before the loop and *of course* it is not const.

3. you have to pass intVersion + 1 to the functions

4.you'll get a significant time only for numbers > 25 or higher (depending on your CPU)

Regards, Alex

unsigned recursiveFib(unsigned num)

{

if (num <= 2)

{

return 1;

}

else

{

return recursiveFib(num - 1) + recursiveFib(num - 2);

}

}

// --------------------------

unsigned nonRecFib(unsigned n)

{

//Variables

int previous = -1;

int result = 1;

int sum = 0;

for (unsigned int i = 0; i <= n; ++i)

{

sum = result + previous;

previous = result;

result = sum;

}

return result;

}

//------------------------

//In main() I have....

int main()

{

while (true)

{

int intVersion = 0;

cout << "Enter number ==>";

cin >> intVersion;

if (intVersion == 0) break;

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

int nonRecAnswer = nonRecFib(intVersion+1);

long duration = clock() - start;

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

}

return 0;

}

bool getNumber(int& intVersion)

{

char* pstop;

string s;

cout << "Enter the Fibonacci number to compute: " << endl;

cin >> s;

intVersion = strtol(s.c_str(), &pstop, 10);

// true if good number

return (*pstop == '\0');

}

while (true)

{

int intVersion = 0;

cout << "Enter number ==>";

cin >> intVersion;

if (intVersion == 0) break;

--------------------------

my current main look liike this...

int main()

{

//Variables

int number; //number to read in from user

int intVersion = 0;

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

int nonRecAnswer = nonRecFib(intVersion+1);

long duration = clock() - start;

//Ask the user to enter a number

cout << "Enter a number and I'll tell you if its a palindrome: " << endl;

cin >> number;

cout << "The result of the number entered is: " << palindrome(number) << endl;

//Enter fibonacci number to compute

while (!getNumber(intVersion))

{

cout << "Not an integer\n";

}

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

return 0;

}

--------------------------

I posted also what my getNumber() looks like...should that be changed?

int main()

{

while (true)

{

int intVersion = 0;

cout << "Enter number ==>";

cin >> intVersion;

if (intVersion == 0) break;

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

int nonRecAnswer = nonRecFib(intVersion+1);

long duration = clock() - start;

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

}

return 0;

}

And I type in say, 30 the results are the same for both. Shouldn't the nonRecAnswer be a lot longer??

Now it says, for 30...134629 and it took 120 clock cyles.

Here is all my code if this will help....

--------------------------

Functions.h

#include <iostream>

using namespace std;

//************************

// Function: power

//

// Accepts: n = to the power of, x = base number

//

// Returns: value computed

//

// Description: Exponent calucation working toward anchor

// case.

//

//************************

int power(int x, unsigned n)

{

if (n == 0)

{

//anchor case

return 1;

}

else

{ //inductive case (n > 0)

return x * power(x, n - 1);

}

}

//************************

// Function: digitCounter

//

// Accepts: number

//

// Returns: returns number of digits in number

//

// Description: Calculates the number of digits in a

// number.

//

//************************

unsigned digitCounter(int number)

{

if (number != 0)

{

return digitCounter(number / 10) + 1;

}

else

{

return 0;

}

}

//************************

// Function: palindrome

//

// Accepts: number to check

//

// Returns: returns true if number is a palindrom, false

// if it is not a palindrome

//

// Description: Check whether number is a palindrome.

//

//************************

bool palindrome(int number)

{

int firstDigit, lastDigit;

int numDigits = digitCounter(number);

if (numDigits <= 1)

{

return true;

}

else

{

int dec = power(10, numDigits-1);

firstDigit = number / dec;

lastDigit = number % 10;

if (firstDigit != lastDigit)

{

return false;

}

else

{

int newNumber = number - (firstDigit*dec); //remove first digit

newNumber /= 10; //remove last digit

return palindrome(newNumber);

}

}

}

//************************

// Function: recursiveFib

//

// Accepts: n = the nth term in the sequence

//

// Returns: the value for the fibonnaci number

//

// Description: Recursive definition calculating

// sequence of numbers.

//

//************************

unsigned recursiveFib(unsigned num)

{

if (num <= 2)

{

return 1;

}

else

{

return recursiveFib(num - 2) + recursiveFib(num - 1);

}

}

//************************

// Function: nonRecFib

//

// Accepts: n = the nth term in the sequence

//

// Returns: the value for the fibonnaci number

//

// Description: Non-Recursive definition calculating

// sequence of numbers.

//

//************************

unsigned nonRecFib(unsigned n)

{

//Variables

int previous = -1;

int result = 1;

//sum

int sum = 0;

for (unsigned int i = 0; i <= n; ++i)

{

//sum

sum = result + previous;

previous = result;

result = sum;

}

return result;

}

//************************

// Function: getNumber

//

// Accepts: number to check

//

// Returns: true or false based upn data type

//

// Description: Receives number from user input and

// determines if its a valid integer number.

//

//************************

bool getNumber(int& intVersion)

{

char* pstop;

string s;

cout << "Enter the Fibonacci number to compute: " << endl;

cin >> s;

intVersion = strtol(s.c_str(), &pstop, 10);

// true if good number

return (*pstop == '\0');

}

--------------------------

main

//include files

#include <iostream>

#include <string>

#include <ctime>

#include "Functions.h"

//namespace to use

using namespace std;

//************************

// Function: main

//

// Accepts: nothing

//

// Returns: int, 0 for successful completion of the

// program

//

// Description: Main function of the program.

//

//************************

int main()

{

//Variables

int number; //number to read in from user

int intVersion = 0;

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

int nonRecAnswer = nonRecFib(intVersion+1);

long duration = clock() - start;

//Ask the user to enter a number

cout << "Enter a number and I'll tell you if its a palindrome: " << endl;

cin >> number;

cout << "The result of the number entered is: " << palindrome(number) << endl;

//Enter fibonacci number to compute

while (!getNumber(intVersion))

{

cout << "Not an integer\n";

}

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

return 0;

}

>> clock_t start = clock();

>> int answer = recursiveFib(intVersion+1)

jandhb, with that sequence you are calling recursiveFib with an argument value of 1 and me and others tried a few times to convince you that you need a *user input* *before* you can call the fibonaccii functions. You either may use a simple cin >> intVersion; or - more comfortable - a call of getInput(..) but you can't omit these inputs.

So, the main(function using getInput() is like that:

int main()

{

while (true)

{

int intVersion = 0;

cout << "Enter number ==>";

if (!getInput(intVersion))

break;;

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

int nonRecAnswer = nonRecFib(intVersion+1);

long duration = clock() - start;

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration << " clock cycles to compute this answer." << endl;

cout.flush();

}

return 0;

}

>>`And I type in say, 30 the results are the same for both. Shouldn't the nonRecAnswer be a lot longer??

No, of course not. There is only one time measurement for both and you are outputting the variable duration twice, so *of course* your output is the same. If you want different resuult you have to *change' the variable 'duration' between the outputs.

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

long duration1 = clock() - start; // time for recursive call

int nonRecAnswer = nonRecFib(intVersion+1);

long duration2 = clock() - start - duration1; // time for non-recursive call

...

cout << "It took " << duration1 << " clock cycles to compute this answer." << endl;

...

cout << "It took " << duration2 << " clock cycles to compute this answer." << endl;

Regards, Alex

1. Thank you for your help. I still have a few questions...sorry, just trying to understand here.

2. Here is what I now have for main()

int main()

{

//Variables

int number; //number to read in from user

int intVersion = 0;

//Ask the user to enter a number

cout << "Enter a number and I'll tell you if its a palindrome: " << endl;

cin >> number;

cout << "The result of the number entered is: " << palindrome(number) << endl;

while (true)

{

int intVersion = 0;

cout << "Enter number ==>";

if (!getNumber(intVersion))

break;;

clock_t start = clock();

int answer = recursiveFib(intVersion+1)

int nonRecAnswer = nonRecFib(intVersion+1);

long duration1 = clock() - start; // time for recursive call

long duration2 = clock() - start - duration1; // time for non-recursive call

//Display results for fibonacci number entered

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration1 << " clock cycles to compute this answer." << endl;

cout.flush();

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration2 << " clock cycles to compute this answer." << endl;

cout.flush();

}

return 0;

}

3. When I type in say, 30 the results are...

"The answer for recursive Fibonacci 30 is 134629. It took 120 clock cycles"

"The answer for non-recursive Fibonacci is 134629. It took 0 clock cycles."

I know non should be faster, but shouldn't it be more than 0??Is duration 2 being calculated properly? Just asking because I thought it would take a little longer to compute this and it would not always be 0 for non-recursive.

1. How do I prevent the program from ending when I type in A for the Fibonacci number...It should loop and say, "please enter an integer" until they do.

2. Once it has shown the results for the first fibonacci number it should not endlessly loop and continue to ask them to enter more #'s.

Can you help me to get these back into the code?

if (!getNumber(intVersion))

break;;

to

while (!getNumber(intVersion))

{

cout << "Please enter a number (0 to stop)";

}

if (intVersion == 0)

break;

>> know non should be faster, but shouldn't it be more than 0

Yes, but you made both measurements *after* the calculations ... You have to move the first calculation *between* the calls.

Regards, Alex

In order to do that would I do this...

cout << "The answer for recursive Fibonacci of " << intVersion << " is " << answer << endl;

cout << "It took " << duration1 << " clock cycles to compute this answer." << endl;

cout.flush();

long duration2 = clock() - start - duration1;

//Display results for non-recursive version

cout << "The answer for non-recursive Fibonacci of " << intVersion << " is " << nonRecAnswer << endl;

cout << "It took " << duration2 << " clock cycles to compute this answer." << endl;

cout.flush();

}

Is that what you mean?

- take time 1

- call recursive Fibonnaci

- take time 2

- call non-recursive Fibonacci

- take time 3

- output difference time 2 to time 1

- output difference time 3 to time 2

All code to this, i gave you more than once (i posted full code that was correct regarding time taking), and if you are still not capable to put all these explanations to a running program, i can't help you anymore.

Regards, Alex

By clicking you are agreeing to Experts Exchange's Terms of Use.

The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**12** Experts available now in Live!