Sun, 28 Mar 2004

Still toying with Fibonacci numbers

Yesterday, I said I needed to stop this silliness with Fibonacci numbers. But I still remain intrigued.

Ron Knott’s page, which I referenced yesterday, includes some information about the relationship between Fibonacci numbers and the Golden Ratio: (sqrt(5)+1)/2, or 1.61803…

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]

About this weblog

This site is the personal weblog of Marc Mims. You can contact Marc by sending e-mail to:
marc@questright.com.

Marc writes here about cycling, programming, Linux, and other items of personal interest.

This site is syndicated with RSS.

Archives

Credits

CSS stolen from Tom Coates who didn't even complain.