As part of an assignment I was asked to find an optimized algorithm to find the m modulus of nth Fibonacci number.
Sounds pretty easy, untill you see the size of the inputs, n has 30 digits in it.
At this stage, basic methods or brute force methods will take eons to finish this. And I had to go back to Maths to find the solution.
The algorithm came from here http://math.stackexchange.com/questions/784710/how-to-prove-fibonacci-sequence-with-matrices#answer-784723
Using A matrix equation for calculating super huge fibonacci numbers.
What we are trying to achieve is
F(n) % n # Where F(n) is the nth Fibonacci Number.
Below is the python code for the same.