Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.
First of all, the problem with this method posted above:
is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.
pow(PHI, n) / sqrt(5.0)
The correct way would be:
(use long long instead of int for large n, as the result will obviously not fit in 32 bit integers).
int Fib( int n )
static const double s = sqrt(5.0);
return int( (pow(1+s,n)-pow(1-s,n))/(pow(2.0,n)*s) );
There is, however, an even much faster way. After quite some experimenting with several approaches and lotsa optimizing, this is imho the ultimate solution: (besides using a direct lookup or caching table of course)
This performs about 3 times as fast as the pow / √5 method. Of course, again, use long long for large n.
unsigned int Fib( unsigned int n )
unsigned int a=1,b=0,c=1,p=1,t;
while (p<=n) p += p;
p >>= 1;
t = b*b;
b *= a+c;
a = a*a + t;
c = c*c + t;
c = b;
b = a;
a += c;