C++ Fibonacci program help

[djbsabkcb]

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

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

[Rashakil Fol]

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.

[freemind]

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.

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

[Rashakil Fol]

Maybe something simpler...

long fib_num(long n)
{
	long low(0), high(1);

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

	return low;
}

[Kazastankas]

Maybe something simpler...

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.

[Narue]

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

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

[Rashakil Fol]

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?

[djbsabkcb]

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

[Rashakil Fol]

In response to Narue's fib2:

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

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

[Narue]

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

[level007]

#include <iostream.h>
#include <stdlib.h>

int fibonacci()
{
 unsigned long fib;
 cout << "Please input a number of fibonacci numbers which will be displayed: ";
 cin >> fib;
 unsigned long a = 1;
 unsigned long b = 1;
 unsigned long temp;
 for (int count1 = 0; fib != count1; count1 ++)
 {
  cout << a << " is the " << count1 + 1 << "th number\n";
  temp = b;
  b += a;
  a = temp;
 }
 return 0;
}

int main()
{
 fibonacci();
 cout << endl;
 system("PAUSE");
 return 0;
}

[iamthwee]

Please check the date on the threads before you post.

[invisal]

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

No, and it works perfectly. For example: the 10th of fibonacci:

high = 1   ; low = 0
------------------------
high = 1   ; low = 1
high = 2   ; low = 1
high = 3   ; low = 2
high = 5   ; low = 3
high = 8   ; low = 5
high = 13  ; low = 8
high = 21  ; low = 13
high = 34  ; low = 21
high = 55  ; low = 34
high = 89  ; <strong>low = 55</strong>

[invisal]

Oh crap, I got fool :( Next time, I will check the date. (mad)

[fancccc]

but how to determine whether if X is a term of the Fibonacci or not? (for last algorithm)

[hajiakhundov]

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

yeah, its 1 1.
But now the problem is the long. This would work only till n = 46.
What if I wand fib (100)? Any suggestions?
Regards

[rubberman]

It was slow, but it worked. Many many years ago I wrote a fibonacci generator using try/throw/catch exceptions in C++ as a test of the exception handling of various compilers of the time (about 20 years ago - a lot of them were buggy). I'd post it here, but the code is hiding on a floppy somewhere in my code library and my last computer with a floppy drive is in storage... :-( Oh, well. Anyway, it can be done, but not effectively for very large numbers! I think we stopped at 13 or so. Enough to test the compiler, but not so much as to overflow the stack.

In other history, I used fibonacci sequences in an index fund balancing program I wrote for a major investment fund back in 1984-85 in San Francisco. They had to rebalance the funds to track whatever indexes they were tied to every day, and this was for over $10B on the S&P500, Russel2000, etc. We were actually able to do that with PC's (with 8087 coprocessors), sucking down the close-of-day prices from the market data feeds, building up the model portfolios, and generating buy/sell orders for the open of the next day.

[rubberman]

yeah, its 1 1. But now the problem is the long. This would work only till n = 46. What if I wand fib (100)? Any suggestions? Regards

A recursive fib routine will crash and burn before you get to very big numbers. This is one of those situations where if your compiler can't do adequate optimization you are going to have to unroll it by hand. The algorithm is naturally recursive, and building an optimized version that is not means you will probably have to resort to the evil "goto" statement, and a lot of insidious cruft that you will NEVER want to look at again after it is working!

[rubberman]

Ok. This is pretty snappy and using unsigned long long (64bit) values, you can get a fibonacci number up to about 100. On my system, there is no apparent delay from input to output of any number. In any case, for a 32bit integer (unsigned), fib(47) is as high as you can go before you wrap around. Not sure of the exact number, but I think a 64bit value gets you to about 100 or so. It definitely wraps shortly after that.

#include <stdlib.h>
#include <iostream>

using namespace std;

unsigned long long fib2(unsigned long long n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;
    return (fib2(n-1) + fib2(n-2));
}

unsigned long long fib( unsigned long long n )
{
   unsigned long long array[n];

   if (n <= 10) return fib2(n);

   // Build up array of 10 elements to work from
   for (unsigned long long i = 0; i < 10; i++)
   {
      array[i] = fib2(i);
   }

   // Populate the rest of the array by using the previously computed values.
   for (unsigned long long i = 10; i < n; i++)
   {
      array[i] = array[i-1] + array[i-2];
   }

   // Now return final value for N
   return array[n-1] + array[n-2];
}

int main( int argc, const char* argv[] )
{
    for (int i = 1; i < argc; i++)
    {
       cout << "fib(" << argv[i] << ") = " << dec << fib(strtoul(argv[i], 0, 10)) << endl;
    }
    return 0;
}