Fibonacci series and Dynamic programming

I really liked the haskell version when I first learned about it in a programming languages course, I believe I've never been more surprised than after seeing the output of 'take 10 fibs' without knowing how did that single line worked.

Correct me if I'm wrong, but this is also O(n) in space, right? I think you can get a similar scala version in:

    lazy val fib:Stream[BigInt] = 0 #::1 #:: fib.zip(fib.tail).map(x=>x._1+x._2)

This is neat and all, but the imperative version wins by being O(1) in space. Right?

Here is the Fibonacci sequence calculated by a literal series of mechanical steps: http://www.chrisfenton.com/the-turbo-entabulator/

Edit:

Doh - I'm a moron! You're using a recurrence relation, which has the nice property of never computing the same sub-solution twice. I'll leave this here as a reminder to think before I nitpick next time.

Original:

Apologies to nitpick, but your iterative python solution isn't DP. DP hinges on the idea of never computing the answer to the same problem twice. For it to be DP, it would need to memoize subproblem solutions and refer to the solution cache rather than recompute the solution to every subproblem in the tree every time.

This solution fits the bill, although it can probably be written a bit more elegantly:

  fibs = {0: 1, 1: 1}
  def fib(n):
      global fibs
      stack = []
      for a in xrange(n,0,-1):
          if a in fibs:
              stack.reverse()
              for item in stack:
                  fibs[item] = fibs[a] + fibs[a-1]
                  a = item
              break
          else:
              stack.append(a)
      return fibs[n]

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.

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

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

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

And, if you want to know more about generating functions, you can check out the book "generatingfunctionology" by the recently late Herbert Wilf gratis at http://www.math.upenn.edu/~wilf/DownldGF.html

Another math-y option is to note that the Fibonacci series satisfies the linear recurrence F[n+2] = F[n+1] + F[n] and can therefore be represented in matrix form. Here's a (trimmed down) Maxima session that gives the details:

    $ maxima
    (%i3) load(eigen)$
    (%i4) A: matrix([1, 1], [1, 0])$
    (%i5) b: columnvector([1, 0])$
    (%i6) fib(n) := (''A^^n . ''b)[2][1];

                              <n>
                      [ 1  1 ]      [ 1 ]
    (%o6) fib(n) := (([      ]    . [   ]) )
                      [ 1  0 ]      [ 0 ]
                                          2
                                            1

    (%i7) makelist(fib(n), n, 10);

    (%o7) [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Since the transition matrix A is symmetric, it can be diagonalized using its eigenvector matrix:

    (%i8) similaritytransform(A)$
    (%i9) Adiag: expand(leftmatrix . A . rightmatrix)$

And the n-th power of a diagonal matrix is the same as raising the values on its diagonal to the n-th power:

    (%i10) AdiagN(n) := matrix([''(Adiag[1][1])^n, 0], [0, ''(Adiag[2][2])^n]);

And thus raising A to the n-th power is the same as raising its diagonal counterpart Adiag to that power and then reversing the diagonalization transform (since leftmatrix and rightmatrix are inverses and cancel out for the interior multiplications):

    (%i11) fibdiag(n) := expand(rightmatrix . AdiagN(n) . leftmatrix . b)[2][1]$

Finally, this leads to a closed-form representation for the n-th Fibonacci number:

    (%i12) fibdiag(n);

            sqrt(5)   1 n    1   sqrt(5) n
           (------- + -)    (- - -------)
               2      2      2      2
    (%o12) -------------- - --------------
              sqrt(5)          sqrt(5)