Skip to content

Instantly share code, notes, and snippets.

@Garciat
Last active January 20, 2018 15:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Garciat/29152e909b9024ff119308063c879ca4 to your computer and use it in GitHub Desktop.
Save Garciat/29152e909b9024ff119308063c879ca4 to your computer and use it in GitHub Desktop.
class Vec2(object):
def __init__(self, x, y):
self.x = x
self.y = y
def dot(v, w):
return v.x * w.x + v.y * w.y
class Mat22(object):
def __init__(self, a, b, c, d):
self.a = a
self.b = b
self.c = c
self.d = d
def rows(self):
yield Vec2(self.a, self.b)
yield Vec2(self.c, self.d)
def cols(self):
yield Vec2(self.a, self.c)
yield Vec2(self.b, self.d)
def __mul__(m, n):
return Mat22(*(
dot(v, w)
for w in n.rows()
for v in m.cols()
))
def pow(x, p):
if p == 1:
return x
z = pow(x, p // 2)
y = z * z
if p % 2 == 1:
y *= x
return y
def fib(n):
return pow(Mat22(1, 1, 1, 0), n).b
if __name__ == '__main__':
import sys
print fib(int(sys.argv[1]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment