Ad:

C++ Discussion Thread
Unsolved
Views: 72257

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Jul 13th, 2005

C++ Fibonacci program help

Expand Post »

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.

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] >>

Similar Threads

need an idea to program in Computer Science

djbsabkcb

Reputation Points: 14

Solved Threads: 0

Junior Poster in Training

Offline

92 posts
since Jun 2005

Permalink

Jul 13th, 2005

Re: C++ Fibonacci program help

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.

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 172

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Jul 13th, 2005

Re: C++ Fibonacci program help

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.

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;
     }
}

freemind

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

62 posts
since Jun 2005

Permalink

Jul 13th, 2005

Re: C++ Fibonacci program help

Maybe something simpler...

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;
}

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 172

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Jul 14th, 2005

Re: C++ Fibonacci program help

Quote originally posted by Rashakil Fol ...

Maybe something simpler...
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.

Kazastankas

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

10 posts
since Jul 2005

Permalink

Jul 14th, 2005

Re: C++ Fibonacci program help

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

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';
}

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Jul 14th, 2005

Re: C++ Fibonacci program help

Quote 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?

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 172

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Jul 16th, 2005

Re: C++ Fibonacci program help

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

djbsabkcb

Reputation Points: 14

Solved Threads: 0

Junior Poster in Training

Offline

92 posts
since Jun 2005

Permalink

Jul 17th, 2005

Re: C++ Fibonacci program help

In response to Narue's fib2:

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

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];
}

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 172

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Jul 17th, 2005

Re: C++ Fibonacci program help

>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.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Page 1
2
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Quick sort

Next Thread in C++ Forum Timeline: Prime numbers problem

DaniWeb Message

Cancel Changes

User Name
Password