Calculating Fibonacci numbers in Python

Question

While doing Project Euler Problem 25, I came across various techniques to compute the nth Fibonacci number. Memoization seemed to be the fastest amongst them all, and intuitively, I expected memoization to be faster than creating a list from bottom-up.

The code for the two functions is:

def fib3(n): #FASTEST YET
    fibs= [0,1] #list from bottom up
    for i in range(2, n+1):
        fibs.append(fibs[-1]+fibs[-2])
    return fibs[n]

def fib4(n, computed= {0:0, 1:1}): #memoization
    if n not in computed:
        computed[n]= fib4(n-1, computed)+ fib4(n-2, computed)
    return computed[n]
print fib3(1000)
print fib4(1000)

fib3 was approximately 8 times faster than fib4. I am unable to figure out the reason behind this. Essentially both are storing the values as they compute, one in a list, the other in a dictionary so that they can access them as "cached" later. Why the huge difference?

Jeez... who down voted this question??? Take a deep breath and a chill pill! Or at least explain your move. — Julien, Aug 05 '16 at 05:10
The best use of memoization shows up when you repeat the function call a number of times. If you repeatedly call fib3 / fib4, you'll find fib4 will be faster — Asish M., Aug 05 '16 at 05:30
@KlausD. *`Recursion is expensive.`* -- I'm not sure if this sentence correct. For calculating *Fibonacci* numbers, this is probably often true, but I found an interesting [counterexample in python](http://stackoverflow.com/q/38784246/2932052) — Wolf, Aug 05 '16 at 08:06
@Wolf The example in that link does recursion rarely, so the recursion has a minimal impact on the runtime. — Klaus D., Aug 05 '16 at 08:16
@Wolf Well, you got an other answer there why you measurement was not representative. — Klaus D., Aug 05 '16 at 08:21
@KlausD. Well thanks for having a look on it. I by chance stumbled upon your comment when I has this shocking experience yesterday and so I now decided to post it as a question. Thanks for your time :) — Wolf, Aug 05 '16 at 08:39

Julien · Answer 1 · 2016-08-05T05:13:08.270

0

Developing on thesonyman101: my_list[i] gives you immediate access to the element while my_dict[key] requires to compute the hash function and checking for collisions before looking what's in the bucket. Also your memoization sets up some potentially deep recursion stack which has some cost too.

Even faster (provided you don't need to recompute several values, which I know is not the case for Euler problems :) is to only keep track of the last 2 terms. So you don't wast any list management cost.

edited Aug 05 '16 at 05:13

answered Aug 05 '16 at 05:04

Julien

13,986
5
29
53

What will the code look like if I keep track of only the last two terms? – nerd2617 Aug 05 '16 at 05:11
Something like (in the `for` loop) `fib_n, fib_n_minus_1 = fib_n + fib_n_minus_1, fib_n` – Julien Aug 05 '16 at 05:13

Santanu Dey · Answer 2 · 2016-08-05T06:42:48.623

-1

You are using recursion in fib4 function. Which is exponential in terms of time complexity

EDIT after some one said memorize makes fib4 linear: Except it does not.

The memorize thing works to reduce calculation time for repetitive calls only. For the first time the Fibonacci value of a number n is calculated by only recursion.

Try this out yourself

import timeit

setup ='''
def fib3(n): #FASTEST YET
    fibs= [0,1] #list from bottom up
    for i in range(2, n+1):
        fibs.append(fibs[-1]+fibs[-2])
    return fibs[n]

def fib4(n, computed= {0:0, 1:1}): #memoization
    if n not in computed:
        computed[n]= fib4(n-1, computed)+ fib4(n-2, computed)
    return computed[n]

'''

print (min(timeit.Timer('fib3(600)', setup=setup).repeat(3, 1)))

print (min(timeit.Timer('fib4(600)', setup=setup).repeat(3, 1)))

This will show fib4 taking longer.

0.00010111480978441638
0.00039419570581368307
[Finished in 0.1s]

If you change the last two lines, that is repeat each for 100 times, the result changes Now fib4 becomes faster, as if not only no recursion, almost like no additional time to compute at all

print (min(timeit.Timer('fib3(600)', setup=setup).repeat(3, 100)))

print (min(timeit.Timer('fib4(600)', setup=setup).repeat(3, 100)))

Results with 50 repeats

0.00501430622506104
0.00045805769094068097
[Finished in 0.1s]

Results with 100 repeats

0.01583016969421893
0.0006815746388851851
[Finished in 0.2s]

edited Aug 05 '16 at 06:42

answered Aug 05 '16 at 05:16

Santanu Dey

2,900
3
24
38

The memoization makes the recursion take only linear time. – hugomg Aug 05 '16 at 05:35
@hugomg and how would that be without expanded allocation of memory ? – Santanu Dey Aug 05 '16 at 05:36
1

Yes, memoisation is about using some extra memory to reduce the time needed. In OP's case the `computed` dictionary is gonna cost O(n) memory to reduce the runtime of the recursive function from O(2^n) to O(n) – hugomg Aug 05 '16 at 05:45
I read about this but - there are additional costs in still calculating fibs through the whole cycle from n to 1 recursively (except the last part that is memorized). It definitely is still more expensive than a for loop. – Santanu Dey Aug 05 '16 at 05:49
1

Every fib function is gonna have to calculate the whole cycle from 1 to n to calculate fib(n). (unless you use that formula with the golden ratio but that would be a totally different algorithm) – hugomg Aug 05 '16 at 05:52
Incorrect.. I tried to run 1000 with fib 4 and get this error RecursionError: maximum recursion depth exceeded So it is still "recursive" and hence not linear. This is in python 3 – Santanu Dey Aug 05 '16 at 06:07
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/120202/discussion-between-santanu-dey-and-hugomg). – Santanu Dey Aug 05 '16 at 06:40
1

Exactly what i thought. memoization can be faster, but there's a requirement. CACHING or filling up of Look-up table. until that's done, it's just plane old recrusion. SLOW!. – Mridul Kashyap Aug 05 '16 at 06:49

score -2 · Answer 3 · edited May 23 '17 at 12:22

-2

take a look at this stackoverflow question.

as you can see, the complexity of fibonacci algorithm(with recursion) comes out to be approximately O(2^n).

while for the fib3 it'll be O(n).

now you can compute, if your input size is 3, fib3 will have a complexity of O(3) but fib4 will have it O(8).

you can see, why it's slower.

edited May 23 '17 at 12:22

Community

1
1

answered Aug 05 '16 at 05:05

Mridul Kashyap

704
1
5
12

fib4 is also O(n) because of the memoization. If it were exponential he wouldn't have been able to print fib4(1000) to compare it with fib3. – hugomg Aug 05 '16 at 05:47
@hugomg but while we go lower into the the call stack, wouldn't memoization be useless? fib4(1000) will in turn call fib4(999) and fib4(998) but neither of these functions have a value stored in lookup table. memoization will only be useful when we go up the call stack since by then every fn call from fib4(1) would have it's value stored in look up table. won't it? – Mridul Kashyap Aug 05 '16 at 06:15

Calculating Fibonacci numbers in Python

3 Answers3