Fast Fibonacci Algorithms
Tags: fibonnaci
Published: 2020-06-28 12:45:11

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/vwbczstikrq4rhjkats8.png)
>          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):
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/73rfgt3654eip3oo2453.png)


Final Matrix Form Will be -
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/r5wnfrbbts4iwtww1a92.png)

>Fibonacci Problem On leetcode([Link](https://leetcode.com/problems/fibonacci-number/))using Matrix exponentiation:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/wk4ly6ufidpvok8qnyx8.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/a3wzsl9yasswomk1szy6.png) 
> **_Source Code_**: 

[Problem](https://leetcode.com/problems/fibonacci-number/)**:-**[Solution](https://github.com/adsv1623/Dev-Post/blob/master/Fibonacci-Exponential.cpp)  

##**# Fast doubling** (faster)
Fast doubling is based on two formulae
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/nj8la72mh7kup2cd6a7v.png)

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.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/inyiljn5me909q8c2nin.png)

>**Soution**:-[Link](https://github.com/adsv1623/Dev-Post/blob/master/Fast-Doubling-Fibonacci.cpp)

#_Other Problems_:
**1.Pisano Period.**
Take a detailed look at this table.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/z1853jpdg6jg3qwsuqs9.png)
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](https://github.com/adsv1623/Dev-Post/blob/master/Pisano.cpp)


**Github**
{% github adsv1623/Dev-Post %}
Other Sites:[Helper Guide](https://funloop.org/post/2017-04-14-computing-fibonacci-numbers.html) , [video](https://youtu.be/EEb6JP3NXBI)
***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:-)***