Faster Fibonacci

TL;DR You can compute the n-th term of a fibonacci sequence using the lesser-known but very interesting, Binet's Formula. It goes by this -

The n-th term in a Fibonacci Sequence F(n) can be expressed as,

$F(n) = \lfloor{ \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n+1} - (\frac{1 - \sqrt{5}}{2}) ^ {n+1}}{\sqrt{5}} }\rfloor$

Here is an implementation of this formula in Python to find the n-th fibonacci number in O(1) time with no extra space or pre-computed values.

import math

def fibo(n):
    return math.floor((math.pow((1 + math.sqrt(5))/2, n+1) - math.pow((1 - math.sqrt(5))/2, n+1))/math.sqrt(5))

The origins of the Fibonacci Sequence

Fibonacci was not the first one to come up with the Fibonacci Series and infact, he never claimed he did either. Leonardo Bonacci (born c. 1170) was the son of an Italian customs official Guglielmo Bonacci. He only became popularly known as Fibonacci long after his death when in 1838, Franco-Italian historian Guillaume Libri decided Leonardo was an awefully overused name and decided to just record him as fillius Bonacci (a.k.a the "son" of Bonacci). There was never any doubt that Leonardo was a very talented mathematician. However, his most notable contributions were not so much mathematical formulations but rather a historical account of the mathematical wonders he discovered on his travel accross the Mediterranean. He found that the Hindu-Arabic Numerals were far superior to the Roman Numeral System (they didn't even have a zero back then?) that was prevalent in Europe at the time. In his book, Liber Abaci he introduced the famous Fibonacci Series to solve a theoretical problem involving Rabbits (which we will discuss later) as an example of what can be achieved using the Indo-Arabic Number System. The Sequence, however, was described as early as 200 B.C. by Indian poet Acharya Pingala on enumerating possible patterns of Sanskrit poetry formed from syllables of two lengths. He called the sequence by the name mātrāmeru.

Fibonacci's Incestuous Rabbits

Sorry for the shocking title 😅. So Fibonacci described the Sequence as a solution the following problem -

Image there are 2 rabbits on a field - one male and one female.

1. A pair consists of one male and one female rabbit.

2. At the end of each month, a pair mates. The babies are not born for another one month (gestation period).

3. The babies are born at the end of the following month and also always consist of a pair - one male and one female - who may reproduce from the next month onwards.

Ignoring the horrid conditions under which these ignorant or vile (could be either) rabbits are reproducing, we can conclude the following pattern -

1. Let's call the first pair of rabbits Pair 1.

2. At the start (let's call it end of month 0), there's only Pair 1.

3. At the end of month 1, Pair 1 mates but there's no newborns. Now there are 1 pair(s) of rabbits.

4. At the end of month 2, Pair 1 produces Pair 2 and mates again. Now there are 2 pair(s) of rabbits.

5. At the end of month 3, Pair 1 produces another pair - let's call that Pair 3 - and mates yet again (by God are mommy and daddy busy!) and Pair 2 mates for the first time. Now there are 3 pair(s) of rabbits.

6. At the end of month 4, Pair 1 produces yet another pair named Pair 4 while Pair 2 also produces their first pair named Pair 5 and in other news, Pair 3 just mated (no babies yet). So now there are 5 pair(s) of rabbits on the field.

I assume you already see the pattern here. Under these conditions, the number of rabbits on the field at the end of month n can be described as -

$F_n = F_{n-1} + F_{n-2}$

which is, as you know, the famous Fibonacci Sequence.

Pingala's Syllables

Let's try again with a less * ahem * graphic example. In the Sanskrit Prosody, there are 2 types of syllables distinguished by the duration it takes to utter the sounds -

1. The Long (L) syllable takes 2 units of time to speak

2. The Short (S) syllable takes 1 unit of time to speak

The question that Acharya Pingala asked is "How many was are there of composing an n-unit prosody using the Long (L) and Short (S) syllables?"

Let's work out a couple of these scenarios.

1. When n = 1, we have only 1 choice i.e., to use a single short syllable (S).

2. When n = 2, we can either go for (SS) or (L).

3. When n = 3, we can go for (SSS), (SL), (LS).

4. When n = 4, we can go for (SSSS), (SSL), (SLS), (LSS), (LL).

Already we see the fibonacci sequence emerge as the number of ways to compose an n-unit prosody using the Long and Short syllables which can be described as -

$F_n = F_{n-1} + F_{n-2}$

This was first described by Pingala in 200 B.C. in his formulation of the solution titled misrau cha.

Gold-bonacci (Fibonacci and the Golden Ratio)

We have seen how we can describe the Fibonacci Sequence as a relation between it's consecutive terms. But let us explore this idea further and see if we can come up with some sort of statistic that enables us to make more interesting conclusions about the Fibonacci numbers. In the table below I have listed out the n-th fibonacci number $F_n$ and it's ratio with the previous number $F_{n-1}$ for n=1,2,...10.

You might be able to see that the value of the ratio seems to be converging towards a certain number between 1.61 and 1.62. We will not go into the rigorous mathematical details to prove it in this post since it is written by me who is by no means a reliable source for mathematical proofs (I'd much rather leave it to the pros - links towards the bottom of the article). But for those of you who are still unconvinced, we can observe a plot of the ratio $\frac{F_n}{F_{n-1}}$ for n=1 to 500 (that seems reasonable I hope). Convinced yet?

In fact, it turns out that if we take the limit of this ratio to infinity, it equates to the Golden Ratio.

$\lim_{n \to \infty}\frac{F_n}{F_{n-1}} = \varphi$

FACTBYTE

The Golden ratio is the ratio of two terms $t_1$ and $t_2$ such that,

$\frac{\max(t_1,t2)}{\min(t_1,t_2)} = \frac{t_1+t_2}{\max(t_1,t_2)}$ and is denoted as $\varphi$.

Let us suppose $t_2 \gt t_1$. Then,

$\varphi = \frac{t_2}{t_1} = \frac{t_1+t_2}{t_2} \implies \frac{t_2}{t_1} = \frac{t_1}{t_2}+\frac{t_2}{t_2} \implies \frac{t_2}{t_1} = \frac{t_1}{t_2}+1 \implies \frac{t_2}{t_1} = 1 + \frac{1}{\frac{t_1}{t_2}}$

Substituting $\frac{t_2}{t_1}$ with $\varphi$,

$\varphi = 1+\frac{1}{\varphi} \implies \varphi^2-\varphi-1 = 0 \implies \varphi = \frac{1 + \sqrt{5}}{2},\frac{1 - \sqrt{5}}{2}$

If we label $\frac{1 + \sqrt{5}}{2}$ as $\varphi$ then $\frac{1 - \sqrt{5}}{2}$ becomes $\frac{1}{\varphi}$ and vice-versa. We will use the former notation in this article.

The interesting property of the 2 solutions to $\varphi$ is that,

$\frac{\varphi - \frac{1}{\varphi}}{\sqrt{5}} = \frac{\frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2}}{\sqrt{5}} = 1$

And also,

$\frac{\varphi ^ 2 - \frac{1}{\varphi} ^ 2}{\sqrt{5}} = \frac{(\frac{1 + \sqrt{5}}{2}) ^ 2 - (\frac{1 - \sqrt{5}}{2}) ^ 2}{\sqrt{5}} = 2$

And also,

$\frac{\varphi ^ 3 - \frac{1}{\varphi} ^ 3}{\sqrt{5}} = \frac{(\frac{1 + \sqrt{5}}{2}) ^ 3 - (\frac{1 - \sqrt{5}}{2}) ^ 3}{\sqrt{5}} = 3$

And also,

$\frac{\varphi ^ 4 - \frac{1}{\varphi} ^ 4}{\sqrt{5}} = \frac{(\frac{1 + \sqrt{5}}{2}) ^ 4 - (\frac{1 - \sqrt{5}}{2}) ^ 4}{\sqrt{5}} = 5$

And also I'm dragging it on for too long because we can clearly observe the pattern here. It can be proved (again, not gonna do it here - links at the bottom of the article) that,

$F_{n} \ge \frac{\varphi ^ {n+1} - \frac{1}{\varphi} ^ {n+1}}{\sqrt{5}} = \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n+1} - (\frac{1 - \sqrt{5}}{2}) ^ {n+1}}{\sqrt{5}} \gt F_{n-1}$

which means,

$F_{n} = \lfloor{ \frac{(\frac{1 + \sqrt{5}}{2}) ^ {n+1} - (\frac{1 - \sqrt{5}}{2}) ^ {n+1}}{\sqrt{5}} }\rfloor$

where $F_n$ is the n-th Fibonacci number (starting from n=0, since we are computer-folks 😁). This formula is also know as Binet's Formula.

What did it cost?

Everything. It cost everything less than if we computed it by recursion or any other such method. Recall that for the recursive solution to Fibonacci, the program needs to maintain a stack of the recursive calls in memory which not only consumes space but also takes time (to copy values to the stack). On the other hand, using Binet's Formula, we can compute the same number in constant time O(1) and the implementation should be pretty straightforward in any language supporting basic maths.

References for N.E.R.D.S

Golden ratio - Wikipedia

Fibonacci number - Wikipedia

The "Fibonacci" Sequence Was Actually Discovered In India 1000 Years Earlier - YouTube

A Proof of Binet's Formula (milefoot.com)