Multiplicación de Toom-Cook

En Toom- k , queremos dividir los factores en k partes.

El primer paso consiste en seleccionar la base B  = b ⁱ , de modo que el número de dígitos tanto de m como de n en la base B sea como máximo k (por ejemplo, 3 en Toom-3). Una elección típica para i viene dada por: 

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.}$

En nuestro ejemplo haremos Toom-3, así que elegimos B = b ² = 10 ⁸ . Luego separamos m y n en sus dígitos de base B m _i , n _i :

${\displaystyle {\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}}$

Luego usamos estos dígitos como coeficientes en polinomios de grado ( k − 1) p y q , con la propiedad de que p ( B )  = m y q ( B ) = n :   

${\displaystyle p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,}$

${\displaystyle q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,}$

El propósito de definir estos polinomios es que si podemos calcular su producto r ( x ) = p ( x ) q ( x ) , nuestra respuesta será r ( B ) = m × n .

En el caso de que los números que se multiplican sean de diferente magnitud, es útil usar diferentes valores de k para m y n , que llamaremos k _m y k _n . Por ejemplo, el algoritmo "Toom-2.5" se refiere a Toom-Cook con k _m  =  3 y k _n  =  2. En este caso, el i en B  = b ⁱ se elige típicamente de la siguiente manera: 

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.}$

El método de Toom-Cook para calcular el producto polinomial${\displaystyle p(x)q(x)}$es uno de uso común. Nótese que un polinomio de grado${\displaystyle d}$está determinado de forma única por${\displaystyle d+1}$puntos (por ejemplo, una línea – un polinomio de grado uno está especificado por dos puntos). La idea es evaluar${\displaystyle p(\cdot )}$y${\displaystyle q(\cdot )}$en varios puntos. Luego, multiplica sus valores en esos puntos para obtener puntos en el polinomio producto. Finalmente, interpola para hallar sus coeficientes.

Desde${\displaystyle \deg(pq)=\deg(p)+\deg(q)}$, necesitaremos${\displaystyle \deg(p)+\deg(q)+1=k_{m}+k_{n}-1}$puntos para determinar el resultado final. Llame a esto${\displaystyle d}$. En el caso de Toom-3,${\displaystyle d=5}$El algoritmo funcionará independientemente de los puntos que se elijan (con algunas pequeñas excepciones, véase el requisito de invertibilidad de la matriz en Interpolación ), pero para simplificar el algoritmo es mejor elegir valores enteros pequeños como 0, 1, -1 y -2.

Un valor puntual inusual que se usa con frecuencia es el infinito, escrito${\displaystyle \infty }$o${\displaystyle 1/0}$Para "evaluar" un polinomio${\displaystyle p}$en el infinito en realidad significa tomar el límite de${\displaystyle p(x)/x^{\deg p}}$como${\displaystyle x}$va al infinito. En consecuencia,${\displaystyle p(\infty )}$siempre es el valor de su coeficiente de grado más alto (en el ejemplo anterior coeficiente${\displaystyle m_{2}}$).

En nuestro ejemplo de Toom-3, utilizaremos los puntos${\displaystyle 0}$,${\displaystyle 1}$,${\displaystyle -1}$,${\displaystyle -2}$, y${\displaystyle \infty }$Estas opciones simplifican la evaluación, generando las siguientes fórmulas:

${\displaystyle {\begin{array}{lrlrlr}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}}$

y análogamente para${\displaystyle q}$En nuestro ejemplo, los valores que obtenemos son:

