4 ms·
The O(log N) algorithm, in Python: def fib(n): a,b,x,y = 0,1,0,1 while n != 0: if n % 2 == 0: a,b = a * a + b * b, 2 * a * b + b * b
by ChristianMarks 13y ago
The O(log N) algorithm, in Python:
def fib(n):
a,b,x,y = 0,1,0,1
while n != 0:
if n % 2 == 0:
a,b = a * a + b * b, 2 * a * b + b * b
n = n // 2
else:
x,y = a * x + b * y, b * x + a * y + b * y
n -= 1
return x