The Nth Fibonacci Number in O(log N)

It&#x27;s easy to compute things quickly if you pretend that you can do arbitary-precision arithmetic in constant time. Want a quadrillion digits of Pi? Easy, just use the Brent–Salamin AGM algorithm and you&#x27;ll get them in about 500 arithmetic operations. NP-complete problems? No problem at all, rephrase them as subset-sum problems and use the polynomial-integer-operations dynamic programming algorithm. I don&#x27;t <i>think</i> you can solve PSPACE in a polynomial number of integer operations, but I can&#x27;t see how to prove it immediately.<p>In &quot;real&quot; terms, computing the Nth fibonacci number takes O(M(N)) = O(N log N 2^(O(log* N))) operations.

An issue here is that the the nth Fibonacci number has O(N) bits, so once you move into arbitrary arithmetic calculations your +&#x27;s and *&#x27;s will become O(N) and O(N logN) respectively.

Factoring into powers of 2 seems to me like an unnecessary complication. It&#x27;s possible to calculate an arbitrary power in O(log N) time without memoization.<p><pre><code> def __get_matrix_power(self, M, p): if p == 1: return M if p % 2 == 1: # odd power return self.__multiply_matrices(M, self.__get_matrix_power(M, p - 1)) else: # even power K = self.__get_matrix_power(M, int(p&#x2F;2)) return self.__multiply_matrices(K, K)</code></pre>

As mentioned, the actual number has O(N) bits and thus can&#x27;t actually be computed in O(log N) time. So if you just want an approximation, you may as well use Binet&#x27;s formula. [1]<p><i>However</i>, one thing this algorithm can do that Binet&#x27;s formula can&#x27;t is compute the N-th Fibonacci number modulo some constant M in O(log N) time. So you could very efficiently compute, say, the last 12 digits of F_123456789. A lot of programming contests (TopCoder, Google Code Jam, etc.) will ask for the answer modulo some constant to take advantage of this trick.<p>[1] <a href="http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression" rel="nofollow">http:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Fibonacci_number#Closed-form_ex...</a>

I remember there is an equation that could get the Nth fibonacci number directly. (Maybe in the exercises of Concrete Mathematics by Knuth).

I wrote about this last December:<p><a href="http://blog.richardkiss.com/?p=398" rel="nofollow">http:&#x2F;&#x2F;blog.richardkiss.com&#x2F;?p=398</a><p>The matrix math is easier, and the Python code is about a dozen lines.

This brings back some memories. I remember talking about the different ways of calculating the Fibonacci numbers in an old comp.lang.java usenet thread about recursion, memoization and dynamic programming from 2007,<p><a href="http://coding.derkeiler.com/Archive/Java/comp.lang.java.programmer/2007-10/msg01792.html" rel="nofollow">http:&#x2F;&#x2F;coding.derkeiler.com&#x2F;Archive&#x2F;Java&#x2F;comp.lang.java.prog...</a><p>The thread discusses the exponential, linear and logarithmic algorithms.

In Python:<p><pre><code> def fib(n): import math r5 = math.sqrt(5) x = pow((1 + r5) &#x2F; 2, n) x -= pow((1 - r5) &#x2F; 2, n) return x &#x2F; r5 $ python fib.py 4 3.0 $ python fib.py 5 5.0 $ python fib.py 50 12586269025.0 $ python fib.py 5000 OverflowError: (34, &#x27;Result too large&#x27;) </code></pre> So we add arbitrary precision. Uglier, but supports any n:<p><pre><code> def fib(n): from math import sqrt from decimal import Decimal r5 = Decimal(sqrt(5)) x = pow((1 + r5) &#x2F; 2, n) x -= pow((1 - r5) &#x2F; 2, n) return x &#x2F; r5 $ python fib.py 4 3.000000000000000242931577139 $ python fib.py 5 5.000000000000000607328942851 $ python fib.py 50000 1.077773489309106593392984005E+10449 $ python fib.py 50309230 8.147201098193506535089177522E+10514006 </code></pre> Or does it?<p><pre><code> $ python fib.py 50309230390 decimal.Overflow: above Emax </code></pre> This was fun. Computing fib(50309230390) is left as an exercise for the reader.<p>Wolfram alpha verifies this is correct for Fib 50,000: <a href="http://www.wolframalpha.com/input/?i=Fib+50000" rel="nofollow">http:&#x2F;&#x2F;www.wolframalpha.com&#x2F;input&#x2F;?i=Fib+50000</a>