def dot(p,q):
"""Dot-product of two vectors (represented as equal-length lists).
"""
return sum((i*j for i,j in zip(p,q)), 0)
def matmul(L, R):
"""Multiply two matrices (represented as lists-of-rows).
>>> matmul([[2]], [[3]])
[[6]]
>>> matmul([[1,1],[1,0]], [[0,1],[1,-1]])
[[1, 0], [0, 1]]
"""
return [[dot(Lrow, Rcol) for Rcol in zip(*R)] for Lrow in L]
def fib(n):
"""Calculate the nth Fibonacci number, indexed as f(0)=1, f(1)=0, f(2)=1.
>>> [fib(n) for n in range(18)]
[1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
"""
result = [[1, 0], [0, 1]]
a, b, c = 1, 1, 0
while n:
n, d = divmod(n, 3)
if d == 0:
pass
elif d == 1:
result = matmul(result, [[a,b],[b,c]])
elif d == 2:
n += 1
d = -1
result = matmul(result, [[-c,b],[b,-a]])
abc, ab2, cb2 = b*(a+c), a**2 + b**2, c**2 + b**2
a, b, c = b * abc + a * ab2, a * abc + b * cb2, b * abc + c * cb2
return result[1][1]