fibonacci sequence

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.
LVL 1
jandhbAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
itsmeandnobodyelseConnect With a Mentor Commented:
>>     int intVersion = 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
0
 
stefan73Commented:
That's because you need to read in intVersion. If it stays 0, there's nothing to compute.

Depending on the implementation of clock(), it can be quite coarse. Try calculating a bigger number (in the 30-40 range).
0
 
jandhbAuthor Commented:
what do you mean by That's because you need to read in intVersion??

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?
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
jandhbAuthor Commented:
You might be onto something though...maybe I'm not actually passing in intVersion to these functions?? what am I missing?
0
 
itsmeandnobodyelseCommented:
1. You 'forgot' to enter the number before calling the functions
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;
}
0
 
jandhbAuthor Commented:
THis is the function being called to determine if they entered an integer...is there where its messing up??

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');
}
0
 
jandhbAuthor Commented:
Alex, I have made the changes you have suggested here, except I need helping this in main..

    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?
0
 
jandhbAuthor Commented:
When I do this in main() just to check if its working...

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.
0
 
jandhbAuthor Commented:
can you help me finish this up guys? please.

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.
//
//******************************************************v
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;
}
0
 
jandhbAuthor Commented:
still having trouble with it.
0
 
jandhbAuthor Commented:
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.  
0
 
jandhbAuthor Commented:
Two other things I noticed Alex that were working...

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?
0
 
itsmeandnobodyelseCommented:
1. Change
   
     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
0
 
jandhbAuthor Commented:
>>You have to move the first calculation *between* the calls.

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?
0
 
itsmeandnobodyelseCommented:
jandbh, all statements were processed sequentially, so if you want to find out how long a call to one of the fibbonacci functions is, you have to take the time before and after the call. You always took the time before (ok) but then you are calling both fibonacci functions *not* taking the time *between*. What you need is:

      - 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
0
All Courses

From novice to tech pro — start learning today.