3 ms·
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 Bi
by nealwu 12y ago
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]
However, 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.
[1] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
- nhaehnle 12y agoA really neat observation here is that Binet's formula and the matrix exponentiation trick are arguably the same thing. How so? You can think of the operations of Binet's formula as happening in the field Q(sqrt{5}). Since sqrt{5} is a square root, every element of this field has a unique representation of the form a + b sqrt{5} with a and b rational, and so the field can be said to have dimension 2 over the rationals. When you squint at how the field operations work in this representation, you'll find that you end up doing something that looks very similar to the 2x2 matrix multiplications trick; with a bit of rearrangement, it's the same thing - except that the matrix multiplication trick is usually derived via dynamic programming, and Binet's formula is usually derived via power series. The fact that things often fit together so nicely is perhaps the most beautiful aspect of mathematics.