DaniWeb Forum Index > Software Development > C++

C++ RSS

C++ Fibonacci program help

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Jun 2005

Posts: 92

Reputation: djbsabkcb is an unknown quantity at this point

Solved Threads: 0

djbsabkcb

Offline

Junior Poster in Training

C++ Fibonacci program help

Jul 13th, 2005

Below is my code for Fibonacci sequence, however when I use a large number such as 100 or more it takes forever to produce output. Why? any help would be appreciated.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
 
using namespace std;
long fib_num ( long  );
 
 
 
int main()
{
 
 
        long  num = 0;
        long  sequence = 0;
 
        cout << " Enter a positive number and I will compute the Fibonacci sequence for that number: ";
        cin >> num;
        if ( num < 0)
        {       cout << " Number must be greater than zero " << endl;
                return 1;
        }
        cout << endl << endl;
 
        sequence = fib_num(num);
 
        cout << " The " << num << "th number of the Fibonacci sequence is " << sequence << endl;
 
        return 0;
}
 
        long fib_num ( long n)
        {
                if ( n == 0)
                {
                        return 0;
                }
 
                else if ( n == 1 )
                {
                        return 1;
                }
                else
                        return  fib_num( n -1) + fib_num(n-2);
        }
#include <iostream>

using namespace std;
long fib_num ( long  );



int main()
{


        long  num = 0;
        long  sequence = 0;

        cout << " Enter a positive number and I will compute the Fibonacci sequence for that number: ";
        cin >> num;
        if ( num < 0)
        {       cout << " Number must be greater than zero " << endl;
                return 1;
        }
        cout << endl << endl;

        sequence = fib_num(num);

        cout << " The " << num << "th number of the Fibonacci sequence is " << sequence << endl;

        return 0;
}

        long fib_num ( long n)
        {
                if ( n == 0)
                {
                        return 0;
                }

                else if ( n == 1 )
                {
                        return 1;
                }
                else
                        return  fib_num( n -1) + fib_num(n-2);
        }

<< moderator edit: added code tags: [code][/code] >>

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: C++ Fibonacci program help

Jul 13th, 2005

Your fibonacci function runs in exponential time.

Let me put it this way:

Suppose that it takes 1 microsecond to compute fib_num(0) and fib_num(1).

Then, in computing fib_num(2), you'll call fib_num(0), which takes 1 microsecond (mms, I'll abbreviate), and fib_num(1), which also takes 1 mms. This means that fib_num(2) will take at least 2 mms.

Then, to compute fib_num(3), you will call fib_num(2), which takes at least 2 mms, and then fib_num(1), which takes 1 mms. So fib_num(3) takes at least 3 mms.

Continuing this pattern, fib_num(4) would take at least 5 mms, fib_num(5) would take 3 + 5 = 8 mms, and fib_num(6) would take 5 + 8 = 13 mms, at least.

This is actually the fibonacci pattern of growth in runtime. And the fibonacci pattern grows exponentially. You'll find that for large values of n (like 100), the time it takes to compute f(n) is about 1.618 times the amount of time it takes to compute f(n - 1). If fib_num(6) takes 13 microseconds, then fib_num(100) would take at least 1.618 to the 94th power times 13 microseconds. And 1.618**94 * 13 equals 5.74e20. This amount of microseconds is equal to 5.74e14 seconds. Which is about 18 million years. You might as well get up for some coffee.

