Exploring Fibonacci Formula in Python
Let’s explore many different methods and techniques for calculating the Fibonacci Series using Python.
The Fibonacci Series is beautiful, fascinating, mysterious! The series is defined as follows: every number is the sum of the two preceding ones. Simple:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Calculating Fibonacci Iteratively
The simplest way to calculate a Fibonacci number (n) is simply to start at the beginning and work forwards, iteratively. This solution calculates all previous values, giving it an exponential running time — larger numbers take increasingly longer to calculate.
Calculating Fibonacci Recursively
The recursive approach to finding Fibonacci numbers is sometimes used as a teaching aid in computer science classes. You can see here that the function calls itself on line 14 — making it recursive.
This method works backwards from the starting position until it reaches either 1 or 0. Otherwise, it calculates the sum of all previous recursions.
Recursion works because the computer keeps track of where we are using a memory construct known as stack memory. This is limited! Trying to find large Fibonacci numbers would exhaust the stack space.
Also: the recursive algorithm suffers from the same time complexity problem as the iterative algorithm — it must calculate all of the values.
Using Memoization for Efficient Recursion
The previous recursive function is
called repeatedly for some values of
of recalculating this value, we can use a technique known as memoization.
Memoization is simply taking note, or a memorandum, of the previous calculated output values. Then we return the memo instead of re-calculating the value.
Python supports memoization very nicely if we use a decorator function. The decorator wraps the algorithm, and intercepts all calls and all return values. By intercepting the calls and the return values, we can store them in a local cache — and in future use the cached answers.
We can now apply the
memo decorator to our function fibonacci_wrapped
and see a very large speed improvement. Unfortunately, recursion limits still apply.
Python has a built-in memoization
decorator, the least recently used cache
We could save ourselves the trouble of
writing our own (inefficient!) memoization decorator, and instead use the
@functools.lru_cache. Don’t forget to
import functools if you want to use this.
Using Matrix Multiplication to Calculate Fibonacci Numbers
The previous examples all suffered from the same problem: all preceding values in the sequence needed to be calculated. We can avoid this inefficiency by using matrix multiplication to directly compute the sequence’s value without calculating the predecessors.
You can read more about matrix multiplication here:
In mathematics, more specifically linear algebra, matrix multiplication is a binary operation that produces a matrix…en.wikipedia.org
Because the Fibonacci sequence is linear and predictable, it can be efficiently calculated using linear algebra.
This formula requires a constant amount of memory space to complete, and takes linearly longer as the value of n increases.
Using the Golden Ratio to Calculate Fibonacci Numbers
This method is included for the sake of completeness!
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the…en.wikipedia.org
The Fibonacci Sequence represents the golden ration perfectly, so we can use Binet’s formula to calculate it:
You can see that I’m cheating here. If the sequence number we’re searching for is higher than 71, this function silently cheats and instead uses the matrix multiplication method.
The Binet formula is precise algebra. However, computers must use an imprecise representation of floating-point numbers. As the values of n increase, the rounding errors also accumulate.
Using Bit Operations to Calculate Fibonacci
In an early article, I described some common formulae for performing bit arithmetic on integers. My long-time subscribers may have been wondering why, but now all is revealed!
It is important to have an understanding of binary arithmetic before we explore the following ways of calculating Fibonacci numbers.
Some reusable python recipes for manipulating bits to perform fast arithmetic.levelup.gitconnected.com
The Lucas Sequence
In this treatment of Fibonacci numbers, I’d like to also show the Lucas Sequence. Like Fibonacci, Lucas numbers are the sum of their two predecessors — they just begin at a different place:
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ....
The Lucas numbers are therefore very closely related to Fibonacci numbers:
Let’s work with this with
F(n-1) = F(5) = 3
F(n+1) = F(7) = 8
F(n-1) + F(n+1) = (3 + 8) = 11
L(6) = 11
Calculating Fibonacci Numbers with the Djikstra Formula
Edsgar Djikstra was perhaps the most brilliant theoretical computer science in modern history. He proposed an algorithm which uses the powers of the Lucas numbers to derive the related Fibonacci number.
Really quite brilliant. Here is the full algorithm:
fibonacci_djikstra recognisably uses the
relationship between Lucas numbers and Fibonacci numbers I showed earlier:
L(n) = F(n-1) + F(n+1).
It goes a step further, and uses the Lucas power function to exploit a part of Binet’s formula — see the integer 5 in there, and do you recognise that from the Golden Ration discussion?
For a more in-depth discussion of Djikstra’s algorithm, feel free to refer to this information.
Karatsuba Fast Multiplication
Following on from our discussion of binary arithmetic, there is one really interesting way to calculate very large products — Karatsuba multiplication.
According to Wikipedia, the Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic “grade school” algorithm, it offers a speedup of 17.75 times versus the traditional quadratic formula for sufficiently large values.
We’ll use this algorithm in our next and final formula for calculating Fibonacci numbers!
Recursive Fast Doubling to Calculate Fibonacci
The following fast doubling formula uses four tools explained earlier: recursion, memoization, binary arithmetic and Karatsuba multiplication. You can guess why I chose to put this formula last!
This formula is very fast. It calculates Fibonacci to the 80'000 place in microseconds on my MacBook Pro.
I’ll explain how this works using the iterative variant, next.
Iterative Fast Doubling to Calculate Fibonacci
We can easily change the forms of an algorithm: from recursive to iterative or iterative to recursive. See how the following, iterative version of the previous differs:
It contains two loops. The first successively halves the sequence number we’re looking for. The second successively doubles it on the way back up. The iterative version is obviously slower but avoids overflowing the stack.
This algorithm uses an important property identified by number theorists: the “halving property”. It also vastly simplifies the matrix multiplication method by exploiting the formula:
There are a lot of squares being calculated, which is where the Karatsuba multiplication is useful.
I thought you might be interested in the timing results. I decided to compare the matrix multiplication algorithm, the fast doubling algorithm, and the Djikstra algorithm. It’s pretty clear that the golden ratio, and the naive iterative and recursive algorithms will be slower.
Here is the code to collect the timing data:
And here is a graph of the timing results:
I hope you enjoyed this article! I’d like to invite you to follow me so that you can be notified when I publish the next article!