[snip]

Fast is good!

I wrote this last night:

===========================================================================

//FIBONACCI SERIES

//0,1,1,2,3,5,8,13,21,34,55,89...

[...]

int Fib(int num) {

int i;

if(num==0) {i = 0;}

else if(num==1) {i = 1;}

else if(num>=2) {i = Fib(num-1) + Fib(num-2);}

return i;

}

[...]

// Then I found Binet's formula:

//

http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
int FibBinet(int num) {

int i = (pow(1+sqrt(5),num) - pow(1-sqrt(5),num)) / (pow(2,num) *

sqrt(5));

return i;

}

A few comments...

1. Using floating point may give problems with rounding

behavior.

2. Using double probably limits the results to 50-ish bits

(ie, on common processors).

3. It's easy to write an integer version that gives results

exact to 64 bits, and fairly quickly, by simple iteration, or

three parameter recursion.

I think I got it (simple iteration)! I took another look at my orig

code/output and noticed you don't have to calculate Fib(N) recursively

each iteration, you just have to keep track of the previous 2 numbers

and add them together.

No wonder it was so slow: by the time it got to Fib(40) it had done

Fib(1) through Fib(39) up to thirty-nine times each.

New version:

long long Fib(int num) {

long long a=0,b=1,F;int i=0;

while(i<=num){

if(i<2){F=i;}else{F=a+b;a=b;b=F;}

i++;

}

return F;

}

But I notice Fib(72) and up are slightly different from the FibBinet()

results

long long FibBinet(int num) {

long long FB = (pow(1+sqrt(5),num) - pow(1-sqrt(5),num)) /

(pow(2,num) * sqrt(5));

return FB;

}

int main(void) {

long long a,b;

for (int i=0;i<=100;i++) {

a = Fib(i);

b = FibBinet(i);

if(a != b) {

printf("Fib(%d) = %-*llu Binet = %llu\n", i,22,a,b);

}

}

}

[dfs@home misc]$ ./Fibonacci

Fib(72) = 498454011879264 Binet = 498454011879265

Fib(73) = 806515533049393 Binet = 806515533049395

Fib(74) = 1304969544928657 Binet = 1304969544928660

Fib(75) = 2111485077978050 Binet = 2111485077978055

Fib(76) = 3416454622906707 Binet = 3416454622906715

Fib(77) = 5527939700884757 Binet = 5527939700884771

Fib(78) = 8944394323791464 Binet = 8944394323791488

Fib(79) = 14472334024676221 Binet = 14472334024676260

Fib(80) = 23416728348467685 Binet = 23416728348467744

Fib(81) = 37889062373143906 Binet = 37889062373144008

Fib(82) = 61305790721611591 Binet = 61305790721611752

Fib(83) = 99194853094755497 Binet = 99194853094755776

Fib(84) = 160500643816367088 Binet = 160500643816367552

Fib(85) = 259695496911122585 Binet = 259695496911123328

Fib(86) = 420196140727489673 Binet = 420196140727490880

Fib(87) = 679891637638612258 Binet = 679891637638614272

Fib(88) = 1100087778366101931 Binet = 1100087778366105088

Fib(89) = 1779979416004714189 Binet = 1779979416004719360

Fib(90) = 2880067194370816120 Binet = 2880067194370824704

Fib(91) = 4660046610375530309 Binet = 4660046610375544832

Fib(92) = 7540113804746346429 Binet = 7540113804746369024

Fib(93) = 12200160415121876738 Binet = 9223372036854775808

Fib(94) = 1293530146158671551 Binet = 9223372036854775808

Fib(95) = 13493690561280548289 Binet = 9223372036854775808

Fib(96) = 14787220707439219840 Binet = 9223372036854775808

Fib(97) = 9834167195010216513 Binet = 9223372036854775808

Fib(98) = 6174643828739884737 Binet = 9223372036854775808

Fib(99) = 16008811023750101250 Binet = 9223372036854775808

Fib(100) = 3736710778780434371 Binet = 9223372036854775808

Also, from (93) onward the Fib() results look random, while the

FibBinet() result is always 9223372036854775808 (highest 64-bit number+1).

4. Using d'Ocagne's identity, an integer four parameter

recursive version can be written that is both 64-bit

exact and runs faster than the floating point version.

I couldn't find much on the web about d'Ocagne's identity, other than a

description and this page.

http://2000clicks.com/mathhelp/BasicRecurrenceRelationsFibonacci.aspx
So far all I've been able to do is prove the identity holds (sometimes

- it seems to hold where m>=n for integers >=0):

int docagne(int m, int n) {

printf("docagne %d,%d: ", m,n);

if((Fib(m)*Fib(n+1))-(Fib(n)*Fib(m+1))==pow(-1,n)*Fib(m-n)) {

printf("identity holds\n");

} else {

printf("identity (or DFS) fails\n");

}

return 0;

}

int main(void) {

int a=-10,b=10;

printf("\nd'Ocagne identity =

(Fib(m)*Fib(n+1))-(Fib(n)*Fib(m+1))=(-1^n)*Fib(m-n)\n\n");

for (int i=a;i<=b;i++) {

for (int j=a;j<=b;j++) {

docagne(i,j);

}

}

}

I leave 3 and 4 as exercises (but feel free to ask for

help if you get stuck).

Cool exercises!

I'm stuck on using docagne to generate the Fib series, and on the

recursive stuff. I do like the idea of recursive functions - they seem

tidier or something.