Multiplicación de Toom-Cook

Toom-Cook , a veces conocido como Toom-3 , llamado así por Andrei Toom , quien introdujo el nuevo algoritmo con su baja complejidad, y Stephen Cook , quien limpió su descripción, es un algoritmo de multiplicación para números enteros grandes.

Dados dos números enteros grandes, a y b , Toom-Cook divide a y b en k partes más pequeñas, cada una de longitud l , y realiza operaciones sobre las partes. A medida que k crece, se pueden combinar muchas de las suboperaciones de multiplicación, reduciendo así la complejidad computacional general del algoritmo. Las suboperaciones de multiplicación se pueden calcular de forma recursiva utilizando nuevamente la multiplicación de Toom-Cook, y así sucesivamente. Aunque los términos "Toom-3" y "Toom-Cook" a veces se usan incorrectamente de manera intercambiable, Toom-3 es solo una única instancia del algoritmo de Toom-Cook, donde k = 3.

Toom-3 reduce nueve multiplicaciones a cinco, y funciona en Θ( n ^{log(5)/log(3)} ) ≈ Θ( n ^1,46 ). En general, Toom- k funciona en Θ( c ( k ) n ^e ) , donde e = log(2 k − 1) / log( k ) , n ^e es el tiempo empleado en submultiplicaciones, y c es el tiempo empleado en adiciones y multiplicaciones por constantes pequeñas. ^[1] El algoritmo Karatsuba es equivalente a Toom-2, donde el número se divide en dos más pequeños. Reduce cuatro multiplicaciones a tres y, por lo tanto, funciona en Θ( n ^{log(3)/log(2)} ) ≈ Θ( n ^1,58 ).

Aunque el exponente e se puede fijar arbitrariamente cerca de 1 aumentando k , el término constante en la función crece muy rápidamente. ^{[1] [2]} La tasa de crecimiento de los esquemas Toom-Cook de nivel mixto todavía era un problema de investigación abierto en 2005. ^[3] Una implementación descrita por Donald Knuth logra la complejidad temporal Θ( n 2 ^{√ 2 log n} log n ) . ^[4]

Debido a su sobrecarga, Toom-Cook es más lento que la multiplicación larga con números pequeños y, por lo tanto, se utiliza normalmente para multiplicaciones de tamaño intermedio, antes de que el algoritmo de Schönhage-Strassen, asintóticamente más rápido (con complejidad Θ( n log n log log n ) ) se vuelva práctico.

Toom describió este algoritmo por primera vez en 1963, y Cook publicó un algoritmo mejorado (asintóticamente equivalente) en su tesis doctoral en 1966. ^[5]

Esta sección analiza exactamente cómo realizar Toom- k para cualquier valor dado de k , y es una simplificación de una descripción de la multiplicación de polinomios de Toom-Cook descrita por Marco Bodrato. ^[6] El algoritmo tiene cinco pasos principales:

1. Terrible
2. Evaluación
3. Multiplicación puntual
4. Interpolación
5. Recomposición

En una implementación típica de un número entero grande, cada número entero se representa como una secuencia de dígitos en notación posicional , con la base o el radio establecido en algún valor b (normalmente grande) ; para este ejemplo, usamos b  = 10000, de modo que cada dígito corresponde a un grupo de cuatro dígitos decimales (en una implementación informática, b normalmente sería una potencia de 2). Supongamos que los dos números enteros que se multiplican son:

metro	=	12	3456	7890	1234	5678	9012
norte	=	9	8765	4321	9876	5432	1098.

Son mucho más pequeños de lo que normalmente se procesaría con Toom-Cook (la multiplicación de primaria sería más rápida), pero servirán para ilustrar el algoritmo.

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

El primer paso es 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, por lo 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 :

$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 en que los números que se multiplican sean de distintos tamaños, resulta útil utilizar distintos 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, la i en B  =  b ⁱ se elige normalmente mediante:

