Skip to content

Instantly share code, notes, and snippets.

@Keirua

Keirua/fib_log.py

Created Apr 13, 2020
Embed
What would you like to do?
fibonacci with O(log(n)) complexity
#
from decimal import *
def fib(n):
return fib_iter(1,0,0,1,Decimal(n))
def fib_iter(a,b,p,q,n):
nb_iter = 0
while n != 0:
#print(a,b,p,q,n)
if n%2 == 0:
p,q = p*p+q*q, (2*p*q)+q*q
n = int(n/2)
else:
a,b = (b*q+a*q+a*p), (b*p+a*q)
n = n-1
nb_iter = nb_iter+1
print(n)
return b
n = 30000000
fN = fib(Decimal(str(n)))
print("fib({})".format(n))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.