5 Ways of Fibonacci in Python – Best way!

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… 🙂

2 thoughts on “5 Ways of Fibonacci in Python – Best way!

  1. 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]

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.