La multiplicación de Toom-Cook, también conocida como Toom-3, es un algoritmo de multiplicación para enteros grandes. Debe su nombre a Andréi Toom, quien introdujo el nuevo algoritmo por su baja complejidad, y a Stephen Cook, quien pulió su descripción.
Dados dos enteros grandes, a y b, el procedimiento consiste en dividir a y b en k partes más pequeñas, cada una de longitud l, y realizar operaciones sobre estas partes. A medida que k aumenta, se pueden combinar muchas de las suboperaciones de multiplicación, reduciendo así la complejidad computacional total 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 indistintamente, Toom-3 es solo un caso particular del algoritmo de Toom-Cook, para el que k = 3.
Toom-3 reduce nueve multiplicaciones a cinco y se ejecuta en .
En general, Toom- se ejecuta en , donde , es el tiempo empleado en submultiplicaciones y es el tiempo empleado en sumas y multiplicaciones por constantes pequeñas (Knuth, pág. 296).
El algoritmo de Karatsuba es equivalente a Toom-2, donde el número se divide en dos números más pequeños.
Reduce cuatro multiplicaciones a tres y, por lo tanto, opera en .
Aunque el exponente puede ajustarse arbitrariamente cerca de 1 incrementando , el término constante de la función crece muy rápidamente.Knuth, p. 296Crandall & Pomerance, p. 474 La tasa de crecimiento para los esquemas de Toom-Cook de niveles mixtos seguía siendo un problema de investigación abierto en 2005.Crandall & Pomerance, p. 536 Una implementación descrita por Donald Knuth alcanza la complejidad temporal .Knuth, p. 302
Debido a su sobrecarga, el algoritmo de Toom-Cook es más lento que la multiplicación larga con números pequeños, por lo que se suele utilizar para multiplicaciones de tamaño intermedio, antes de que el método asintóticamente más rápido, el algoritmo de Schönhage-Strassen (con complejidad ) resultase 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.Positive Results, chapter III of Stephen A. Cook: On the Minimum Computation Time of Functions.
Detalles En esta sección se explica cómo realizar la operación Toom-k para cualquier valor dado de k, y es una simplificación de la descripción de la multiplicación de polinomios de Toom-Cook descrita por Marco Bodrato.Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In WAIFI'07 proceedings, volume 4547 of LNCS, pages 116–133. June 21–22, 2007. author website El algoritmo consta de cinco pasos principales: Separación Evaluación Multiplicación punto por punto Interpolación Recomposición
En una aplicación típica con enteros grandes, cada entero se representa como una secuencia de dígitos en notación posicional, con la base o radix establecida en algún valor b (generalmente grande). Para este ejemplo, se usa b = 10000, de modo que cada dígito corresponde a un grupo de cuatro dígitos decimales (en una aplicación informática, b suele ser una potencia de 2). Supóngase que los dos enteros que se multiplican son:
m=1234567890123456789012n=987654321987654321098.
Estos números son mucho más pequeños de lo que normalmente se procesarían con el algoritmo de Toom-Cook (la multiplicación en la escuela primaria sería más rápida), pero servirá para ilustrar el algoritmo.
Sedparación En el algoritmo Toom-k, se separan los factores en k partes.
El primer paso es seleccionar la base B = bi, de manera que el número de dígitos de m y 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:
En el presente ejemplo, se trabajará con Toom-3, así que se elige . A continuación, se separan m y n en sus dígitos de base B: mi, ni:
Luego se usan estos dígitos como coeficientes en los polinomios de grado 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 se puede calcular su producto , la respuesta será .
En el caso de que los números que se multiplican sean de diferente magnitud, es útil usar distintos valores de k para m y n, que denominaremos km y kn. Por ejemplo, el algoritmo "Toom-2.5" se refiere al Toom-Cook con km = 3 y kn = 2. En este caso, la i en B = bi se suele elegir mediante:
Evaluación
El método de Toom-Cook para calcular el producto polinómico es de uso común. Cabe destacar que un polinomio de grado se determina unívocamente mediante puntos (por ejemplo, un polinomio de línea de grado uno se especifica mediante dos puntos). La idea consiste en evaluar y en varios puntos. Luego, se multiplican sus valores en estos puntos para obtener puntos sobre el polinomio producto. Finalmente, se interpola para hallar sus coeficientes.
Dado que , se necesitan puntos para determinar el resultado final. Se denomina a este resultado . En el caso de Toom-3, . El algoritmo funcionará independientemente de los puntos elegidos (con algunas excepciones menores; véase el requisito de invertibilidad de la matriz de interpolación), pero para simplificarlo, es mejor elegir valores enteros pequeños como 0, 1, -1 y -2.
Un valor de punto inusual que se usa con frecuencia es el infinito, escrito como o . "Evaluar" un polinomio en el infinito significa, en realidad, tomar el límite de cuando tiende a infinito. Por consiguiente, siempre es el valor de su coeficiente de mayor grado (en el ejemplo anterior, el coeficiente ).
En el presente ejemplo de Toom-3, se usan los puntos , , , y . Estas opciones simplifican la evaluación, generando las fórmulas:
y de forma análoga para . En nuestro ejemplo, los valores obtenidos son:
Como se muestra, estos valores pueden ser negativos.
Para una explicación posterior, será útil considerar 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 x km para p y d x kn para q. La fila correspondiente al infinito siempre contiene ceros, excepto un 1 en la última columna.
Evaluación más rápida 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 proporcionada por Bodrato 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 directa. Además, se evitó la multiplicación por en el cálculo de .
Multiplicación punto a punto A diferencia de la multiplicación de los polinomios y , la multiplicación de los valores evaluados y solo implica la multiplicación de enteros (una instancia más pequeña del problema original). Se invoca recursivamente el 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á al procedimiento de multiplicación larga. Sea r el polinomio producto, entonces se tiene que:
Como se muestra, estos valores también pueden ser negativos. Para números suficientemente grandes, este es el paso más costoso, el único que no es lineal con respecto a los tamaños de y .
Interpolación Este es el paso más complejo, el inverso del paso de evaluación: dados los puntos en el polinomio producto , se necesita determinar sus coeficientes. En otras palabras, se quiere 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 por ser . Se podría resolver esta ecuación con una técnica como la eliminación de Gauss-Jordan, pero esto es demasiado costoso. En cambio, se aprovecha el hecho de que, siempre que los puntos de evaluación se elijan adecuadamente, esta matriz es invertible (véase también matriz de Vandermonde), y por lo tanto:
Solo queda calcular este producto matriz-vector. Aunque la matriz contiene fracciones, los coeficientes resultantes serán enteros. Por lo tanto, todo se puede realizar con aritmética de enteros, simplemente sumas, restas y multiplicaciones/divisiones por constantes pequeñas. Un desafío de diseño complejo en el algoritmo de Toom-Cook es encontrar una secuencia eficiente de operaciones para calcular este producto. Una secuencia proporcionada por Bodrato para Toom-3 es la siguiente, ejecutada aquí sobre el ejemplo en ejecución:
Ahora se conoce el polinomio producto :
Si se utilizaran diferentes , o puntos de evaluación, la matriz y, por lo tanto, la estrategia de interpolación cambiaría. Pero no depende de las entradas, por lo que puede codificarse directamente para cualquier conjunto de parámetros.
Recomposición Finalmente, se evalúa r(B) para obtener la 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 = 104 y B = b2 = 108.
| || || || || || || || ||3084||8414||8617||5176 |- | || || || || || ||6740||4157||2123||7444|| || |- | || || || ||3422||4165||8197||1852|| || || ||
|align=right| 13||1284||3338||7466|| || || || || || |- | + ||121||9313||1840|| || || || || || || || |- |colspan=100| |- | ||121||9326||3124||6761||1632||4937||6009||5208||5858||8617||5176
Y este es, de hecho, el producto de 1234567890123456789012 y 987654321987654321098.
Descomposición asimétrica El paso de interpolación depende del grado del polinomio producto, que es la suma de los grados de los polinomios factoriales, pero no de los grados individuales. Si bien el método básico Toom-3 divide cada factor en 3 partes (polinomio cuadrático), si los factores difieren en tamaño, puede ser beneficioso dividir uno en 2 partes (una función lineal) y el otro en 4 partes (una cúbica) con coeficientes de tamaño más equilibrado. Entonces, el mismo paso de interpolación puede producir un polinomio producto cuadrático.
Para Toom-3, esta es la única división alternativa interesante (el caso degenerado de la separación de cualquiera de los factores en una sola parte no ofrece ahorro de tiempo), pero un algoritmo de Toom-Cook de mayor grado permite posibilidades adicionales.
Además de los casos de separación equitativa, es posible tener casos con semienteros, que siempre son asimétricos. El número total de partes es impar y el grado del polinomio producto es par. Por ejemplo, Toom-2.5 separa un factor en 2 partes y el otro en 3, mientras que Toom-3.5 puede separar los factores como 2+5 o 3+4.
Matrices de interpolación para varios k Aquí se muestran matrices de interpolación comunes para algunos valores pequeños comunes de km y kn.
Toom-1 Aplicando formalmente la definición, se puede considerar Toom-1 (km = kn = 1). Esto no resulta en un algoritmo de multiplicación, sino en 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 un punto de evaluación, cuyo valor es irrelevante, puesto que solo se utiliza para "evaluar" polinomios constantes. Por lo tanto, la matriz de interpolación es la matriz identidad:
Toom-1.5 Toom-1.5 (km = 2, kn = 1) sigue siendo degenerado: reduce recursivamente una entrada a la mitad, pero deja la otra sin cambios. Por lo tanto, solo se puede convertirlo en un algoritmo de multiplicación si se proporciona 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 y 8. Su matriz de interpolación es la matriz identidad: