Toom-Cook , a veces conocido como Toom-3 , lleva el nombre de Andrei Toom , quien introdujo el nuevo algoritmo de 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 en 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 recursivamente 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 instancia del algoritmo Toom-Cook, donde k = 3.
Toom-3 reduce nueve multiplicaciones a cinco y ejecuta en Θ( n log(5)/log(3) ) ≈ Θ( n 1,46 ). En general, Toom- k se ejecuta en Θ( c ( k ) n e ) , donde e = log(2 k − 1) / log( k ) , n e es el tiempo dedicado a las submultiplicaciones y c es el tiempo gastado en sumas 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, opera en Θ( n log(3)/log(2) ) ≈ Θ( n 1,58 ). La multiplicación larga ordinaria es equivalente a Toom-1, con complejidad Θ ( n 2 ).
Aunque el exponente e se puede establecer 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 usa típicamente para multiplicaciones de tamaño intermedio, antes del algoritmo asintóticamente más rápido de Schönhage-Strassen (con complejidad Θ ( n log n log log n ) ) se vuelve práctico.
Toom describió por primera vez este algoritmo 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 polinomial de Toom-Cook descrita por Marco Bodrato. [6] El algoritmo tiene cinco pasos principales:
En una implementación típica de enteros grandes, cada número entero se representa como una secuencia de dígitos en notación posicional , con la base o base establecida en algún valor (normalmente grande) b ; 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). Digamos que los dos números enteros que se multiplican son:
Estos son mucho más pequeños de lo que normalmente se procesarían con Toom-Cook (la multiplicación en la escuela 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 i , de modo que el número de dígitos de myn 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:
En nuestro ejemplo haremos Toom-3, así que elegimos B = b 2 = 10 8 . Luego separamos m y n en sus dígitos de base B m i , n i :
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 :
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 diferentes tamaños, 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, la i en B = b i normalmente se elige por:
El enfoque de Toom-Cook para calcular el producto polinómico p ( x ) q ( x ) es uno de uso común. Tenga en cuenta que un polinomio de grado d está determinado únicamente por d + 1 puntos (por ejemplo, una línea - polinomio de grado uno está especificado por dos puntos). La idea es evaluar p (·) y q (·) en varios puntos. Luego multiplica sus valores en estos puntos para obtener puntos en el polinomio producto. Finalmente interpola para encontrar sus coeficientes.
Dado que grados( pq ) = grados( p ) + grados( q ) , necesitaremos grados( p ) + grados( q ) + 1 = k m + k n − 1 puntos para determinar el resultado final. Llame 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 puntos pequeños. valores enteros como 0, 1, −1 y −2.
Un valor de punto inusual que se usa con frecuencia es el infinito, escrito ∞ o 1/0. "Evaluar" un polinomio p en el infinito en realidad significa tomar el límite de p ( x )/ x grados p cuando x llega al infinito. En consecuencia, p (∞) es siempre el valor de su coeficiente de mayor grado (en el ejemplo anterior, coeficiente m 2 ).
En nuestro ejemplo de Toom-3, usaremos los puntos 0, 1, −1, −2 y ∞. Estas opciones simplifican la evaluación y producen las fórmulas:
y análogamente para q . En nuestro ejemplo, los valores que obtenemos son:
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:
Las dimensiones de la matriz son d por k m para p y d por k n para q . La fila del infinito siempre es cero excepto un 1 en la última columna.
La evaluación multipunto se puede obtener más rápido 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:
Esta secuencia requiere cinco operaciones de suma/resta, una menos que la evaluación sencilla. Además se guardó la multiplicación por 4 en el cálculo de p (−2).
A diferencia de multiplicar los polinomios p (·) y q (·), multiplicar los valores evaluados p ( a ) y 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 cambiará a la multiplicación larga del libro de texto . Sea r el polinomio producto, en nuestro ejemplo tenemos:
Como se muestra, estos también pueden ser negativos. Para números suficientemente grandes, este es el paso más caro, 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 puntos d en el polinomio producto r (·), necesitamos determinar sus coeficientes. En otras palabras, queremos resolver esta ecuación matricial para el vector del lado derecho:
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 así:
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 enteros, solo sumas, restas y multiplicación/división por pequeñas constantes. 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:
Ahora conocemos nuestro polinomio producto r :
Si estuviéramos usando diferentes k m , k n o puntos de evaluación, la matriz y, por tanto, nuestra estrategia de interpolación cambiarían; pero no depende de las entradas y, por lo tanto, puede codificarse para cualquier conjunto de parámetros determinado.
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 desplazamientos de un número entero de dígitos en base b . En el ejemplo actual b = 10 4 y B = b 2 = 10 8 .
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 .
Toom-1 ( k m = k n = 1) requiere 1 punto de evaluación, aquí elegido como 0. Degenera a una multiplicación larga, con una matriz de interpolación de la matriz identidad:
Toom-1.5 ( k m = 2, k n = 1) requiere 2 puntos de evaluación, aquí elegidos como 0 y ∞. Su matriz de interpolación es entonces la matriz identidad:
Esto también degenera en una 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, aquí elegidos como 0, 1 y ∞. Es lo mismo que la multiplicación de Karatsuba , con una matriz de interpolación de:
Toom-2.5 ( k m = 3, k n = 2) requiere 4 puntos de evaluación, aquí elegidos como 0, 1, −1 y ∞. Luego tiene una matriz de interpolación de:
