fibmat.py

class fibmatwhip:
    def __init__(self, mat=None):
        self.mat = mat or (1, 1, 1, 0)
        self.cache = {
            0: self.mat,
        }
        self.cache_max = 0

    def fib(self, n):
        from math import log
        try:
            if n < 2:
                return self.mat[3 - n]
            if n == 1 << int(log(n, 2)):
                return self.cache[int(log(n, 2))][1]
        except KeyError:
            pass
        cm = self.cache_max
        while int(log(n, 2)) > cm:
            a, b, c, d = self.cache[cm]
            self.cache[cm + 1] = (
                a * a + b * b,
                b * (a + d),
                b * (a + d),
                b * b + d * d
            )
            cm += 1
        self.cache_max = cm
        ans = self.cache[int(log(n, 2))]
        n -= 1 << int(log(n, 2))
        while n > 0:
            tmp = self.cache[int(log(n, 2))]
            ans = (
                ans[0] * tmp[0] + ans[1] * tmp[2],
                ans[0] * tmp[1] + ans[1] * tmp[3],
                ans[2] * tmp[0] + ans[3] * tmp[2],
                ans[2] * tmp[1] + ans[3] * tmp[3],
            )
            n -= 1 << int(log(n, 2))
        assert ans[1] == ans[2]
        return ans[1]

class fibmatwhipmod:
    def __init__(self, mat=None, mod=1000000007):
        self.mod = mod
        self.mat = mat or (1, 1, 1, 0)
        self.cache = {
            0: self.mat,
        }
        self.cache_max = 0

    def fib(self, n):
        from math import log
        try:
            if n < 2:
                return self.mat[3 - n]
            if n == 1 << int(log(n, 2)):
                return self.cache[int(log(n, 2))][1] % self.mod
        except KeyError:
            pass
        cm = self.cache_max
        while int(log(n, 2)) > cm:
            a, b, c, d = self.cache[cm]
            self.cache[cm + 1] = (
                (a * a + b * b) % self.mod,
                (b * (a + d)) % self.mod,
                (b * (a + d)) % self.mod,
                (b * b + d * d) % self.mod
            )
            cm += 1
        self.cache_max = cm
        ans = self.cache[int(log(n, 2))]
        n -= 1 << int(log(n, 2))
        while n > 0:
            tmp = self.cache[int(log(n, 2))]
            ans = (
                (ans[0] * tmp[0] + ans[1] * tmp[2]) % self.mod,
                (ans[0] * tmp[1] + ans[1] * tmp[3]) % self.mod,
                (ans[2] * tmp[0] + ans[3] * tmp[2]) % self.mod,
                (ans[2] * tmp[1] + ans[3] * tmp[3]) % self.mod,
            )
            n -= 1 << int(log(n, 2))
        assert ans[1] == ans[2]
        return ans[1] % self.mod

if __name__ == '__main__':
    from recur_memz import fib_rec_memz as fib2

    f = fibmatwhip()
    for x in xrange(300):
        print f.fib(x),
        print fib2(x),
        print '\033[1;32m-- pass\033[0m' if f.fib(x) == fib2(x) else '\033[1;31m-- fail\033[0m'
    for x in reversed(xrange(300)):
        print f.fib(x),
        print fib2(x),
        print '\033[1;32m-- pass\033[0m' if f.fib(x) == fib2(x) else '\033[1;31m-- fail\033[0m'
    print
    print f.cache
    print f.cache_max

    from recur_memz import fib_rec_memz_withmod as fib2
    f = fibmatwhipmod()
    for x in xrange(300):
        print f.fib(x),
        print fib2(x),
        print '\033[1;32m-- pass\033[0m' if f.fib(x) == fib2(x) else '\033[1;31m-- fail\033[0m'
    for x in reversed(xrange(300)):
        print f.fib(x),
        print fib2(x),
        print '\033[1;32m-- pass\033[0m' if f.fib(x) == fib2(x) else '\033[1;31m-- fail\033[0m'

fibrec.py

def fibrec(n):
    if n < 2:
        return n
    return fibrec(n - 1) + fibrec(n - 2)

def fibrecmod(n, mod=1000000007):
    if n < 2:
        return n % mod
    return (fibrecmod(n - 1) + fibrecmod(n - 2)) % mod

fibrecmemz.py

memz = {}

def fib_rec_memz(n):
    try:
        return memz[n]
    except KeyError:
        pass
    if n < 2:
        memz[n] = n
        return memz[n]
    try:
        a = memz[n - 1]
    except KeyError:
        memz[n - 1] = fib_rec_memz(n - 1)
        a = memz[n - 1]
    try:
        b = memz[n - 2]
    except KeyError:
        memz[n - 2] = fib_rec_memz(n - 2)
        b = memz[n - 2]
    memz[n] = a + b
    return memz[n]

modmemz = {}
def fib_rec_memz_withmod(n, mod=1000000007):
    try:
        return modmemz[n] % mod
    except KeyError:
        pass
    if n < 2:
        modmemz[n] = n % mod
        return modmemz[n] % mod
    try:
        a = modmemz[n - 1] % mod
    except KeyError:
        modmemz[n - 1] = fib_rec_memz(n - 1) % mod
        a = modmemz[n - 1] % mod
    try:
        b = modmemz[n - 2] % mod
    except KeyError:
        modmemz[n - 2] = fib_rec_memz(n - 2) % mod
        b = modmemz[n - 2] % mod
    modmemz[n] = (a + b) % mod
    return modmemz[n] % mod

recur_memz.py

memz = {}

def fib_rec_memz(n):
    try:
        return memz[n]
    except KeyError:
        pass
    if n < 2:
        memz[n] = n
        return memz[n]
    try:
        a = memz[n - 1]
    except KeyError:
        memz[n - 1] = fib_rec_memz(n - 1)
        a = memz[n - 1]
    try:
        b = memz[n - 2]
    except KeyError:
        memz[n - 2] = fib_rec_memz(n - 2)
        b = memz[n - 2]
    memz[n] = a + b
    return memz[n]

modmemz = {}
def fib_rec_memz_withmod(n, mod=1000000007):
    try:
        return modmemz[n] % mod
    except KeyError:
        pass
    if n < 2:
        modmemz[n] = n % mod
        return modmemz[n] % mod
    try:
        a = modmemz[n - 1] % mod
    except KeyError:
        modmemz[n - 1] = fib_rec_memz(n - 1) % mod
        a = modmemz[n - 1] % mod
    try:
        b = modmemz[n - 2] % mod
    except KeyError:
        modmemz[n - 2] = fib_rec_memz(n - 2) % mod
        b = modmemz[n - 2] % mod
    modmemz[n] = (a + b) % mod
    return modmemz[n] % mod