4 ms·
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
by blt 13y ago
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 13y agoYour 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 http://en.wikipedia.org/wiki/Exponentiation_by_squaring.
- nicolasp 13y agoThe 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 13y agoThe 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_chain_multiplication http://en.wikipedia.org/wiki/Dynamic_programming#Matrix_chai...).
- d0mine 13y agoHere'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-number-in-sublinear-time/1526036#1526036 http://stackoverflow.com/questions/1525521/nth-fibonacci-num... It is ~20 times faster for n=10000
- blt 13y agoCool - did not know about that. Wish I could edit my comment.
- mjhea0 13y agoYes - 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 https://gist.github.com/mjhea0/5798178