/dev/random

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

    Copyright (c) 2015 Project Nayuki
    All rights reserved. Contact Nayuki for licensing.
    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