fibonacci

[invictus]

Well im sorry to post yet another question about fibonacci...
But I could not find out on the other topics how to solve my problem.

Im a beginner in c++ and gotta make a program that calculates fib. up to 10000'th number.

here is what I tried. but failed for 50 and higher.
Probably coz it goes beyond INT_MAX.. but how to solve it :S?

// Programma: Fibonacci
void fibo(){
    long long fib[10000];
        fib[0] = 1;
        fib[1] = 1;
    long i;
    long n;
    cout << "welk fibonacci getal wil je hebben?" <<endl;
    cin >> i;
    if (i == 0){
     cout << "het " << i << "de fibonacci getal bestaat niet" << endl; }
    if (i == 1){
       cout << "het " << i << "ste fibonacci getal is " << fib[i-1] << endl; } 
    if (i == 2){
       cout << "het " << i << "de fibonacci getal is " << fib[i-1] << endl; }
    if (i > 2) {
       n = 2;
       while (i-n >= 0){
       fib [n] = fib[n-1] + fib[n-2];
       n++;}
       cout << "het " << i << "de fibonacci getal is " << fib[n-2] << endl; }  
}

edit:
after much trying I made it up to 92

[hamsterman]

You are right. You can't do this with int and not even with long long int. You have to use a bignum library.
http://gmplib.org/
Though I somehow have a feeling your instructor simply didn't know how quickly Fibonacci numbers grow.
I just calculated 10000th Fibonacci number with my own bignum library. I got

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

I wonder if this is correct..

[invictus]

Been asking around and indeed we need to make it with pointers...
so gotta start training with that :)

http://www3.wolframalpha.com/input/?i=fibonacci%2810000%29

so yes it seems to be correct :)

ill post if I have any difficulties with the pointers :)

[D80DSL3A]

@hamsterman: A chance to test our new BigInt classes! Mine gives the same value as yours (nice).

How did you find the value using your library? I wrote a special function so I could do it with just 3 instances of a BigInt:

BigInt findFib( int N )
{
	BigInt fibs[3];
	fibs[0] = 0;
	fibs[1] = 1;
	for(int j=2; j<=N; j++)
		fibs[j%3] = fibs[(j-1)%3] + fibs[(j-2)%3];// so they cycle as needed
	return fibs[N%3];
}

[hamsterman]

I wrote for(integer a = 1, b = 0, c, i = 0; i < 10000; i += 1, c = a, a += b, b = c);.
I <3 overcomplicated for loops.