I found the perl module Math::Fibonacci which uses this relationship to calculate the n-th Fibonacci number using the fast algorithm:

F(n) = ~ g^n/sqrt(5)

where g is the golden ratio and ~ means “take the nearest integer.”

I experimented a bit with that algorithm and it is quite useful for Fibonacci values that can be expressed within the precision of native floats. To get beyond the limitations of native floats, I used Math::BigFloat. Unfortunately, it took much longer to get results than just using the trivial expansion with Math::BigInt, and those results were not exact.

Then I found Math::Big which has a fibonacci function. In scalar mode, it uses a very fast divide-and-conquer algorithm based on the formula:

F(n+m) = Fm * Fn+1 + Fm-1 * Fn

Using Math::Big::fibonacci, I can calculate the 10,000-th Fibonacci number in 0.37 seconds with this command line:

perl -MMath::Big -e 'print 0+Math::Big::fibonacci($ARGV[0]),"\n"' 10000

It takes about 2.5 seconds to get the same result with the trivial expansion using the code I posted yesterday.

[/programming] [link]