The famous Fibonacci sequence has fascinated mathematicians, artists, designers, and scientists for centuries. Also known as the Golden Ratio, this sequence and its remarkable prevalence in nature suggest its significance as a fundamental characteristic of the Universe.
The Fibonacci sequence begins with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and continues indefinitely. Each number is the sum of the two preceding numbers. Although it is a simple pattern, it seems to serve as an inherent numbering system in the cosmos.
The sequence was devised by Leonardo Fibonacci while studying the ideal growth patterns of rabbit populations over the course of a year. Today, these emerging patterns and ratios (phi = 1.61803...) can be observed on both micro and macro scales, spanning biological systems to inanimate objects. While the Golden Ratio does not account for every structure or pattern in the universe, it undeniably plays a significant role.
Following are some fascinating examples of phi (the Golden ratio) in the natural world.
The significance of the Golden ratio has also been seen in biological systems. Please refer here where it is discussed how Golden ratio is used to identify if the uterus is healthy or not.
Now let us look at Fibonacci numbers with a coding point of view.
There are multiple ways to find Nth Fibonacci number and they differ in their time complexities too. Lets gradually increase the complexities of these ways to find Fibonacci numbers and understand.
WAY 1 : Simple Recursion
int fib1(int n){
if(n == 0)
return 0;
if(n == 1)
return 1;
return fib(n-1) + fib(n-2);
}The code is pretty much self-explanatory where we use a top-down approach to find the Nth Fibonacci number.
Time Complexity - O(2^n)
Space Complexity - O(n)
WAY 2: Recursion with 1-D DP array (Memoization Technique)
int fib2(int n, vector <int>& dp){
if(n == 0) return 0;
if(n == 1) return 1;
if(dp[n] != -1) return dp[n];
dp[n-1] = fib(n-1, dp);
dp[n-2] = fib(n-2, dp);
return dp[n-1] + dp[n-2];
}This code takes an integer 'n' as input and a reference to a vector 'dp' that stores the computed values.
Time Complexity - O(n)
Space Complexity - O(n) + O(n) ~ O(n)
WAY 3: Tabulation using 1-D DP array
int fib3(int n, vector <int>& dp){
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<n+1;i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}This code takes an integer 'n' as input and fills the table (1-D DP array) in a bottom-up approach. Answer is the last element in the table.
Time Complexity - O(n)
Space Complexity - O(n)
WAY 4: Tabulation using 2 variables
int fib4(int n, vector <int>& dp){
int prev1 = 0;
int prev2 = 1;
int ans = 0;
for(int i=2;i<n+1;i++){
ans = prev1 + prev2;
prev1 = prev2;
prev2 = ans;
}
return ans;
}This code takes an integer 'n' as input and rather then filling the table in a bottom-up approach, it only updates two variables as any 'nth' Fibonacci number is dependent on only (n-1)th & (n-2)th Fibonacci number. This is a space optimized approach as compared to the above approaches.
Time Complexity - O(n)
Space Complexity - O(1)
WAY 5: Matrix Exponentiation
vector <vector<int>> matrixMultiplication(vector<vector<int>> a, vector<vector<int>> b){
int sz = a.size();
vector <vector<int>> ans(sz, vector<int>(sz,0));
for(int i=0;i<sz;i++){
for(int j=0;j<sz;j++){
for(int k=0;k<sz;k++)
ans[i][j] += a[i][k] * b[k][j];
}
}
return ans;
}
vector <vector<int>> findFib(int n, vector<vector<int>> a){
// if n==0, return identity matrix
if(n == 0){
int a_sz = a.size();
vector <vector<int>> ans(a_sz, vector<int>(a_sz,0));
for(int i=0;i<a_sz;i++)
ans[i][i] = 1;
return ans;
}
// if n==1, return the same matrix
if(n == 1) return a;
vector <vector<int>> intrm = findFib(n/2, a);
vector <vector<int>> ans = matrixMultiplication(intrm, intrm);
if(n&1) ans = matrixMultiplication(ans, a);
return ans;
}
int fib5(int fib){
// Edge cases
if(fib == 0) return 0;
else if(fib == 1) return 1;
vector <vector<int>> a = {{1,1},{1,0}};
vector <vector<int>> ans = findFib(fib, a);
return ans[0][1];
}This code implements an optimized approach to find the Fibonacci number at index 'fib' using matrix exponentiation. Let us look at it in a much greater depth.
The function matrixMultiplication() performs matrix multiplication of two square matrices 'a' and 'b'.
The function findFib() recursively calculates the Fibonacci matrix 'a' raised to the power of 'n'. If 'n' is 0, it returns an identity matrix. If 'n' is 1, it returns matrix 'a' itself. Otherwise, it recursively finds the matrix exponentiation of 'a' by halving 'n', and then squares the intermediate result. If 'n' is odd, it multiplies the result by matrix 'a' once more.
The function fib5() serves as an entry point to find the Fibonacci number at index 'fib'. It initializes matrix 'a' with the values {{1,1},{1,0}} as the Fibonacci transformation matrix. It then calls the findFib function to obtain the Fibonacci matrix raised to the power of 'fib'. The value at index [0][1] of the resulting matrix represents the Fibonacci number at index 'fib'.
Time Complexity - O(LogN)
Space Complexity - O(logN)
WAY 6: Using Golden Ratio
int fib6(int n){
return round(pow((1 + sqrt(5)) / 2, n) / sqrt(5));
}This code calculates the Fibonacci number at index 'n' using a closed-form formula based on the golden ratio.
The formula used is:
F(n) = round((phi^n) / sqrt(5))
Where phi is the golden ratio, approximately equal to:
phi = (1 + sqrt(5)) / 2.
The code essentially calculates the Fibonacci number using a direct mathematical formula, avoiding the need for recursion or iteration.
Time Complexity - O(1)
Space Complexity - O(1)
Conclusion:
Exploring various algorithms to compute Fibonacci numbers not only enhances our programming skills but also fosters a greater understanding and admiration for the captivating patterns and symmetries present in nature. By delving into the intersection of mathematics, programming, and the natural world, we gain valuable insights into the captivating interplay of science and art.
Thanks for reading. Cheers!
Comments