Geek asks and answers

Finding 1500000 Fib Number Using C ++

I wrote the following code to find the 1500,000th Fibonacci number (please ignore the terrible indent, I wrote this in about 2 minutes). I need this as a string. This should supposedly 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 through 3 numbers every time) I understand that the problem is that the number must be large in order to be contained as an int. Is there a way to save it without containing it as an int or file (since that would be extremely inefficient)? If so, how do I do this?

+3
source share
2 answers

Use the Bignum library .

+2
source

, bignum:

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

, O (log (n)), O (n) , : n

, n n- n * log (phi)/log (2) = n * 0,69 , 1.5M ^ th 130kb , 300kb ( 2 ^ (10000000) 10 ^ (300000))

n = 1500

, ( 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 );
}

, . ( 78- )

+1

More articles:


All Articles