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?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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
jandhbAuthor Commented:
You might be onto something though...maybe I'm not actually passing in intVersion to these functions?? what am I missing?
0
Cloud Class® Course: CompTIA Cloud+

The CompTIA Cloud+ Basic training course will teach you about cloud concepts and models, data storage, networking, and network infrastructure.

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
itsmeandnobodyelseCommented:
>>     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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.