[blt]

The fastest way to calculate the Fibonacci sequence (with integer math) is a simple loop, just like you'd do it on paper. This version is slower and much more complicated. With so many relevant good examples of recursion and dynamic programming, it boggles my mind to see the Fibonacci sequence used as an example for either.

    def fib(n):
        a, b = 0, 1
        for k in range(n):
            a, b = b, a + b
        return a

[cousin_it]

Your method computes fib(n) in O(n) arithmetic operations. There's a way to do it in O(log n) arithmetic operations on integers of the same size. First note that you can obtain the two-element vector (fib(n),fib(n+1)) by applying the matrix A=((0,1),(1,1)) to the vector (fib(n-1),fib(n)). So to get from (fib(0),fib(1)) to (fib(n),fib(n+1)), you need to raise the matrix A to the nth power. That can be done in O(log n) arithmetic operations by using repeated squaring: http://en.wikipedia.org/wiki/Exponentiation_by_squaring.

[d0mine]

Here's O(log n) solution [1]:

  def fib_sicp(n):
      a, b, p, q = 1, 0, 0, 1
      while n > 0:
          if n % 2 == 0: # even
              oldp = p
              p = p*p + q*q
              q = 2*oldp*q + q*q
              n //= 2
          else:
              olda = a
              a = b*q + a*q + a*p
              b = b*p + olda*q
              n -= 1
      return b
  

[1]: http://stackoverflow.com/questions/1525521/nth-fibonacci-num...

It is ~20 times faster for n=10000

[blt]

Cool - did not know about that. Wish I could edit my comment.

[nicolasp]

The Fibonnacci sequence is (IMO) one of the easiest to understand examples of dynamic programming, so it makes for a good introduction to the concept. Furthermore, the dynamic programming implementation is better if you're going to call it multiple times (depending on the context of course -- if you want the first n number the linear version can be adapted to be even better).

[blt]

The looping version could keep a static array around to eliminate that difference. I think Fibonacci is a bad example because the student will wonder why they are going to the trouble of dynamic programming when it doesn't save any work. A better example would be the recursive computation of N choose K - because it avoids overflow from computing the factorial-based formula directly - or matrix chain multiplication (http://en.wikipedia.org/wiki/Dynamic_programming#Matrix_chai...).

[mjhea0]

Yes - an iterative loop is much faster, because with recursion you have to calculate a number of trivial fibonacci numbers.

https://gist.github.com/mjhea0/5798178