Finding the 1500000th Fib Number Using C++

Question

I wrote the following code to find the 1500000th Fibonacci number(Please ignore horrible indenting, I wrote this in about 2 minutes). I need it as a string. This should, hypothetically work:

#include <cstdlib>
#include <iostream>
#include <sstream>
int i;
int b=1;
int c=2;
using namespace std;

int main(int argc, char *argv[])
{

    int fib=1500000;

for (i=1;i<fib-3;i++){
c=b+c;
b=c-b;
}
   stringstream ss;
   ss << c;
   string d=ss.str();
cout << d << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

It goes through the process 1500000-3 times(It goes over by 3 numbers every time) I understand that the problem is that the number is to big to be contained as an int. Is there any way for me to store it without containing it as an int or file(Since that would be grossly inefficient)? If so, how would I do it?

Answer 1

Use a Bignum library.

Answer 2

If you need an exact form, you might use one of the other recurrence relations with a bignum library:

fib(2*n) = fib(n)^2 + fib(n-1)^2
fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))

Which should reduce the number of calculations needed to O(log(n)) rather than O(n) You can see pseudocode for a method based on this here: nth fibonacci number in sublinear time

Note that the n^th fibonacci number requires about n*log(phi)/log(2) = n*0.69 binary digits to represent, so exact representation of the 1.5M^th will require about 130kb to represent in binary, or 300kb as a string ( being approximately 2^(10000000) or 10^(300000) )

---

Removed as doubles overflow at about n=1500

You can do this directly using doubles as follows ( adapted from http://en.wikipedia.org/wiki/Fibonacci_number ) :

double fib( int n )
{
   static const SQRT_5 = sqrt(5.0);
   static const phi = (1.0+SQRT_5)/2.0;
   return floor( (pow(phi,n)/SQRT_5) + 0.5 );
}

Although if you need every digit, this wont work. ( It will only give every digit upto about the 78th fibonacci number)

Answer 3

Boost makes using bignums extraordinarily easy.

#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int integer;

integer fibonacci( unsigned long long n )
{
  integer a = 0;
  integer b = 1;
  while (n --> 0)
  {
    integer c = a + b;
    a = b;
    b = c;
  }
  return a;
}


#include <iostream>
#include <string>

int main( int argc, char ** argv )
try
{
  long long n = std::stoll( argc == 2 ? argv[1] : "" );
  if (n < 0) throw 1;
  std::cout << fibonacci( n ) << "\n";
}
catch (...)
{
  std::cerr << 
    "usage:                                     \n"
    "  fibonacci N                              \n"
    "where N is the Fibonacci number to compute.\n";
  return 1;
}

In the example above I have used the native Boost bignum type, which is:

• header only (no need to compile Boost!)
• pretty darn quick
  — I computed fibonacci(1500000) in about two minutes on my ancient AMD Sempron 130. If I knock off a zero the results are almost instantaneous.

If that isn’t fast enough for you, Boost Multiprecision also provides backends for:

• GNU GMP
  This is the best bignum library out there, used in almost all serious bignum computing contexts, but it is encumbered by copyleft and is notoriously difficult to set up properly.
• libTomMath
  This is significantly easier to install, but you still must know what you are doing.

Answer 4

The 1500000th Fibonacci number is printed in C99 using this answer with just a change :

#define BUFFER_SIZE 18935

There is no library, output should be like (313,482 digits) :

129089216811873951612785 ... 853738956168354898000000
took 59s

Computation of f(1500000) took 30s and base conversion too, so it's about a minute.

And : In 1963 Stephen P. Geller used an IBM 1620 computer to show that the last four digits repeat every 15,000 times, the last five repeat every 150,000 times, and finally, after the computer ran for nearly three hours, a repetition of the last six digits appeared at the 1,500,000th Fibonacci number.

Try f(15000) online - Thank You.

Answer 5

Are you sure C++ is fast at all ?

    gawk  -v _____='1500000' -v PREC=20000 -p- -Mbe '

    BEGIN {
     1      _ += ___ = _ ^= ____ = __ = _ < _
     1      _____ += ___
     1      ____ = --_____
     1      do {
     1          print __ = length(_ = fib(____)), substr(_, 1, 50), substr(_, __ + 1 - 50)
        } while (++____ < _____)
    }

     1  function fib(______, _, __, ___, ____, _____)
    {
     1      if ((______ = +_ < ______ ? +______ : +_) < (__ *= (__ = _ ~ _) + (++__))) {
            return (______ - ((! _) < (______ % --__)))
        }
     1      _____ = (___ = __ = (_ = _ < _) ~ _) + ___
    20      while ((___ += ___) <= ______) {
    20          ++____
        }
    21      do {
    21          __ = (__ * __ + _ * _) substr(_ *= __ + __ - _, ___, ! ___)
    21          if (int(______ / (___ /= _____)) % _____) { # 10
    10              __ = (__ + _) substr(_ = __, ___, ! ___)
            }
        } while (____--)
     1      return _
    }
( gawk -v _____='1500000' -v PREC=20000 -p- -Mbe ; )  0.10s user 0.01s system 95% cpu 0.115 total

 313482 12908921681187395161278531776694736120150441703840        
        02113051432895630172796932853738956168354898000000

*How the heck C++ took 59.0 secs for something awk takes 0.115 secs