${\displaystyle {\begin{array}{lrlrlr}p(0)&=&m_{0}&=&56789012&=&56789012\\p(1)&=&m_{0}+m_{1}+m_{2}&=&56789012+78901234+123456&=&135813702\\p(-1)&=&m_{0}-m_{1}+m_{2}&=&56789012-78901234+123456&=&-21988766\\p(-2)&=&m_{0}-2m_{1}+4m_{2}&=&56789012-2\times 78901234+4\times 123456&=&-100519632\\p(\infty )&=&m_{2}&=&123456&=&123456\\[4pt]q(0)&=&n_{0}&=&54321098&=&54321098\\q(1)&=&n_{0}+n_{1}+n_{2}&=&54321098+43219876+98765&=&97639739\\q(-1)&=&n_{0}-n_{1}+n_{2}&=&54321098-43219876+98765&=&11199987\\q(-2)&=&n_{0}-2n_{1}+4n_{2}&=&54321098-2\times 43219876+4\times 98765&=&-31723594\\q(\infty )&=&n_{2}&=&98765&=&98765\end{array}}}$

Como se muestra, estos valores pueden ser negativos.

Para una explicación posterior, será útil ver este proceso de evaluación como una multiplicación matriz-vector, donde cada fila de la matriz contiene potencias de uno de los puntos de evaluación, y el vector contiene los coeficientes del polinomio:

${\displaystyle \left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1)^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2}\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left({\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right).}$

Las dimensiones de la matriz son d x k _m para p y d x k _n para q . La fila correspondiente al infinito siempre es toda cero, excepto por un 1 en la última columna.

A diferencia de multiplicar los polinomios${\displaystyle p(\cdot )}$y${\displaystyle q(\cdot )}$multiplicando los valores evaluados${\displaystyle p(a)}$y${\displaystyle q(a)}$Simplemente implica multiplicar números enteros , una instancia más pequeña del problema original. Invocamos recursivamente nuestro procedimiento de multiplicación para multiplicar cada par de puntos evaluados. En implementaciones prácticas, a medida que los operandos se vuelven más pequeños, el algoritmo pasará a la multiplicación larga estándar . Siendo r el polinomio producto, en nuestro ejemplo tenemos:

${\displaystyle {\begin{array}{l c l c l c r}r(0)&=&p(0)\,q(0)&=&56789012\times 54321098&=&3084841486175176\\r(1)&=&p(1)\,q(1)&=&135813702\times 97639739&=&13260814415903778\\r(-1)&=&p(-1)\,q(-1)&=&-21988766\times 11199987&=&-246273893346042\\r(-2)&=&p(-2)\,q(-2)&=&-100519632\times -31723594&=&3188843994597408\\r(\infty )&=&p(\infty )\,q(\infty )&=&123456\times 98765&=&12193131840.\end{array}}}$

Como se muestra, estos también pueden ser negativos. Para números suficientemente grandes, este es el paso más costoso, el único paso que no es lineal en los tamaños de${\displaystyle m}$y${\displaystyle n}$.

Este es el paso más complejo, el inverso del paso de evaluación: dado nuestro${\displaystyle d}$puntos en el polinomio producto${\displaystyle r(\cdot )}$Necesitamos determinar sus coeficientes. En otras palabras, queremos resolver esta ecuación matricial para el vector del lado derecho:

${\displaystyle {\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2}&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(-2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{aligned}}}$

Esta matriz se construye de la misma manera que la del paso de evaluación, excepto que es${\displaystyle d\times d}$Podríamos resolver esta ecuación con una técnica como la eliminación gaussiana , pero esto es demasiado costoso. En su lugar, utilizamos el hecho de que, siempre que los puntos de evaluación se hayan elegido adecuadamente, esta matriz es invertible (véase también la matriz de Vandermonde ), y por lo tanto:

${\displaystyle {\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1}{6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{\tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned}}}$

Solo queda calcular este producto matriz-vector. Aunque la matriz contiene fracciones, los coeficientes resultantes serán enteros , por lo que todo se puede realizar con aritmética entera, simplemente sumas, restas y multiplicaciones/divisiones por constantes pequeñas. Un desafío de diseño complejo en Toom-Cook es encontrar una secuencia eficiente de operaciones para calcular este producto; una secuencia propuesta por Bodrato ^{[ 6 ]} para Toom-3 es la siguiente, ejecutada aquí sobre el ejemplo en ejecución:

