Algorithms For Fast Fibonacci Series.
Definition
The Fibonacci sequence is defined as
F(0)=0 , F(1)=1
F(n) = F(n−1)+F(n−2) for n≥2.
So the sequence (starting with F(0)) is 0, 1, 1, 2, 3, 5, 8, 13, 21, ….
Learning Outcomes
- See the huge difference between a slow algorithm and a fast one.
- Matrix exponentiation (fast)
- Fast doubling (faster)
- Other Problems On Fibonacci
- Pisano Period( F(n) mod m ) m ≥ 2.
# Matrix exponentiation (fast)
Matrix Exponentiation (also known as matrix power, repeated squaring) is a technique used to solve linear recurrences.
The concept of matrix exponentiation in its most general form is very useful in solving questions that involve calculating the nth term of a linear recurrence relation in time of the order of log(n).
The algorithm is based on this innocent-looking identity (which can be proven by mathematical induction):
Final Matrix Form Will be -
Fibonacci Problem On leetcode(Link)using Matrix exponentiation:
Source Code:
# Fast doubling (faster)
Fast doubling is based on two formulae
These identities can be extracted from the matrix exponentiation algorithm. This algorithm is the matrix exponentiation algorithm with the reductant calculations removed. It should be a constant factor faster than matrix exponentiation, but the asymptotic time complexity is still the same.
Soution:-Link
Other Problems:
1.Pisano Period.
Take a detailed look at this table.
You see is it Periodic?
yes,Both these sequences are periodic! For m = 2, the period is 011 and has length 3, while for m = 3 the period is 01120221 and has length 8.
Let's say, F(2015) mod 3 we just need to find the remainder of 2015 when divided by 8. Since 2015 = 251·8+7,
we conclude that F(2015) mod 3 = F 7 mod 3 = 1.
Solution:-Link
Github
Dev-Post
This C++ Program demonstrates the the computation of Fibonacci Numbers using Matrix Exponentiation.
Here is source code of the C++ Program to Find Fibonacci Numbers using Matrix Exponentiation.
Pisano Period For Computation Of Last digits For A large Fibonacci Sequence.
Other Sites:Helper Guide , video
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Like” button below, it’ll mean a lot to me. Thanks:-)
Top comments (0)