Power Matrix

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
angelmh
Posts: 11
Joined: Wed Dec 02, 2015 11:08 am
Gender: None specified

Power Matrix

Postby angelmh » Fri Mar 11, 2016 11:04 pm

Hola, queisiera ver si alguien puede colocar alguna descripcion de este tema, de segur que como a mi, est le hace falta a muchos. Gracias de antemano y saludos.



humbertodiaz
Posts: 97
Joined: Mon Oct 06, 2014 6:25 am
Gender: None specified

Re: Power Matrix

Postby humbertodiaz » Sat Mar 12, 2016 7:09 am

Saludos. Que quieres decir con "power matrix"? Quieres decir exponenciacion de matrices? Es decir, elevar una matriz a una potencia?

angelmh
Posts: 11
Joined: Wed Dec 02, 2015 11:08 am
Gender: None specified

Re: Power Matrix

Postby angelmh » Sat Mar 12, 2016 8:13 pm

Si amigo, disculpa por no expresarme bien, es eso mismo que mencionas, mi problema es directamente Fibonacci, el lio es que para hallar Fibo(n) donde n es muy grande, digamos n = 10^15, si trabajo con long no me calcula correctamente el resultado y si lo hago con BigInteger me mata el time limit exceded, que puedo hacer en mi caso? ejemplo de ello es el problema 3480, el cual lo hallo relativamente sencillo por esa via de las matrices pero no me da correctamente. Saludos y gracias adelantada por tu ayuda.

humbertodiaz
Posts: 97
Joined: Mon Oct 06, 2014 6:25 am
Gender: None specified

Re: Power Matrix

Postby humbertodiaz » Mon Mar 21, 2016 1:16 am

Disculpa que me he tardado en responder. Estuve ocupado con una competencia.

En realidad tienes dos problemas. Primero, los calculos en estos tipos de problemas tipicamente se tienen que hacer aplicando modulo. El ejercicio 3480, por ejemplo, indica que los calculos se deben hacer modulo 1000. Se pueden organizar las operaciones para que no haya un desbordamiento. BigInteger permite hacer los calculos sin ese riesgo, pero se generan numeros tan grandes en el proceso que los calculos toman demasiado tiempo. La clave es una implementacion hecha con cuidado.

Ahora explicare la segunda parte: como calcular terminos de una relacion de recurrencia eficientemente usando exponenciacion de matrices.

Digamos que tienes una relacion de recurrencia como la siguiente:

F(n) = aF(n - 1) + bF(n - 2)

Los valores iniciales son F(0) y F(1). Evaluar esa funcion se puede representar como una multiplicacion de matrices:

Code: Select all

[ u  v ] [ F(n - 1) ]  =  [ F(n)     ]
[ x  y ] [ F(n - 2) ]     [ F(n - 1) ]


Hay que deducir que valores van en la matriz para que se cumpla la relacion que deseamos. Podemos expandir las ecuaciones envueltas para ver cuales valores determinan cuales resultados:

uF(n - 1) + vF(n - 2) = F(n)
xF(n - 1) + yF(n - 2) = F(n - 1)


La segunda ecuacion nos sugiere que x = 1, y = 0. La primera ecuacion es igual a la relacion de recurrencia, lo cual implica que u = a, v = b. Entonces terminamos con la siguiente ecuacion de matrices:

Code: Select all

[ a  b ] [ F(n - 1) ]  =  [ F(n)     ]
[ 1  0 ] [ F(n - 2) ]     [ F(n - 1) ]


Podriamos, por ejemplo, calcular F(2) de esta manera:

Code: Select all

[ a  b ] [ F(1) ]  =  [ F(2) ]
[ 1  0 ] [ F(0) ]     [ F(1) ]


Ahora considera que esto se le podria aplicar a cualquier par de terminos consecutivos de la recurrencia para obtener el proximo. Tampoco estamos limitados a multiplicar por la matriz de la izquierda una sola vez. Por cada vez que multiplicamos, "avanzamos" otro termino en la secuencia:

Code: Select all

[ a  b ] [ a  b ] [ F(1) ]  =  [ F(3) ]
[ 1  0 ] [ 1  0 ] [ F(0) ]     [ F(2) ]


La operacion de multiplicacion de matrices es asociativa. Multiplicar las primeras dos matrices y despues multiplicar por la tercera da el mismo resultado final que multiplicar las ultimas dos y despues por la primera. Ademas, multiplicar por la matriz de la izquierda repetidamente es equivalente a multiplicar por una potencia de esa matriz. Si deseamos multiplicar n veces, es equivalente a multiplicar por su n-esima potencia:

Code: Select all

[ a  b ] ^ n [ F(1) ]  =  [ F(n + 1) ]
[ 1  0 ]     [ F(0) ]     [ F(n)     ]


Afortunadamente, calcular la n-esima potencia de esa matriz se puede hacer eficientemente usando el algoritmo de exponenciacion binaria. El proceso requiere O(log n) productos de matrices en el peor caso, lo cual es sumamente eficiente para algo como n = 10^15 y las matrices pequeñas requeridas para secuencias como la de Fibonacci. El algoritmo es esencialmente identico al que se usa para exponenciacion de numeros, pero reemplaza la multiplicacion de numeros con multiplicacion de matrices.

Un detalle importante que hay que considerar para la implementacion es que se debe aplicar modulo mientras se hacen los calculos. Quizas no es inmediatamente evidente como integrar modulo a un algoritmo que utiliza matrices. Se debe tomar modulo en cada operacion que se haga entre matrices. Esto da los mismos resultados como si se evaluara la recurrencia directamente y se tomara modulo en el proceso. Nota que se debe implementar con cuidado para evitar que haya un desbordamiento en algun paso intermedio.

Finalmente, esta tecnica es aplicable a otras tipos de relaciones de recurrencia. Por ejemplo, se podria aplicar a secuencias que dependen de mas de dos terminos anteriores o que envuelven sumar una constante tambien. Solo limite el analisis para que fuera mas claro.

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: Power Matrix

Postby isaac » Tue Mar 22, 2016 2:28 pm

Existe una matriz con la que se puede encontrar los terminos de la sucesion de Fibonnaci en log n. La matriz es la siguiente:

0 1
1 1

Si elevas la matriz a la N, queda:

F[n-2] F[n-1]
F[n-1] F[n]

y como decia Humberto, con exponenciacion modular, puedes hacerlo de forma eficiente. Saludos.


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest