Fast Fibonacci
My 6.006 TA mentioned a quick way to calculate the nth Fibonacci number that I thought was really cool! It's more efficient than recursion (exponential), memoization (linear), or looping through/keeping track of the previous two numbers (linear).
The O(log n) method combines matrix multiplication with repeated squaring. It's based on the fact that [[1, 1], [1, 0]][a, b] = [a+b, b].
I wrote three possible methods in Python, which I copied below this post (full code on Github).
When calculating the millionth Fibonacci number, loopfib took 16.5753660202 seconds, and matrixfib took 0.820223808289 seconds, roughly 20x faster.
Side note: Python automatically converts 32-bit ints to bignums, so this code can handle calculating the millionth Fibonacci number.
def matrixfib(n):
a = [[1, 1], [1, 0]]
t = [[1, 0], [0, 1]]
b = [1, 1]
while n > 0:
if n % 2 == 1:
t = dot(t, a)
n /= 2
a = dot(a, a)
return t[1][0]*b[0]+t[1][1]*b[1]
def naive(n):
if n == 0 or n ==1:
return 1
else:
return naive(n-1) + naive(n-2)
def loopfib(n):
prev = 0
curr = 1
res = 1
while n > 0:
res = curr + prev
prev = curr
curr = res
n -= 1
return res
The O(log n) method combines matrix multiplication with repeated squaring. It's based on the fact that [[1, 1], [1, 0]][a, b] = [a+b, b].
I wrote three possible methods in Python, which I copied below this post (full code on Github).
When calculating the millionth Fibonacci number, loopfib took 16.5753660202 seconds, and matrixfib took 0.820223808289 seconds, roughly 20x faster.
Side note: Python automatically converts 32-bit ints to bignums, so this code can handle calculating the millionth Fibonacci number.
def matrixfib(n):
a = [[1, 1], [1, 0]]
t = [[1, 0], [0, 1]]
b = [1, 1]
while n > 0:
if n % 2 == 1:
t = dot(t, a)
n /= 2
a = dot(a, a)
return t[1][0]*b[0]+t[1][1]*b[1]
def naive(n):
if n == 0 or n ==1:
return 1
else:
return naive(n-1) + naive(n-2)
def loopfib(n):
prev = 0
curr = 1
res = 1
while n > 0:
res = curr + prev
prev = curr
curr = res
n -= 1
return res
