| Previous | Index | Next |
Fast Fibonacci Numbers
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 steve@thinkfuse.com. |
|
| Previous | Next |