${\displaystyle {\begin{array}{l c l c r}r_{0}&\leftarrow &r(0)&=&3084841486175176\\r_{4}&\leftarrow &r(\infty )&=&12193131840\\r_{3}&\leftarrow &(r(-2)-r(1))/3&=&(3188843994597408-13260814415903778)/3\\&&&=&-3357323473768790\\r_{1}&\leftarrow &(r(1)-r(-1))/2&=&(13260814415903778-(-246273893346042))/2\\&&&=&6753544154624910\\r_{2}&\leftarrow &r(-1)-r(0)&=&-246273893346042-3084841486175176\\&&&=&-3331115379521218\\r_{3}&\leftarrow &(r_{2}-r_{3})/2+2r(\infty )&=&(-3331115379521218-(-3357323473768790))/2+2\times 12193131840\\&&&=&13128433387466\\r_{2}&\leftarrow &r_{2}+r_{1}-r_{4}&=&-3331115379521218+6753544154624910-12193131840\\&&&=&3422416581971852\\r_{1}&\leftarrow &r_{1}-r_{3}&=&6753544154624910-13128433387466\\&&&=&6740415721237444\end{array}}}$

Ahora conocemos nuestro polinomio producto${\displaystyle r}$:

${\displaystyle {\begin{array}{rrrl}r(x)=&&3084841486175176&\\&+&6740415721237444&\!\!\!\!x\\&+&3422416581971852&\!\!\!\!x^{2}\\&+&13128433387466&\!\!\!\!x^{3}\\&+&12193131840&\!\!\!\!x^{4}\end{array}}}$

Si estuviéramos usando diferentes${\displaystyle k_{m},k_{n}}$o puntos de evaluación, la matriz y por lo tanto nuestra estrategia de interpolación cambiaría; pero no depende de las entradas y por lo tanto se puede codificar de forma fija para cualquier conjunto dado de parámetros.

Finalmente, evaluamos r(B) para obtener nuestra respuesta final. Esto es sencillo ya que B es una potencia de b y, por lo tanto, las multiplicaciones por potencias de B son todos desplazamientos por un número entero de dígitos en base b . En el ejemplo actual, b = 10⁴ ^y B = ^b² = ^10⁸ .

Y este es de hecho el producto de 1234567890123456789012 y 987654321987654321098.

Aplicando formalmente la definición, podemos considerar Toom-1 ( k _m = k _n = 1). Esto no produce un algoritmo de multiplicación, sino un algoritmo recursivo que nunca se detiene, ya que reduce trivialmente cada instancia de entrada a una llamada recursiva con la misma instancia. El algoritmo requiere 1 punto de evaluación, cuyo valor es irrelevante, ya que se utiliza únicamente para "evaluar" polinomios constantes. Por lo tanto, la matriz de interpolación es la matriz identidad:

${\displaystyle \left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).}$

Toom-1.5 ( k _m = 2, k _n = 1) sigue siendo degenerado: reduce recursivamente una entrada a la mitad, pero deja la otra sin cambios; por lo tanto, solo podemos convertirlo en un algoritmo de multiplicación si proporcionamos un algoritmo de multiplicación de 1 × n como caso base (mientras que el verdadero algoritmo Toom-Cook se reduce a casos base de tamaño constante). Requiere 2 puntos de evaluación, elegidos aquí como 0 e ∞. Su matriz de interpolación es entonces la matriz identidad:

${\displaystyle \left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}}\right).}$

El algoritmo es esencialmente equivalente a una forma de multiplicación larga: ambos coeficientes de un factor se multiplican por el único coeficiente del otro factor.

Toom-2 ( k _m = 2, k _n = 2) requiere 3 puntos de evaluación, elegidos aquí como 0, 1 e ∞. Es lo mismo que la multiplicación de Karatsuba , con una matriz de interpolación de:

${\displaystyle \left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1\\0&0&1\end{matrix}}\right).}$

Toom-2.5 ( k _m = 3, k _n = 2) requiere 4 puntos de evaluación, elegidos aquí como 0, 1, −1 e ∞. Tiene entonces una matriz de interpolación de:

${\displaystyle \left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).}$