Fast Fibonacci

fib.py

import math
from itertools import product

def fib(n):
    F = [1, 1]
    T = [[0, 1],
         [1, 1]]

    if n == 1:
        return 1

    T = matrixExp(T, n-1)

    res = 0
    for i in range(len(T)):
        res += T[0][i] * F[i]
    return res

def isfib(n):
    phi = 0.5 + 0.5 * math.sqrt(5.0)
    a = phi * n
    return n == 0 or abs(round(a) - a) < 1.0 / n

def matrixMul(m1, m2):
    cols, rows = len(m1[0]), len(m1)
    resRows = xrange(len(m2))
    rMatrix = [[0] * cols for _ in resRows]
    for idx in resRows:
        for j, k in product(xrange(cols), xrange(rows)):
            rMatrix[idx][j] += m2[idx][k] * m1[k][j]
    return rMatrix

def identity(size):
    size = range(size)
    return [[(i == j) * 1 for i in size] for j in size]

def matrixExp(m, pow):
    accumulator = identity(len(m))
    for i in range(pow):
        accumulator = matrixMul(accumulator, m)
    return accumulator