It'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'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't <i>think</i> you can solve PSPACE in a polynomial number of integer operations, but I can't see how to prove it immediately.<p>In "real" 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 +'s and *'s will become O(N) and O(N logN) respectively.
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.<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/2))
return self.__multiply_matrices(K, K)</code></pre>
As mentioned, the actual number has O(N) bits and thus can't actually be computed in O(log N) time. So if you just want an approximation, you may as well use Binet's formula. [1]<p><i>However</i>, one thing this algorithm can do that Binet's formula can'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://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...</a>
I wrote about this last December:<p><a href="http://blog.richardkiss.com/?p=398" rel="nofollow">http://blog.richardkiss.com/?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://coding.derkeiler.com/Archive/Java/comp.lang.java.prog...</a><p>The thread discusses the exponential, linear and logarithmic algorithms.