Fast Computation of Fibonacci Numbers: Part II

Additional notes, and insights on computing Fibonacci numbers

Fibonacci numbers seem to be very popular, the last article on efficient methods for computing Fibonacci numbers performed beyond my expectations, it trended on the front page of Hacker News and also on X/Twitter. There was a ton of discussion around it, which surfaced up additional details and resources. I decided to collect all of the interesting discussions, and notes and distil them in this post for you. If you enjoyed the previous article, I am sure you will find these additional details worth your time.

Here’s the list of topics that we are going to cover:

• An elegant and short proof of the closed form expression using matrix diagnlozation

• A trick for exact computation of Fibonacci numbers using the closed form expression without resorting to floating points

• An interesting historical note on the exponentiation by repeated squaring algorithm which changed how cryptographic algorithms compute powers

• Other interesting articles related to Fibonacci numbers computation

  • A programming language interpreter using fast matrix exponentiation technique

  • Using monoids to compute quickly compute Fibonacci numbers in Haskell

  • A visually illustrated article on fast computation of Fibonacci numbers

• Some notes on the implementation of Fibonacci numbers, specifically how to handle large numbers and how it impacts performance

Photo by Daniele Levis Pelusi on Unsplash

---

Exact Computation using the Golden Ratio Based Formula

In the previous article we saw the following closed form formula for computing the nth Fibonacci number using the golden ratio:

\(\begin{align*} &F(n) = \frac{1}{\sqrt{5}} \left(\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right) \\ &\text{Or, } F(n) = \frac{1}{\sqrt{5}} (\varphi^n - \psi^n) \\ &\text{Where }\varphi \text{ and } \psi \text{ are golden ratio values} \\ &\text{Also, note that }\psi = -\varphi^{-1} \end{align*} \)

This formula for computing the nth Fibonacci number is neat but as it involves irrational numbers, implementing and using it is not very practical because we cannot represent irrational numbers exactly. We would have to use floating point data types which have limited precision, and each arithmetic operation on them would lead to accumulation of small errors which may eventually lead to incorrect results.

However, there is a trick to get around this problem. Just like we represent complex numbers with two parts (e.g. 1 + 2i), we can represent such irrational numbers using two parts, e.g. a + bφ, where a, and b are integers.

Let’s phrase it more mathematically. ℚ is the set of all rational numbers, and we can define a set ℚ(φ) which is the set of all rational numbers of the form a + bφ. It turns out that the set ℚ(φ) forms a ring.

If you don’t remember what a ring is, don’t worry. Without getting too technical, a ring is an algebraic structure defined on a set, such that it is closed for addition and multiplication. This means when adding (or multiplying) two values from ℚ(φ), the result also lies in ℚ(φ). This is called the property of closure. In addition to closure, rings also have few other properties, but we won’t go there.

Now, we can transform the closed form expression for Fibonacci numbers in a form suitable for computation within this ring.

\(\begin{align*} &F(n) = \frac{1}{\sqrt{5}} (\varphi^{n} + \psi^{n}) \\ &\text{It is known that }\psi = -\varphi^{-1} \\ &\text{And, from the value of }\varphi = \frac{1 + \sqrt{5}}{2} \\ &\text{we can find the value of }\sqrt{5} \text{ as} \\ &\sqrt{5} = -1 + 2\varphi \\ \\ &\therefore F(n) = (-1 + 2\varphi)^{-1} (\varphi^n + (-\varphi)^{-n}) \\ \\ & \text{If you notice, all the components of this expression are of the form } a + b\varphi \text{,} \\ &\text{which can be computed by doing arithmetic on the ring } {Q}(\varphi) \end{align*}\)

Although, this may seem very abstract but it can be implemented in code very neatly. The following is a partial Python implementation of ℚ(φ).

from fractions import Fraction

class PhiRational:
    PHI = 1.61803398875

    def __init__(self, a, b = 0):
        if isinstance(a, PhiRational):
            self.a = a.a
            self.b = a.b
        else:
            self.a = Fraction(a)
            self.b = Fraction(b)

    def __int__(self):
        if self.b == 0:
            return int(self.a)
        else:
            return int(self.a + self.b * PhiRational.PHI)

    def __add__(self, other):
        other = PhiRational(other)

        return PhiRational(self.a + other.a, self.b + other.b)

    def __mul__(self, other):
        other = PhiRational(other)

        a, b = self.a, self.b
        c, d = other.a, other.b

        return PhiRational(a*c + b*d, a*d + b*c + b*d)

    def __pow__(self, n):
        # Compute power by repeated squaring and multiplications
        # in log2(n) time.
        base   = PhiRational(self.a, self.b)
        result = PhiRational(1, 0)

        while n != 0:
            if n % 2 == 1:
                result *= base
                n -= 1

            base *= base
            n //= 2

        return result

    def __repr__(self):
        return f'({self.a} + {self.b}φ)'

As you can see, all the arithmetic operations such as add, multiply, and power on this ring are being done without involving the actual floating point value of φ. This means that we can compute the nth Fibonacci number without any loss of precision using this technique.

Just for completion, our expression for the nth Fibonacci in terms of ℚ(φ)can be computed using the above code as:

int((PhiRational(0,1)**n - PhiRational(1,-1)**n) / PhiRational(-1, 2))

The above code is taken from this Github repo, which also contains the equivalent Ruby implementation of various Fibonacci number algorithms as well.

---