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.
