Solved

fibonacci sequence

Posted on 2004-10-30
344 Views
Last Modified: 2010-04-01
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.
0
Question by:jandhb
    15 Comments
     
    LVL 12

    Expert Comment

    by:stefan73
    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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 1

    Author Comment

    by:jandhb
    You might be onto something though...maybe I'm not actually passing in intVersion to these functions?? what am I missing?
    0
     
    LVL 39

    Expert Comment

    by:itsmeandnobodyelse
    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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 1

    Author Comment

    by:jandhb
    still having trouble with it.
    0
     
    LVL 39

    Accepted Solution

    by:
    >>     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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 1

    Author Comment

    by:jandhb
    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
     
    LVL 39

    Expert Comment

    by:itsmeandnobodyelse
    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
     
    LVL 1

    Author Comment

    by:jandhb
    >>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
     
    LVL 39

    Expert Comment

    by:itsmeandnobodyelse
    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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

     Java Android Coding Bundle

    Whether you're an Apple user or Android addict, learning to code for the Android platform is an extremely valuable, in-demand skill. It all starts with Java, the language behind the apps and games that make Android the top platform it is today.

    Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
    Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
    The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
    The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

    875 members asked questions and received personalized solutions in the past 7 days.

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

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    12 Experts available now in Live!

    Get 1:1 Help Now