Re:The Nth Fibonacci Number in O(log N)
by isani on Wednesday December 17, 2014 @02:59AM
(#8761523)
Factoring into powers of 2 seems to me like an unnecessary complication. It's possible to calculate an arbitrary power in O(log N) time without memoization.
[ Parent
| on HN ]
Also working on pairs of consecutive fibonacci numbers (f_n, f_(n+1)) instead of the matrix [[f_(n+1) f_n] [f_n f_(n-1)]] makes this much simpler.
def fib(n):
def fib2(n):
# returns (f_n, f_(n+1))
if n == 0:
return 0, 1
if n % 2:
a, b = fib2(n-1)
return b, a+b
a, b = fib2(n//2)
return b*a + a*(b-a), a*a + b*b
return fib2(n)[0]