Skip to content

Instantly share code, notes, and snippets.

@goulu

goulu/fibonacci.py

Last active April 26, 2017 05:20
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 goulu/f56725fa32fbb4840c855a8309662c9d to your computer and use it in GitHub Desktop.
Save goulu/f56725fa32fbb4840c855a8309662c9d to your computer and use it in GitHub Desktop.
Download ZIP
compute fibonacci(n)%m for very large n
Raw
fibonacci.py
from Goulib.math2 import digits, identity
def mod_matmul(A,B, mod=0):
return [[sum(a*b for a,b in zip(A_row,B_col))%mod for B_col in zip(*B)] for A_row in A]
def mod_matpow(M, power, mod=0):
result = identity(2)
for power in digits(power,2,True):
if power:
result = mod_matmul(result, M, mod)
M = mod_matmul(M, M, mod)
return result
def fibonacci(n,mod=0):
return mod_matpow([[1,1],[1,0]],n,mod)[0][1]
print(fibonacci(int(1E19),1000000007)) # gives 647754067
@goulu
Copy link
Author

goulu commented Apr 26, 2017 •
edited

see https://www.drgoulu.com/2017/04/25/comment-calculer-le-1e19-eme-terme-de-la-suite-de-fibonacci/
all functions are available in https://github.com/goulu/Goulib math2 module with better documentation ...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment