For appreciating this post, I request you to go through 5 Ways of Fibonacci in Python post of mine, where I have explained 5 different ways by which you could write code for finding nth Fibonacci number. At the end of the post, I had promised you that I would come up with performance measurements for each of these ways and conclude on whats the best way; So, here I am!

When I used all five ways to calculate 15000th Fibonacci number, and calculated the time taken by each of these methods for 10 iterations, this is what I got

Fib(n=15000) |
||||

loops |
recursion |
generators |
memoization |
memoization as decorator |

45 | 87 | 58 | 44 | 43 |

47 | 88 | 58 | 42 | 42 |

51 | 92 | 60 | 44 | 43 |

43 | 87 | 58 | 42 | 43 |

48 | 92 | 61 | 42 | 44 |

45 | 87 | 59 | 43 | 44 |

44 | 85 | 57 | 42 | 44 |

44 | 87 | 62 | 43 | 43 |

48 | 86 | 59 | 42 | 43 |

45 | 91 | 61 | 45 | 45 |

46 |
88.2 |
59.3 |
42.9 |
43.4 (Avg) |

Takeaways:

- Looping technique seems pretty reasonable
- Recursion is hell.. lets consider we need to find fib(5). Now, fib(5) = fib(4) + fib(3) and fib(4) = fib(3) + fib(2) and so on.. Now in this case, fib(3) is calculated twice, which is redundant. Hence the increased time as depicted in the table above.
- Generators help in creating iterators and avoid the issues with recursion, but are slightly heavy as the function is re-entered over and again
- Memoization ensures the calculated numbers like fib(3) in case of recursion and hence are faster
- Decorators adds a slight overhead in terms of program flow switching between decorator to the actual function and hence slightly slower than Memoization without decorators

So the clear winner is Memoization on a function written with a for loop… 🙂

Advertisements

THX

The best (fastest) way is not to use recursion or loops. Example of very goog solution which works fast for big numbers:

from numpy import matrix

def fib(n):

return (matrix(

‘0 1; 1 1’ if n >= 0 else ‘-1 1; 1 0’, object

) ** abs(n))[0, 1]