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

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

## Comments

## Post a Comment