In "real" terms, computing the Nth fibonacci number takes O(M(N)) = O(N log N 2^(O(log* N))) operations.

For example, the nth Fibonacci number has n log_2 \phi bits, which means that to simply list the digits in the nth number, it takes O(n) time.

So from there it's pretty easy to see that actually this algorithm can't "really" operate in O(log n), or at least, something must be up that causes us to produce that analysis.

Another bit of intuition that might help you see where this bound comes from: what's actually true is that it takes O(log n) _matrix multiplications_ to get the result. So if you see that and you see that listing the digits of the nth number of the sequence is O(n), it starts to point at the fact that there's a hidden cost to the multiplications.

[1] http://web.engr.illinois.edu/~jeffe/teaching/algorithms/note...

Having said that, doing it once in the past in an undergrad class and remembering it 10 years later when a relevant article on some website is posted are two different things.

https://news.ycombinator.com/item?id=35076

Basically, take a list of integers, and for each element n create a thread that sleeps n seconds, after which it appends n to the result list.

Assuming the original list is dense (there are no gaps between integers), we can sort it in O(n)!

:)

  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)

  def fib(n):
    def fib2(n):
      # returns (f_n, f_(n+1))
      if n == 0:
        return 0, 1
      if n % 2:
        a, b = fib2(n-1)
        return b, a+b
      a, b = fib2(n//2)
      return b*a + a*(b-a), a*a + b*b
    return fib2(n)[0]

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

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.

If ever there was a way to impress an interviewer it is to bust out this baby when asked to make a fibonacci function.

Don't get me wrong, it'd still be impressive "Woah, he memorized this!" but seeing someone do the matrix trick would be even more impressive, to me.

Now, if you derived the formula on the board from the matrix, that'd be incredibly impressive. The idea here is how the person's brain thinks. When I see them write an equation on the board, I think "Oh, they memorized it" when I see them step through the process of creating a matrix and doing matrix multiplication, I think "Wow, they /really/ know their stuff". If they just threw up the matrix and couldn't explain it, I wouldn't be as impressed. Same as if they wrote the equation and couldn't explain it.

At the end of the day, if they could explain either approach, I'd be impressed, I think the matrix form just lends itself to more likely be in a way that the person can explain it

  X = P^(-1) D P

  X^n = (P^(-1) D P)^n = P^(-1) D^n P

http://blog.richardkiss.com/?p=398

The matrix math is easier, and the Python code is about a dozen lines.

http://coding.derkeiler.com/Archive/Java/comp.lang.java.prog...

The thread discusses the exponential, linear and logarithmic algorithms.

    def fib(n):
        import math
        r5 = math.sqrt(5)
        x = pow((1 + r5) / 2, n)
        x -= pow((1 - r5) / 2, n)
        return x / 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, 'Result too large')

    def fib(n):
        from math import sqrt
        from decimal import Decimal
        r5 = Decimal(sqrt(5))
        x = pow((1 + r5) / 2, n)
        x -= pow((1 - r5) / 2, n)
        return x / 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

  $ python fib.py 50309230390
  decimal.Overflow: above Emax

Wolfram alpha verifies this is correct for Fib 50,000: http://www.wolframalpha.com/input/?i=Fib+50000

The formula came from section 17.3.2, which goes into detail about how to derive it.