${\displaystyle i=\max\{\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 polinómico p ( x ) q ( x ) es un método de uso común. Nótese que un polinomio de grado d está determinado de forma única por d  + 1 puntos (por ejemplo, un polinomio de grado uno está especificado por dos puntos). La idea es evaluar p (·) y q (·) en varios puntos. Luego, multiplicar sus valores en estos puntos para obtener puntos en el polinomio producto. Finalmente, interpolar para encontrar sus coeficientes.

Como deg( pq ) = deg( p ) + deg( q ) , necesitaremos deg( p ) + deg( q ) + 1 = k _m + k _n − 1 puntos para determinar el resultado final. Llamemos a esto d . En el caso de Toom-3, d  = 5. El algoritmo funcionará sin importar qué puntos se elijan (con algunas pequeñas excepciones, consulte el requisito de invertibilidad de la matriz en Interpolación), pero en aras de simplificar el algoritmo es mejor elegir valores enteros pequeños como 0, 1, −1 y −2.

Un valor puntual inusual que se utiliza con frecuencia es el infinito, escrito ∞ o 1/0. "Evaluar" un polinomio p en el infinito significa en realidad tomar el límite de p ( x )/ x ^{grado p} cuando x tiende al infinito. En consecuencia, p (∞) es siempre el valor de su coeficiente de mayor grado (en el ejemplo anterior, el coeficiente m ₂ ).

En nuestro ejemplo de Toom-3, utilizaremos los puntos 0, 1, −1, −2 y ∞. Estas opciones simplifican la evaluación y generan las fórmulas:

${\displaystyle {\begin{array}{lrlrl}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 q . En nuestro ejemplo, los valores que obtenemos son:

pág. (0)	=	m0​	=	56789012	=	56789012
pág. (1)	=	m0 + m1 + m2​​​	=	56789012 + 78901234 + 123456	=	135813702
p (−1)	=	m0 - m1 + m2​​​	=	56789012 − 78901234 + 123456	=	−21988766
p (−2)	=	m0-2m1 + 4m2​​​​​	=	56789012 − 2 × 78901234 + 4 × 123456	=	−100519632
p (∞)	=	metros cuadrados	=	123456	=	123456
q (0)	=	número 0	=	54321098	=	54321098
q (1)	=	n0 + n1 + n2​​​	=	54321098 + 43219876 + 98765	=	97639739
q (−1)	=	n0 - n1 + n2​​​	=	54321098 − 43219876 + 98765	=	11199987
q (−2)	=	n 0 − 2 n 1 + 4 n 2	=	54321098 − 2 × 43219876 + 4 × 98765	=	−31723594
q (∞)	=	número 2	=	98765	=	98765.

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{matriz}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matriz}}\right)=\left({\begin{matriz}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{matriz}}\right)\left({\begin{matr ix}m_{0}\\m_{1}\\m_{2}\end{matriz}}\right)=\left({\begin{matriz}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matriz}}\right)\left({\begin{matriz}m_{0}\\m_{1}\\m_{2}\end{matriz}}\right).}$

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

La evaluación multipunto se puede obtener más rápidamente que con las fórmulas anteriores. Se puede reducir el número de operaciones elementales (suma/resta). La secuencia dada por Bodrato ^[6] para Toom-3, ejecutada aquí sobre el primer operando (polinomio p ) del ejemplo en ejecución es la siguiente:

pág . 0	←	m0 + m2​​	=	56789012 + 123456	=	56912468
pág. (0)	=	m0​	=	56789012	=	56789012
pág. (1)	=	p0 + m1​​	=	56912468 + 78901234	=	135813702
p (−1)	=	p0 − m1​​	=	56912468 − 78901234	=	−21988766
p (−2)	=	( p (−1) + m 2 ) × 2 − m 0	=	(- 21988766 + 123456 ) × 2 - 56789012	=	− 100519632
p (∞)	=	metros cuadrados	=	123456	=	123456.

Esta secuencia requiere cinco operaciones de suma/resta, una menos que la evaluación simple. Además, se ahorró la multiplicación por 4 en el cálculo de p (−2).

A diferencia de la multiplicación de los polinomios p (·) y q (·), la multiplicación de los valores evaluados p ( a ) y q ( a ) solo 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 hacen más pequeños, el algoritmo cambiará a la multiplicación larga de libro escolar . Si r es el polinomio producto, en nuestro ejemplo tenemos:

o (0)	=	p (0) q (0)	=	56789012 × 54321098	=	3084841486175176
o (1)	=	p (1) q (1)	=	135813702 × 97639739	=	13260814415903778
r (−1)	=	p (−1) q (−1)	=	−21988766 × 11199987	=	-246273893346042
r (−2)	=	p (−2) q (−2)	=	−100519632 × −31723594	=	3188843994597408
r (∞)	=	p (∞) q (∞)	=	123456 × 98765	=	12193131840.

