understanding the mathematical algorithm behind the TPRODUCT problem

I've been trying to solve the codechef problem: http://www.codechef.com/MAY11/problems/TPRODUCT/

They have given the post-contest analysis here: http://www.codechef.com/wiki/may-2011-contest-problem-editorials

I need some help in开发者_开发百科 understanding the logic discussed there: They are talking about using logarithm in place of the function

Pi=max(Vi*PL, Vi*PR)

Math is not my strong area. [I've been trying to improve by participating in contests like this]. If someone can give a very dumbed down explanation for this problem, it would be helpful for mortals like me. Thanks.

One large problem with multiplication is that numbers get very large very fast, and there are issues with reaching the upper bounds of an int or long, and spilling over to the negatives. The logarithm allows us to keep the computations small, and then get the answer back modulo n.

In retracing the result found via dynamic programming, the naive solution is to multiply all the values together and then mod:

(x0 * x1 * x2 * ... * xk) (mod n)

this is replaced with a series of smaller computations, which avoid bound overflow:

z1 = e^(log(x0) + log(x1)) modulo n
z2 = e^(log(x2) + log(z1)) modulo n
...
zk = e^(log(xk) + log(z{k-1})) modulo n

and then zk contains the result.

Presumably, they are relying on the simple mathematical observation that if:

z = y * x

then:

log(z) = log(y) + log(x)

Thus turning multiplications into additions.