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:
Code:
pow(PHI, n) / sqrt(5.0)
is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.
The correct way would be:
Code:
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) );
}
(use long long instead of int for large n, as the result will obviously not fit in 32 bit integers).
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)
Code:
unsigned int Fib( unsigned int n )
{
n--;
unsigned int a=1,b=0,c=1,p=1,t;
while (p<=n) p += p;
do
{
p >>= 1;
t = b*b;
b *= a+c;
a = a*a + t;
c = c*c + t;
if (n&p)
{
c = b;
b = a;
a += c;
}
}
while (p>1);
return a;
}
This performs about 3 times as fast as the pow / √5 method. Of course, again, use long long for large n.