Computing the 10,000th Fibonacci number in less than a second. Unveiling the Secrets of Giant Numbers: Building Your Own BigInt

In this exciting journey, we explore the evolution of Fibonacci calculations, from the inefficiency of traditional recursion to the powerful domain of matrix multiplication and optimized algorithms. Ready for an exciting exploration of big numbers and exciting code? Let's dive in!

Before we delve into the realm of optimized algorithms and matrix magic, let's embark on a journey that traces back to the traditional method of calculating Fibonacci numbers through recursion. While this approach seems intuitive and simple, it quickly reveals its inefficiency as the numbers grow larger.

The Fibonacci sequence is often defined recursively, where each number is the sum of the two preceding ones: F(n) = F(n-1) + F(n-2). Let's implement this definition using a recursive function in Rust:

The time complexity of the recursive Fibonacci algorithm is approximately O(2^n), where n is the input number. This means that the computation time grows exponentially with the input size. As a result, even relatively small values of n can lead to considerable computation times.

Our journey then takes us to the creation of a robust data structure, aptly named BigInt, that empowers us to manipulate colossal numbers with finesse. Here's a glimpse into the code:

In this section, we introduce the BigInt structure, which stores the digits of a large number in a vector. Methods like new, from_vec, and to_string facilitate creation, conversion, and visualization of these gigantic numbers. The overloading of addition and multiplication operators enables seamless arithmetic operations on BigInt instances.

Matrix formula for Fibonacci numbers

But then, denoting

we get:

Thus, to find the nth Fibonacci number, you need to raise the matrix P to the power of n.

Remembering that raising a matrix to the n'th power can be done in O(log n) (see Binary exponentiation), it turns out that the nth Fibonacci number can be easily computed in O(log n) using only integer arithmetic.

Exponentiation, a fundamental mathematical operation, becomes significantly more powerful when combined with binary manipulation. Binary exponentiation, also known as binary powering, is a technique that empowers us to compute the result of raising a number to a certain power in a remarkably efficient manner. In this section, we'll explore the binary exponentiation algorithm, understand its mechanics, and delve into its implementation.

Binary exponentiation is a technique that allows us to compute a^n with only O(log n) multiplications, a substantial improvement over the naive approach of performing n multiplications. What's more, this technique can be applied not only to exponentiation but to any associative operation, making it versatile and applicable to a wide range of scenarios.

An operation is associative if, for any values a, b, and c, the following holds true:

This associativity property forms the foundation of binary exponentiation, extending its application to various operations, including modular arithmetic and matrix multiplication.

The Algorithm Unveiled: Binary Exponentiation Steps

The beauty of binary exponentiation lies in its simplicity and elegance. Let's break down the algorithm into steps and unveil its magic:

Observe that for any number a and even power n, the following identity holds true (derived from the associativity of multiplication):

This identity forms the crux of the binary exponentiation algorithm. When n is even, we've shown how to reduce the problem to computing the power of a^(n/2) using only one multiplication.

Now, let's consider the case when n is odd. In this scenario, we can convert the problem to computing the power of a^(n-1), which is even:

The algorithm essentially recurses by splitting the exponent n into two parts: one part that is halved (n/2 or n-1) and another part that is always squared (n/2). This recurrence continues until n reaches the base case of 0, where the result is 1.

Here's the implementation of binary exponentiation in Rust:

In this implementation, we iteratively update result and a based on the binary properties of n, optimizing the calculation process.

Combining all of the above, we get a way to calculate fibonacci numbers very quickly. Below is all the code that, without third-party dependencies, calculates these numbers very well

  You can try it here: rust playground