How I calculated the 1,000,000th Fibonacci Number with Python

No, the title is not clickbait at all! A few days ago I really wanted to find the optimal solution to calculating Fibonacci numbers and I wanted to try to calculate the 100,000th number in the sequence, but I thought; if I could calculate the 100,000th, what’s stopping me finding the 1,000,000th? So today, I am going to show you how I went about doing this and all the issues I came across.

The Fibonacci sequence is one of the most well known mathematical sequences and is the most basic example of recurrence relations. Each number in the sequence consists of the sum of the previous two numbers and the starting two numbers are 0 and 1. It goes something like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 and so on forever..

Over the next few minutes, I will go through a few different approaches until I show you the optimal solution:

1. Using simple recursion
2. Using cache with recursion
3. Using an iterative method
4. Using Binet’s formula
5. Calculating the 1,000,000th number

But before we get started, I must say that all the timings mentioned are all based on the hardware I am currently running and the Python version (3.9.1).

Using simple recursion

This is a very simple and easy way to return the nth Fibonacci number in Python:

It uses recursion to repeatedly call itself multiple times calculating the previous number and using it to work out the next. But that is also its downside, as the function extremely inefficient and resource intensive, this is because at every stage it calculates the previous 2 numbers, and the previous 2 numbers of those number etc. Soon you reach a point where it takes too long to calculate the next number, for example on my computer it took me 1.43 seconds to calculate the 35th number. This will obviously be extremely slow, and basically impossible, to calculate higher values.

Using cache with recursion