Fibs Faster

from numba import jit


def ifib(x):
    fibn = 0
    fibo = 1
    for i in xrange(1, x):
        fibo, fibn = fibo+fibn, fibo
    return fibo


def makemem():
    memo = {1: 0, 2: 1}

    def imem(x):
        if x in memo:
            return memo[x]
        m = len(memo)
        fibo = memo[m]
        fibn = memo[m-1]
        for i in xrange(m, x+1):
            fibo, fibn = fibo+fibn, fibo
            memo[i] = fibo
        return fibo

    return imem


@jit
def jfib(x):
    fibn = 0
    fibo = 1
    for i in xrange(1, x):
        fibnn = fibo
        fibo = fibo+fibn
        fibn = fibnn
    return fibo


def fastFib(x, memo):
    assert type(x) == int and x >= 0 and type(memo) == dict
    if x == 1 or x == 2:
        return 1
    if x in memo:
        return memo[x]
    memo[x] = fastFib(x-1, memo) + fastFib(x-2, memo)
    return memo[x]


def fib(x):
    assert type(x) == int and x >= 0
    if x == 1 or x == 2:
        return 1
    else:
        return fib(x-1) + fib(x-2)




"""

from memoization import *

f = makemem()  # prepare memoized version

%time fib(30)
CPU times: user 531 ms, sys: 75 ms, total: 606 ms
Wall time: 512 ms
Out[4]: 832040

%time fastFib(30, {})
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 62.9 µs
Out[5]: 832040

%time ifib(30)
CPU times: user 8 µs, sys: 0 ns, total: 8 µs
Wall time: 12.2 µs
Out[6]: 832040

%time f(30)
CPU times: user 24 µs, sys: 1 µs, total: 25 µs
Wall time: 33.1 µs
Out[7]: 832040

%time jfib(30)
CPU times: user 47.2 ms, sys: 5.09 ms, total: 52.3 ms
Wall time: 47.3 ms
Out[8]: 832040L

"""