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 na...