Even if you ran this program on a computer that was 10000 times faster (the times mentioned above are kind of slow by today's standards), it would still take at least 1819 years to compute. And computing fib_num(101) would take at least 2944 years to complete.

Notice that you recurse to fib_num(n-1) and fib_num(n-2). But in order to compute fib_num(n-1), you'll call fib_num(n-2) and fib_num(n-3). Notice that fib_num(n-2) is getting calculated multiple times. This is redundant.

In order to compute fib_num efficiently, you'll want to use a loop instead of recursion.

•

Join Date: Jun 2005

Posts: 62

Reputation: freemind is an unknown quantity at this point

Solved Threads: 1

freemind

Offline

Junior Poster in Training

Re: C++ Fibonacci program help

Jul 13th, 2005

Numerous recursive calls of a function produce delays. The maths is done in the previous answer to your question by Rashakil Fol. Besides this sequence produces really big numbers. I changed the algorithm a bit and even the 50th member of the sequence goes over the boundaries of the long (at least on my machine). To save time though you can exchange the recursion with a simple for loop. I think the algorithm should be right.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
long fib_num ( long n)
{
     long last=2;     // temporary "last" number in the sequence
     long blast=1;    // one before the temporary "last"
     long sum;
 
     switch(n) {
               case 0: return 0;
                    break;
               case 1: return 1;
                    break;
               case 2: return 2;
                    break;
               default: for(long i=3; i != n; i++) {
                                 sum=blast+last;
                                 blast=last;
                                 last=sum;
                        }
                        return sum;
                    break;
     }
}
long fib_num ( long n)
{
     long last=2;     // temporary "last" number in the sequence
     long blast=1;    // one before the temporary "last"
     long sum;

     switch(n) {
               case 0: return 0;
                    break;
               case 1: return 1;
                    break;
               case 2: return 2;
                    break;
               default: for(long i=3; i != n; i++) {
                                 sum=blast+last;
                                 blast=last;
                                 last=sum;
                        }
                        return sum;
                    break;
     }
}

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: C++ Fibonacci program help

Jul 13th, 2005

Maybe something simpler...

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
long fib_num(long n)
{
	long low(0), high(1);
 
	while (n--) {
		high += low;
		low = high - low;
	}
 
	return low;
}
long fib_num(long n)
{
	long low(0), high(1);

	while (n--) {
		high += low;
		low = high - low;
	}

	return low;
}

•

Join Date: Jul 2005

Posts: 10

Reputation: Kazastankas is an unknown quantity at this point

Solved Threads: 0

Kazastankas Kazastankas is offline

Offline

Newbie Poster

Re: C++ Fibonacci program help

Jul 14th, 2005

•

Originally Posted by Rashakil Fol

Maybe something simpler...
Help with Code Tags

C++ Syntax (Toggle Plain Text)
long fib_num(long n)
{
	long low(0), high(1);
 
	while (n--) {
		high += low;
		low = high - low;
	}
 
	return low;
}
long fib_num(long n) { long low(0), high(1); while (n--) { high += low; low = high - low; } return low; }

Wouldn't that trap high at 1 and low at 0? Perhaps 1, 1 are what you meant as starting vars.

•

Join Date: Sep 2004

Posts: 7,580

Reputation: Narue has a reputation beyond repute

Solved Threads: 709

Narue

Offline

Code Goddess

Re: C++ Fibonacci program help

Jul 14th, 2005

>however when I use a large number such as 100 or more it takes forever
It will also probably produce incorrect results. Fibonacci numbers grow at such a large amount that unless N is small, you'll overflow a long. Even using unsigned long to protect against undefined behavior and extend the range a bit, you can still only accurately produce fibonacci numbers up to a value of 45 (if I recall correctly) for N when long is 32 bits.

But the speed issue is the many, many unnecessary repeated calculations. You can fix it by using a non-recursive algorithm (as described by everyone else), or by saving the results in an array for the recursive algorithm and skipping the recursive calls if the result for a value has already been worked out:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
 
// Slow textbook version
unsigned long fib1 ( unsigned long i )
{
  if ( i < 2 )
    return i;
 
  return fib1 ( i - 1 ) + fib1 ( i - 2 );
}
 
// Fast caching version
unsigned long fib2 ( unsigned long i )
{
  unsigned long x;
  static unsigned long save[45];
 
  if ( save[i] != 0 )
    return save[i];
  else if ( i < 2 )
    x = i;
  else
    x = fib2 ( i - 1 ) + fib2 ( i - 2 );
 
  return save[i] = x;
}
 
int main()
{
  std::cout<< fib1 ( 45 ) <<'\n';
  std::cout<< fib2 ( 45 ) <<'\n';
}
#include <iostream>

// Slow textbook version
unsigned long fib1 ( unsigned long i )
{
  if ( i < 2 )
    return i;

  return fib1 ( i - 1 ) + fib1 ( i - 2 );
}

// Fast caching version
unsigned long fib2 ( unsigned long i )
{
  unsigned long x;
  static unsigned long save[45];

  if ( save[i] != 0 )
    return save[i];
  else if ( i < 2 )
    x = i;
  else
    x = fib2 ( i - 1 ) + fib2 ( i - 2 );

  return save[i] = x;
}

int main()
{
  std::cout<< fib1 ( 45 ) <<'\n';
  std::cout<< fib2 ( 45 ) <<'\n';
}

I'm here to prove you wrong.

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: C++ Fibonacci program help

Jul 14th, 2005

•

Originally Posted by Kazastankas

Wouldn't that trap high at 1 and low at 0? Perhaps 1, 1 are what you meant as starting vars.

Did you actually think through a few iterations of the loop?

•

Join Date: Jun 2005

Posts: 92

Reputation: djbsabkcb is an unknown quantity at this point

Solved Threads: 0

djbsabkcb

Offline

Junior Poster in Training

Re: C++ Fibonacci program help

Jul 16th, 2005

I tried values 1 and 1 which made program work correctly. Thanks, for all the input everyone.

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: C++ Fibonacci program help

Jul 17th, 2005

In response to Narue's fib2:

If we're going to have a static, fixed-length, read-only array, then heck,

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
unsigned long fib3 ( unsigned long i )
{
  static unsigned long save[45] = {0, 1, 1, 2, 3, 5, 8, 13, 21,
 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
 317811, 514229, 832040, 1346269, 2178309, 3524578,
 5702887, 9227465, 14930352, 24157817, 39088169,
 63245986, 102334155, 165580141, 267914296, 433494437,
 701408733};
 
  return save[i];
}
unsigned long fib3 ( unsigned long i )
{
  static unsigned long save[45] = {0, 1, 1, 2, 3, 5, 8, 13, 21,
 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
 317811, 514229, 832040, 1346269, 2178309, 3524578,
 5702887, 9227465, 14930352, 24157817, 39088169,
 63245986, 102334155, 165580141, 267914296, 433494437,
 701408733};

  return save[i];
}

•

Join Date: Sep 2004

Posts: 7,580

Reputation: Narue has a reputation beyond repute

Solved Threads: 709

Narue

Offline

Code Goddess

Re: C++ Fibonacci program help

#10

Jul 17th, 2005

>If we're going to have a static, fixed-length, read-only array, then heck
In real code, yea. But for learning purposes, that only teaches you to google for the first N fibonacci numbers.

I'm here to prove you wrong.