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!
Part 0: The Recursive Dilemma – Traditional Fibonacci Computation
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.
Traditional Recursive Approach
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:
fn fibonacci_recursive(n: u32) -> u32 {
if n == 0 {
return 0;
} else if n == 1 || n == 2 {
return 1;
} else {
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}
}
Time Complexity Analysis
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.
Part 1: BigInt – Building Blocks for Big Numbers
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:
// Import necessary libraries
use std::cmp::max;
use std::fmt;
use std::ops::{Add, Mul};
// Define the BigInt structure
#[derive(Debug, Clone)]
struct BigInt {
data: Vec<u32>,
}
impl BigInt {
// Constructor for creating a BigInt from a single value
fn new(value: u32) -> Self {
BigInt {
data: vec![value], // Initialize the data vector with the provided value.
}
}
// Constructor for creating a BigInt from a vector of digits
fn from_vec(data: Vec<u32>) -> Self {
BigInt {
data, // Initialize the data vector with the provided digits.
}
}
// Convert the BigInt to a string
fn to_string(&self) -> String {
self.data.iter().rev().map(|digit| digit.to_string()).collect() // Convert each digit to a string and concatenate.
}
}
// Implement addition for BigInt
impl Add<&BigInt> for &BigInt {
type Output = BigInt;
fn add(self, other: &BigInt) -> BigInt {
// ... (Addition logic)
// Perform digit-wise addition, considering carry values.
// Return a new BigInt instance representing the sum.
}
}
// Implement multiplication for BigInt
impl Mul<&BigInt> for &BigInt {
type Output = BigInt;
fn mul(self, other: &BigInt) -> BigInt {
// ... (Multiplication logic)
// Implement binary multiplication algorithm to efficiently compute the product.
// Return a new BigInt instance representing the product.
}
}
// ... (Other operations, methods, and traits for BigInt)
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.
Part 2: Matrix Magic – Cracking Fibonacci's Code
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.
Part 3: Binary Exponentiation: Unleashing the Power of Efficient Exponentiation
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.
The Binary Exponentiation Algorithm: A Glimpse into Efficiency
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.
The Essence of Associativity: A Brief Recap
An operation is associative if, for any values a, b, and c, the following holds true:
(a * b) * c = a * (b * c)
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):
a^n = (a^(n/2))^2 = a^(n/2) * a^(n/2)
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:
a^n = a^(n-1) * a
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:
fn binary_pow(a: u32, mut n: u32) -> u32 {
let mut result = 1;
while n > 0 {
if n & 1 == 1 {
result *= a; // Accumulate the result using binary multiplication.
}
a *= a; // Square the base for each iteration.
n >>= 1; // Halve the exponent.
}
result
}
In this implementation, we iteratively update result and a based on the binary properties of n, optimizing the calculation process.
Part 4: Conclusion
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
use std::cmp::max;
use std::fmt;
use std::ops::{Add, Mul};
#[derive(Debug, Clone)]
struct BigInt {
data: Vec<u32>,
}
impl BigInt {
fn new(value: u32) -> Self {
BigInt {
data: vec![value],
}
}
fn from_vec(data: Vec<u32>) -> Self {
BigInt { data }
}
fn to_string(&self) -> String {
self.data.iter().rev().map(|digit| digit.to_string()).collect()
}
}
impl Add<&BigInt> for &BigInt {
type Output = BigInt;
fn add(self, other: &BigInt) -> BigInt {
let max_len = max(self.data.len(), other.data.len());
let mut result = Vec::new();
let mut carry = 0;
for i in 0..max_len {
let a = if i < self.data.len() { self.data[i] } else { 0 };
let b = if i < other.data.len() { other.data[i] } else { 0 };
let sum = a + b + carry;
result.push(sum % 10);
carry = sum / 10;
}
if carry > 0 {
result.push(carry);
}
BigInt::from_vec(result)
}
}
impl Mul<&BigInt> for &BigInt {
type Output = BigInt;
fn mul(self, other: &BigInt) -> BigInt {
let mut result = BigInt::new(0);
for (i, num) in other.data.iter().enumerate() {
let mut carry = 0;
let mut temp_result = vec![0; i];
for &digit in self.data.iter() {
let product = digit * num + carry;
temp_result.push(product % 10);
carry = product / 10;
}
if carry > 0 {
temp_result.push(carry);
}
result = &result + &BigInt::from_vec(temp_result);
}
result
}
}
fn matrix_mul(a: &[[BigInt; 2]; 2], b: &[[BigInt; 2]; 2]) -> [[BigInt; 2]; 2] {
let mut result = [[BigInt::new(0), BigInt::new(0)], [BigInt::new(0), BigInt::new(0)]];
for i in 0..2 {
for j in 0..2 {
for k in 0..2 {
result[i][j] = &result[i][j] + &(&a[i][k] * &b[k][j]);
}
}
}
result
}
fn matrix_power(matrix: &[[BigInt; 2]; 2], power: u32) -> [[BigInt; 2]; 2] {
if power == 0 {
[
[BigInt::new(1), BigInt::new(0)],
[BigInt::new(0), BigInt::new(1)],
]
} else if power == 1 {
matrix.clone()
} else {
let half_power = power / 2;
let half_matrix = matrix_power(matrix, half_power);
let result = matrix_mul(&half_matrix, &half_matrix);
if power % 2 == 0 {
result
} else {
matrix_mul(&result, matrix)
}
}
}
fn fibonacci(n: u32) -> BigInt {
if n == 0 {
BigInt::new(0)
} else if n == 1 || n == 2 {
BigInt::new(1)
} else {
let base_matrix = [
[BigInt::new(1), BigInt::new(1)],
[BigInt::new(1), BigInt::new(0)],
];
let matrix_power_n_minus_1 = matrix_power(&base_matrix, n - 1);
matrix_power_n_minus_1[0][0].clone()
}
}
impl fmt::Display for BigInt {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.to_string())
}
}
fn main() {
let n = 10000;
let result = fibonacci(n);
println!("Fibonacci({}) = {}", n, result);
}
The result of the program execution:
You can try it here: rust playground
Also you can see more posts here: Boosty
Top comments (0)