One of the common methods for calculating fibonacci numbers quickly involves matrix exponentiation. I recently came across a new algorithm for generating Fibonacci numbers by Japanese mathematician Takahashi Daisuke. Here is my implementation:
from math import log, floor def fib (n): if n == 0: return n F, L, sign, exp = 1, 1, -2, int(floor(log (n,2))) mask = 2**exp for i in xrange (exp - 1): mask = mask >> 1 F2 = F**2 FL2 = (F + L)**2 F = ((FL2 - 6*F2) >> 1) - sign if n & mask: temp = (FL2 >> 2 ) + F2 L = temp + (F << 1) F = temp else: L = 5*F2 + sign sign = -2 if n & mask else 2 if n & (mask >> 1) == 0: return F * L else: return ((F + L) >> 1) * L - (sign >> 1)
Here is a comparison of my implementation of the Daisuke algorithm above versus an implementation of the matrix exponentiation algorithm (source unfortunately can't be found right now):
About the author
I'm Steve Krenzel, a software engineer and co-founder of Thinkfuse. Contact me at firstname.lastname@example.org.