codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
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]
Private
[
?
]
Run code
Submit