Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

fibonacci sequence

Posted on 2004-10-30
15
Medium Priority
?
391 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
Comment
Question by:jandhb
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 4
15 Comments
 
LVL 12

Expert Comment

by:stefan73
ID: 12453249
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
ID: 12453276
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
ID: 12453287
You might be onto something though...maybe I'm not actually passing in intVersion to these functions?? what am I missing?
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 12453294
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
ID: 12453295
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
ID: 12453319
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
ID: 12453341
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
ID: 12453366
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
ID: 12453560
still having trouble with it.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 100 total points
ID: 12454280
>>     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
ID: 12454995
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
ID: 12455051
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
ID: 12456062
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
ID: 12456517
>>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
ID: 12461383
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

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

636 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