Skip to content

Instantly share code, notes, and snippets.

@Lyken17
Created February 26, 2016 20:51
Show Gist options
  • Save Lyken17/b69dacaa98022ea17b2f to your computer and use it in GitHub Desktop.
Save Lyken17/b69dacaa98022ea17b2f to your computer and use it in GitHub Desktop.
import numpy as np
def fibonacci(n):
def fast_mod(base, exp, mod):
base = base % mod
res = 1
while exp > 0:
if exp & 1:
res = (res * base) % mod
base = base * base % mod
exp >>= 1
return res
base = np.matrix([[0, 1], [1, 1]])
return (fast_mod(base ,n, 1000000) * np.matrix([[1, 0], [0, 1]]))[0, 1]
for i in xrange(10):
print fibonacci(i+1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment