## Fibonacci Fun Time

I signed up for Coursera’s Algorithmic Toolbox for fun and to dust the cobwebs on some CS FUNdamentals.

The first programming assignment involved a number of different variations on calculating Fibonacci numbers. And although they provided a more efficient solution than the naive recursive implementation, I wanted do some googling and see if there were any other faster implementations.

I came upon Nayuki’s fast doubling implementation and wanted to do a quick and dirty benchmark against more common algorithms. Here it is!

## Decorator functions

from functools import wraps

def memoize(func):
table = {}

@wraps(func)
def wrapper(*args):
if args not in table:
table[args] = func(*args)

return table[args]

return wrapper

def callrange(func):
@wraps(func)
def wrapper(n):
for i in range(n):
func(i)

return func(n)

return wrapper

## Fibonacci functions

def recursive_fibonacci(n):
if n in (0, 1):
return n

return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)

@callrange
@memoize
def memoized_fibonacci(n):
if n in (0, 1):
return n

return memoized_fibonacci(n - 1) + memoized_fibonacci(n - 2)

def list_fibonacci(n):
L = [i for i in range(n + 1)]

for i in range(2, len(L)):
L[i] = L[i - 1] + L[i - 2]

return L[n]

def sum_fibonacci(n):
if n in (0, 1):
return n

i = 2
j, k = 0, 1

while i < n + 1:
j, k = k, j + k
i += 1

return k

def fast_doubling_fibonacci(n):
"""
Fast doubling Fibonacci algorithm

https://www.nayuki.io/page/fast-fibonacci-algorithms
"""
def _fib(n):
if n == 0:
return (0, 1)
else:
a, b = _fib(n // 2)
c = a * (b * 2 - a)
d = a * a + b * b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)

return _fib(n)[0]

def test(f):
solutions = [int(n) for n in open('fibonacci.txt')]

for i in range(len(solutions)):
assert f(i) == solutions[i]

def time(f, n):
import time

start = time.time()
f(n)
end = time.time()

print "%24s: %12f" % (f.func_name, end - start)  # 1 sec lsb

if __name__ == '__main__':
F = [
memoized_fibonacci,
list_fibonacci,
sum_fibonacci,
fast_doubling_fibonacci,
]

for f in F:
test(f)
time(f, 10000)

\$ python fibonacci.py
memoized_fibonacci:    22.862408
list_fibonacci:     0.005365
sum_fibonacci:     0.002401
fast_doubling_fibonacci:     0.000047