optimise my solution

Question

I just solve this but want know more efficient way to do matrix multiplication

M :
------
1 1 0
0 0 5
3 2 0

f[n] = M^n

I have implemented using Exponentiation_by_squaring

Is there more efficient then this ?

The whole modulo thing makes me think there could be some kind of mathematical hackery to turn it into simple equation. — Euphoric, Sep 04 '14 at 06:54
Shouldn't the modulo also be in calculateProduction for each variable? The way you have it now seems to be incorrect. — Euphoric, Sep 04 '14 at 07:00
`First I have thought recursive solution with dynamic programming but it take more time` Hang on... It shouldn't. Post the dynamic programming version. — UmNyobe, Sep 04 '14 at 07:37
dynamic programming won't help, because each value is only needed once. — kevin cline, Sep 05 '14 at 01:31

score 4 · Answer 1 · answered Sep 04 '14 at 09:52

4

Since N can be as large as 10^12 it should have been clear that iterating from 1 to N is not the desired solution. The key insight is that the recursion can be rewritten as V(i) = M * V(i-1), where

 V(i) = [RR(i), MM(i), PP(i)] (a column vector)

so

 V(0) = [ 3 1 0 ]

and

 M = | 1 0 3 |
     | 1 0 2 |
     | 0 5 0 |

Now V(N) = M^N * V(0)

We can calculate M^N in log(N) time by repeatedly squaring:

M^2 = M * M
M^4 = M^2 * M^2
...

Perform all calculations mod 100000006 to avoid accumulating large numbers.

To arrive at this solution, it helps to have a basic familiarity with linear algebra.

answered Sep 04 '14 at 09:52

kevin cline

33,608
3
71
142

1

`helps to have a` ***basic*** `familiarity with linear algebra`. Not that basic... – UmNyobe Sep 04 '14 at 09:59
aggree @UmNyobe , `@kevin` can you please explain more in detail .. How you declare M .. on which basis you have take M – HybrisHelp Sep 04 '14 at 10:10
1

I'm not sure if it would be possible to mod all calculations and arrive at correct solution using this approach. – Euphoric Sep 04 '14 at 10:12
`@kevin` and can you help me give exact program (if possible) cause i am newbie in algorithm. So i want to see this how can you implement such matrix and all .. If possible plz give program. – HybrisHelp Sep 04 '14 at 10:15
Basically he poses the recurrence above as evaluating a system of equations. He translate that to a matrix-vector multiplication (how it is solved) and now get a new recurrence `V(i+1) = M V(i)`. This can be translated as `V(N) = M^N * V(0)`. Now the problem is reduced to computing `M^N (exponentiation)` on a 3x3 matrix. this is algorithmic porn – UmNyobe Sep 04 '14 at 10:20
@UmNyobe I was taught this in school (albeit a maths-heavy one). It's already avoiding the harder problems like computing M^n as quickly as possible by giving an OK algorithm. The problem is a first order (simplest) [Recurrence relation](http://en.wikipedia.org/wiki/Recurrence_relation). The solution presented here is at the very beginning of the "Solving" and "Solving using linear algebra". Then it's a matter of computing an exponentiated matrix, and the OP proposes using squaring as an easy shortcut – Ordous Sep 04 '14 at 10:23
@Ordous same here, but it seems I forgot what have been taught. Coming with this by your own is definitely not easy. – UmNyobe Sep 04 '14 at 10:25
@Euphoric I'm fairly certain you could since `(a mod n) * (b mod n) = (ab mod n)` and `(a mod n) + (b mod n) = (a+b) mod n` and matrix multiplication (and exponentiation) can be decomposed into integer multiplication and summation. As long as your variables are long enough to contain `100000006^2 * 3` and you do mods *in between matrix multiplications* you should be absolutely fine. – Ordous Sep 04 '14 at 10:31
@Euphoric all say (a mod n) * (b mod n) = (ab mod n) but eg: `(13 mod 10) * (15 mod 10) != ((13*15) mod 10)` `3*5 != 5` – HybrisHelp Sep 04 '14 at 13:00
@Euphoric , @UmN , @kevin can you please tell me or refer a link to do `exponentiated matrix`. What could best dynamic solution to compute this in JAVA – HybrisHelp Sep 04 '14 at 13:05
@ankit337 Actually, you are missing mod 10 of whole left side. That will make it equal. – Euphoric Sep 04 '14 at 13:40
@Euphoric: I'm 100% sure you can take the modulus after each operation. It is only necessary to show that if a = b (mod N) then for any c, a + c = b + c (mod N) and a * c = b * c (mod N). – kevin cline Sep 05 '14 at 01:37
@UmNyobe: The fundamentals of vector and matrix multiplication is the most basic topic in linear algebra. – kevin cline Sep 05 '14 at 01:41
1

@ankit337: you can get further help only after presenting evidence of some effort on your part. Most of us get paid to program. Why should we work for free? – kevin cline Sep 05 '14 at 01:43

optimise my solution

1 Answers1