# Fun with Fibonacci

Just read an interesting blog post about comparing Python and Haskell code to calculate the Fibonacci sequence. I wrote a faster version, just for the hell of it. I realise that it is not a fair comparison any more, and doesn't prove anything, but it does demonstrate a useful optimization technique. Here's the code...

```from time import time

def memoize(f):
f._cache = {}
def do_f(n):
if n in f._cache:
return f._cache[n]
r = f(n)
f._cache[n] = r
return r
return do_f

@memoize
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)

if __name__ == "__main__":
start_time = time()
for i in range(36):
print "n=%d => %d" % (i, fib(i))

print "Time elapsed: %f" % (time() - start_time)
```

When I run it on my machine, it claims to take 0.00000 seconds. Damn, thats fast!

Use Markdown for formatting
```*Italic* **Bold** `inline code`

> This is a quote
>

```python
import this
```
```
your comment will be previewed here Magnus

Memoization is indeed a good (time) optimisation technique. It might be worth pointing out that you've sacrificed memory for time by doing it though.

Nice use of Python decorators! filox

Nice, but the point was in measuring the speed of languages, without changing the naive algorithm... Paul

@filox : If you use the naive algorithm, you're going to see languages win that are written naively. If you want a _real_ language comparison, I think you need to use the best way to do it in either language. Bob

You must be using some form of Windows OS. Python time.time() resolution on Windows XP is around 15 milliseconds. So you have shown that your algorithm runs in less than about 15 ms on your machine. Try it again using time.clock(). Python time.clock() on my Windows XP box has about 2 microsecond resolution. Bob

I just took my own advice that I just gave you. I ran on WIndows XP with time.time() and I also got 0 seconds. When I ran using time.clock() I got about 3 milliseconds. billg

should be even faster with xrange instead of range (unless you're using python3000). of course, you probably won't be able to measure the speedup. JeffH

For comparison, running the code without the memoize decorator I get
Time elapsed: 43.063779

Running Will's memoized version knocks it down to
Time elapsed: 0.001341

Using shedskin, http://mark.dufour.googlepages.com/, on the non-memoized version runs in
Time elapsed: 0.782071
(remember, I'm not trading memory for speed)

Making a shared library out of fib with shedskin, then importing it and using it results in:
Time elapsed: 1.242797

You really need to check out shedskin -- c++ speeds, python code to maintain filox

First, you have an error in the program - it says fib(2) = 1, which is wrong. Your whole sequence is one step behind. and since we're making fast algorithms, here's one even faster (doesn't spend as much memory either):

from time import clock
temp = []
temp.append(1)
temp.append(1)

def fib(n):
global temp
if n %d" % (i, fib(i))

print "Time elapsed: %f" % (clock() - start) filox

well, this didn't turn out as I'd hoped... for some reason, my python code was mangled :( Bob

You could try something like this.

import time

def fib(n): # write Fibonacci series up to n
"""Print a Fibonacci series up to n."""
a, b = 0, 1
for i in range(n):
#print b
a, b = b, a+b

startTime = time.clock()

fib(36)

print 'elapsed time: ', (time.clock() - startTime) eric casteleijn

the first 2 lines of fib should read:

if n == 0 or n == 1:
return 1 JeffH

Here is a non-recursive version
`def fib(n): prev = -1 result = 1 for i in xrange(n+1): sum = result + prev prev = result result = sum return result`
Time elapsed: 0.000813 Hugo

If you're generating the sequence in order anyway, there is no point in memoization. You're sacrificing a lot of space to save all these results, when all you really need is the result of the last two calls. Using a function like Bob's is more space-efficient, and should run at least as fast (probably slightly faster because the cache lookups take some small amount of time).

I'd write a generator for this myself:

def gen_fib(n):
a, b = 0, 1
for dummy in range(n):
yield b
a, b = b, a + b

This is probably the fastest way to generate the sequence in order. If you need fast access to random elements from the sequence, the closed-form solution is probably faster since it does not have to generate the entire sequence for each call:

sqrt5 = math.sqrt(5)
phi = (1 + sqrt5) / 2
def fib(n):
"""return the nth element from the sequence"""
return round(phi**n / sqrt5)

it pre-computes the phi and sqrt(5) calls. The algorithm is most likely O(n) because I think the ** operation is. But this is done in C and should be very fast. Like I said, generating the sequence in order is probably faster using the generator since it doesn't involve a division and power operation.

Disclaimer: none of this has been timed, I may be wrong in performance assumptions. zonedabone
Here's some food for thought! Simpler is better!
``` def fib(n):
st=time.clock()
a,b=1,1
for i in range(n-2):
c=a+b
a=b
b=c
print(time.clock()-st)
```
got around 1.5E-5 or .000015 seconds or 0.015 milliseconds. That's the best time I've seen here and much simpler.

Note:I disregarded the article's time since it was proven to be 3 milliseconds in actuality.