Fibonacci numbers
Introduction
The fibonacci series is the number sequence in which the given number results from adding the two previous numbers. The terms in the Fibonacci sequence are as follows:
The individual numbers in this sequence are called Fibonacci numbers. The Fibonacci sequence is a fantastic mathematical concept found in various places, including seashell patterns and the Parthenon.
Properties of Fibonacci Numbers
- The ADDITION Rule
F_{N + K} = F_{K} . F_{N + 1} + F_{K - 1} . F_{N}
- Applying Addition Rule to the case, K = N
F_{N + N} = F_{N} . F_{N + 1} + F_{N - 1} . F_{N}
F_{2N} = F_{N} ( F_{N + 1} + F_{N - 1})
- From the above property, we can prove that for any positive integer K, F_{NK} is the multiple of F_{N }(By the Induction Hypothesis).
- The inverse of the above property is true since, if F_{M} is multiple of F_{N}, then M is also the multiple of N.
- Cassini’s Identity
F_{N - 1} . F_{N + 1} - F_{N}^{2} = (-1)^{N}
This identity was given by Giovanni Domenico Cassini, an Italian mathematician. In the mathematical expression, N is the variable and it can have values from 1…..N.
For eg., if ‘N’ is an odd number, i.e. 1, 3, 5,... then (-1)^{N+1} = +1 in every case. But if we take even value here, we will get the result as -1.
- GCD Identity
For M, N >= 1
GCD(F_{M} , F_{N}) = F_{GCD (M, N) }, where M, N are integers
The Golden Ratio Approach
The golden ratio is defined as the limit of the ratio of successive terms in the Fibonacci sequence.
Now, if we divide F_{2 }with F_{1}, we get, F_{2} / F_{1} = 1 / 1 = 1 F_{3} / F_{2} = 2 / 1 = 2 F_{4} / F_{3} = 3 / 2 = 1.5 F_{5} / F_{4} = 5 / 3 = 1.667 F_{6} / F_{5} = 8 / 5 = 1.6 F_{7} / F_{6} = 13 / 8 = 1.625 F_{8} / F_{7} = 21 / 13 = 1.61538 F_{9} / F_{8} = 34 / 21 = 1.619047 F_{10} / F_{9} = 55 / 34 = 1.61765 F_{11} / F_{10} = 89 / 55 = 1.61818 F_{12} / F_{11} = 144 / 89 = 1.617975 F_{13} / F_{12} = 233 / 144 = 1.61805 . . . and so on. |
The golden ratio is coming about 1.618, as it means that as ‘N’ becomes sufficiently large, the fibonacci sequence approaches or approximates a geometric sequence. So, starting at number 144, and if we multiply 144 by 1.618, we get 233 (Approx.), the next element in the sequence. If we now multiply 233 with 1.618, we get approximately 377. Hence this golden ratio helps to approximate the next number in the series easily.
The formula for golden ratio is,
(1 + √5)^{N } - (1 - √5)^{N} F_{N} = ------------------------------ 2^{N} . √5 |
For example, let us find out the 8^{th} element in the sequence using the formula,
(1 + √5)^{8 } - (1 - √5)^{8}
F_{8} = ------------------------------ = 21
2^{8} . √5
Code:
// To print the Nth Fibonacci Number. #include <bits/stdc++.h> using namespace std; // The approx value of the golden ratio approach double goldenRatio = 1.6180339; // Taking an array of size, 'N' = 5 int fibonacciSeries[5] = {0, 1, 1, 2, 3}; // The function to find Nth fibonacci number int fibonacci(int N){ // The fibonacci no.s for N < 5 if(N < 5) return fibonacciSeries[N]; // Or else to start counting from the 4th term int i = 4, func = 4; while(i < N){ func = round(func * goldenRatio); i++; } return func; } // Main program int main(){ int N = 10; cout << N << "th Fibonacci number in the series: " << fibonacci(N) << endl; return 0; } |
Output:
10th Fibonacci number in the series: 68 |
The matrix multiplication in O(log N)
Code of Fibonacci Number Matrix Multiplication in C++
// To find the Nth Fibonacci Number in O(log N) time complexity "; |
Input:
Enter the Nth position to find the matrix exponentiation: 7 |
Output:
21 13 13 8 |
Time Complexity
The time complexity depends on two factors:
- Matrix multiplication, K^{3}
As the matrix moves ‘column by column’ or ‘row by row’, we will get a matrix K x K where ‘K’ represents the number of states. We can notice that in our code, the function ‘multiply’ has three nested for loops which takes time complexity = K x K x K = K^{3}.
- Log(N)
For computing the large input, we raise the matrix to the power N, which takes log(N) time.
Hence, multiplying both the factors (1) and (2), we get => K^{3}. log(N)
Therefore, the time complexity will be O(K^{3} log N).
Space Complexity
The space complexity is O(log N) since we raise the matrix to the Nth power. Hence it will take O(log N) additional space.
Frequently Asked Questions
What is the golden ratio in the Fibonacci sequence?
From atoms to the massive stars in the sky has patterns. The golden ratio reveals predictable or observable patterns. This ratio is derived from the Fibonacci sequence, named after Leonardo Fibonacci, an Italian mathematician.
What is the time complexity of finding the Nth fibonacci term by recursion?
The time complexity by recursion is O(2^{N}).
What is the time complexity of finding N^{th} fibonacci term with DP?
For finding the N^{th} fibonacci number, we got O(N) time complexity in the dynamic programming method.
Here, we store the previous terms, which are overlapping to reduce the time complexity.
Key Takeaways
In this blog, we learned about Fibonacci numbers, their properties, the working of matrix multiplication in O(log N) time complexity, and the golden ratio approach.
Try problems related to the Fibonacci numbers here on CodeStudio to understand the working concept of Fibonacci numbers. To be more confident in data structures and algorithms, try out our DS and Algo Course.
CREDITS: GIPHY
By Sneha Mallik
Comments
No comments yet
Be the first to share what you think