DFS said:

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

}

Oftentimes when using a recursive formulation there needs to be a

helper function that has an extra parameter or two where the real

work is done (disclaimer: not compiled or tested):

typedef unsigned long long U64;

static U64 fibber( U64 a, U64 b, unsigned i, unsigned n );

U64

fibonacci( unsigned n ){

return fibber( 1, 0, 0, n );

}

U64

fibber( U64 a, U64 b, unsigned i, unsigned n ){

return i == n ? b : fibber( b, a+b, i+1, n );

}

Can you see the relationship between this recursive definition

and your iterative one? Incidentally, notice how the recursive

call means we don't need the temporary variable F.

Probably you can revise this code so the helper function takes

only three parameters rather than four. Try it!

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;

}

Here is the basic outline. From d'Ocagne we know

f( 2n ) == ( f(n-1) + f(n+1) ) * f(n)

f( 2(n-1) ) == ( f(n-2) + f(n) ) * f(n-1)

If you play around with these, and keeping in mind the

identity that f(k-1) + f(k) == f(k+1), you should find that

values for f( 2n-1 ), f( 2n ), and f( 2n+1 ) can be

expressed in terms of just f(n-1) and f(n)

f( 2n-1 ) == ... something in terms of f(n-1) and f(n) ...

f( 2n ) == ... something in terms of f(n-1) and f(n) ...

f( 2n+1 ) == ... something in terms of f(n-1) and f(n) ...

This means if we know f(k-1) and f(k), we can calculate either of

the pairs { f(2k-1), f(2k) } or { f(2k), f(2k+1) } using a small

number of additions and multiplications. That in turn suggests

we can use the binary decomposition of n to ascend a chain where

at each step we either "double" or "double and add one", ie,

choose either the first pair or the second pair. Starting off

with f(-1) == 1 and f(0) == 0, and looking at the bits of n

starting at the high-order bit, this method will calculate

fibonacci(n) in only O( log n ) steps.