Como se muestra, 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 m y n .

Este es el paso más complejo, el inverso del paso de evaluación: dados nuestros d puntos en el polinomio producto r (·), 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 d × d . Podríamos resolver esta ecuación con una técnica como la eliminación gaussiana , pero es demasiado costosa. En su lugar, utilizamos el hecho de que, siempre que los puntos de evaluación se hayan elegido adecuadamente, esta matriz es invertible (ver también 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}}}$

Todo lo que queda es calcular este producto matriz-vector. Aunque la matriz contiene fracciones, los coeficientes resultantes serán números enteros, por lo que todo esto se puede hacer con aritmética de números enteros, simplemente sumas, restas y multiplicación/división por constantes pequeñas. Un desafío de diseño difícil en Toom-Cook es encontrar una secuencia eficiente de operaciones para calcular este producto; una secuencia dada por Bodrato ^[6] para Toom-3 es la siguiente, ejecutada aquí sobre el ejemplo en ejecución:

o0​	←	o (0)	=	3084841486175176
r4​	←	r (∞)	=	12193131840
r3​	←	( r (−2) − r (1))/3	=	(3188843994597408 − 13260814415903778)/3
			=	−3357323473768790
1​	←	( r (1) − r (−1))/2	=	(13260814415903778 − (−246273893346042))/2
			=	6753544154624910
r2​	←	r (−1) − r (0)	=	−246273893346042 − 3084841486175176
			=	−3331115379521218
r3​	←	( r2 - r3 ) / 2 + 2r ( ∞ )	=	(−3331115379521218 − (−3357323473768790))/2 + 2 × 12193131840
			=	13128433387466
r2​	←	r2 + r1 - r4​​​	=	−3331115379521218 + 6753544154624910 − 12193131840
			=	3422416581971852
1​	←	r1 - r3​​	=	6753544154624910 - 13128433387466
			=	6740415721237444.

Ahora conocemos nuestro producto polinomial r :

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

Si estuviéramos usando diferentes k _m , k _n o puntos de evaluación, la matriz y, por lo tanto, nuestra estrategia de interpolación cambiarían; pero no depende de las entradas y, por lo tanto, puede codificarse 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 todas desplazamientos por un número entero de dígitos en base b . En el ejemplo actual, b = 10 ⁴ y B = b ² = 10 ⁸ .

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840
	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

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

Aquí damos matrices de interpolación comunes para algunos valores pequeños comunes diferentes de k _m y k _n .

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 solo 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 reduciendo a la mitad su tamaño, pero deja la otra entrada sin cambios, por lo tanto, podemos convertirlo en un algoritmo de multiplicación solo si proporcionamos un algoritmo de multiplicación 1 × n como caso base (mientras que el verdadero algoritmo de 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 y ∞. Luego tiene 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).}$

• D. Knuth. El arte de la programación informática , volumen 2, tercera edición, Addison-Wesley, 1997. Sección 4.3.3.A: Métodos digitales, pág. 294.
• R. Crandall y C. Pomerance. Números primos: una perspectiva computacional . Segunda edición, Springer, 2005. Sección 9.5.1: Métodos de Karatsuba y Toom–Cook, pág. 473.
• Bodrato, Marco (2007). "Hacia una multiplicación óptima de Toom-Cook para polinomios univariados y multivariados de característica 2 y 0". En Carlet, Claude; Sunar, Berk (eds.). Aritmética de campos finitos, Primer taller internacional, WAIFI 2007, Madrid, España, 21 y 22 de junio de 2007, Actas . Apuntes de clase en informática. Vol. 4547. Springer. págs. 116–133. doi :10.1007/978-3-540-73074-3_10.
• Bodrato, Marco (8 de agosto de 2011). «Multiplicación óptima de polinomios de Toom-Cook/convolución de Toom Cook, implementación para polinomios» . Consultado el 22 de septiembre de 2023 .

• Multiplicación de tres vías de Toom-Cook de la documentación de GMP: "Multiplicación de tres vías de Toom". Manual de la biblioteca aritmética de precisión múltiple GNU MP (versión 6.3.0) . Free Software Foundation, Inc. 30 de julio de 2023 [Copyright 1991, 1993-2016, 2018-2020].