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

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]