Fast Fibonacci Algorithms

Adarsh Raj — Sun, 28 Jun 2020 12:45:11 +0000

     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:

Problem:-Solution

# 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

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.

View on GitHub

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:-)

DEV Community: Adarsh Raj