Q Matrix... Dynamic is not always the solution...

Alsalam alikom wa ra7mat allah wa barakatoh

Today I'm going to speak about a useful (I hope) piece of algorithm, that makes ur life easier ;)..

Let's re-visit the Fibonacci Series, F(n) = F(n-1) + F(n-2)

Till yesterday, I knew only the dynamic solution for it (Top Down and Bottom Up)

long long fib(unsigned int index) {
if (index < 0)
return 0;
if (sol[index] != -1)
return sol[index];
return fib(index - 1) + fib(index - 2);
}
looks neat, huh!!
so, what if I ask u to give me the answer of fib(1000000000) ?
this will require in the best case to have 1000000000 iterations which is O(n), mmmm bad!!

Let's see the second solution (using Q-Matrix)
Some math first :
Q: What do you need to calculate fib(n) ?
A: fib(n-1) & fib(n-2)

so, if we re-wrote the relation between inputs and output like this :
[fib(n-1), fib(n-2)] * [1, 1] = [fib(n-1) + fib(n-2), fib(n-1)] which is [fib(n), fib(n-1)]
[1, 0]

that last vector is suitable to get the next fib(n+1) if we multiplied it by the same matrix, right ? ok,... good,
now the idea :
let's call the matrix M, the vector V so Vn * M = Vn+1
if we did this : Vn * M^3, what will be the result ?
this will iterate 3 times and give us Vn+3 (in one step)
Q: How many matrix multiplications do you need to get M^1000000000 ?
A: lg(1000000000)
Q: How ?
A: M*M = M^2, M^2 * M^2 = M^4, M^4 * M^4 = M^8..... and so on, the powers goes this fast :2, 4, 8, 16, 32....... powers of 2 ;)

The code to do this multiplication goes like this :
Matrix power(int n)
{
if (n <= 1)
return *this;
int i;
Matrix res = *this;
for(i = 2; i < n; i += i)
res = res * res;
i /= 2;
return res.power(n - i);
}
When you are sure you understand this, try to solve this nice problem : http://acm.uva.es/p/v107/10743.html

That's it for today...
C u soon In Shaa Allah,

Alsalam alikom wa ra7mat allah wa barakatoh