Hasta ahora todos los métodos de multiplicar números de \(n\) cifras tardan un tiempo del orden de \(n(\log n) f(n)\) siendo \(f(n)\) una función que tiende a infinito con \(n\) más lentamente que \(\log n\). Una conjetura de Schönhage y Strassen afirma que cualquier método de multiplicación necesitará al menos \(n(\log n)\). Acaba de publicarse un algoritmo para multiplicar precisamente en tiempo del orden de \(n(\log n)\). ¡Ya sabemos multiplicar! Este mes hemos aprendido a multiplicar eficientemente.
Los autores son David Harvey de la Universidad de New South Wales en Sydney y Joris Van Der Hoeven del Laboratoire d’informatique de l’École polytechnique. Comentamos hoy su proeza.
No deja de ser sorprendente que el nuevo método sea tan enormemente complicado. Queda la tarea ingente de simplificarla
Este es un paso de gigante en la solución de una de las cuestiones básicas de las matemáticas y que lleva milenios pendiente. El algoritmo usual, que aprendimos en la escuela, tarda un tiempo del orden de \(n^2\). Pero los ordenadores ya hace tiempo que no usan el método primitivo más que para multiplicar números pequeños. Para multiplicar números grandes usan unas implementaciones libres (GNU Multiple Precision Arithmetic Library) del segundo algoritmo de Schönhage-Strassen que data del año 1971. Este algoritmo multiplica en un tiempo del orden de \(n(\log n)(\log\log n)\).
Schönhage y Strassen en 1971 ya conjeturaron que el tiempo realmente necesario debe ser \(n\log n\), (el tiempo necesario para realizar una operación de transformada de Fourier rápida con los datos del problema). Si esta conjetura es cierta tenemos ya el algoritmo definitivo desde el punto de vista de la eficacia teórica.
Debemos explicar en este punto la dificultad de probar que necesitamos realmente un tiempo del orden \(n\log n\). Una cosa es imaginar un algoritmo y estudiar concretamente cuanto tiempo tarda este algoritmo (esto es lo que se acaba de hacer). Otra, muy distinta, es imaginar una tarea en abstracto (en este caso multiplicar dos números) y probar que cualquier método que la realice necesitará un tiempo (en este caso \(n\log n\)). La dificultad es que no sabemos cuál es el algoritmo.
Idea general de los algoritmos para multiplicar.
Nuestro problema es multiplicar números enteros. Estamos interesados en algoritmos que lo hagan lo más rápidamente posible. Esto depende del tamaño de los números. Por eso precisamos el problema y lo que queremos es multiplicar números de \(n\) cifras y lo que nos interesa realmente es como se complica la tarea cuando aumenta \(n\). Medimos esta complicación dando una idea de como crece el tiempo necesario para realizar la tarea.
El algoritmo que aprendimos en la escuela es muy adecuado para números de pocas cifras. Pero hay métodos mejores. Todos estos métodos tienen unas características comunes que vamos a analizar:
Recurrencia.
Todos estos métodos reducen el producto de los dos números de \(n\) cifras a un determinado número de productos de números menores.
Por ejemplo el método usual reduce el producto a \(n^2\) productos de números de una cifra. Después los resultados deben sumarse adecuadamente, pero esto es una tarea relativamente menor. Luego si \(M(n)\) denota el tiempo necesario para multiplicar dos números de \(n\) cifras obtenemos $$M(n)<n^2 M(1).$$ Esto es general, cualquier método nos da una recurrencia que permite después dar una cota de \(M(n)\). En este caso, para el algoritmo usual, \(M(n)\) es del orden de \(n^2\).
Ya vimos en otra entrada: Multiplicar es más fácil de lo que piensas, cómo el algoritmo de Karatsuba reduce el producto de dos números de \(n\) cifras a tres productos de números de \(n/2\) cifras y un resto debido a las sumas con lo que $$M(n)<3M(n/2)+ an$$ Lo que permite reiterando el proceso obtener cualquier producto en un tiempo \(n^{1.58496}\) mucho más rápido que el usual.
Los otros métodos que se conocen, hacen uso de varias ideas.
Producto de Polinomios.
La primera idea, que ya explicamos entonces, se basa en que cada número escrito en el sistema decimal es el valor de un polinomio \(p(x)\) en \(x=10\). Por ejemplo \(237= 2\cdot 10^2+3\cdot 10+7=p(10)\) siendo \(p(x)=2x^2+3x+7\). De este modo podemos reducir multiplicar dos números al problema de multiplicar dos polinomios. (Ver la entrada anterior Multiplicar es más fácil de lo que piensas, para una explicación más detallada.)
Transformada de Fourier rápida.
Para obtener el producto \(C(x)=A(x)B(x)\) de dos polinomios de grado \(n\), podemos seguir la estrategia de calcular en \(n+1\) puntos \(m_k=A(x_k) B(x_k)\) y conociendo esto buscar el polinomio \(C(x)\) tal que cumpla las ecuaciones \(C(x_k)=m_k\). Esto parece más complicado que hacer el producto directamente. Pero si escogemos \(x_k\) las \(n+1\) raíces \(n+1\)-ésimas de la unidad, calcular \(A(e^{2\pi ik/(n+1)})\) es calcular la transformada de Fourier de los coeficientes de \(A\). Resulta que hay un procedimiento, descubierto por Gauss, que permite realizar estas operaciones en tiempo \(n\log n\). Es la transformada de Fourier rápida FFT (por sus siglas en inglés).
Todos los métodos realmente rápidos que se conocen dependen de la FFT. De aquí surge la conjetura de que lo más que podemos aspirar es a un método del orden de \(n\log n\). También está sostenida por el hecho de que esta cota inferior se ha probado en el caso de la multiplicación on-line, aquella en que el \(k\)-ésimo bit del producto debe escribirse antes de que el \((k+1)\)-ésimo bit de los factores sea leído.
El juego de los anillos.
Vemos que hemos pasado del problema de multiplicar enteros (elementos del anillo \(\textbf{Z}\) de los números enteros), al problema de multiplicar polinomios (elementos del anillo \(\textbf{Z}[x]\)). Después al usar las raíces de la unidad, hemos transformado el producto a producto en el anillo de los números complejos \(\textbf{C}\)).
Pero el álgebra está repleta de anillos interesantes. Y la historia de los métodos de multiplicación, ha sido también una historia de anillos protagonistas.
Las últimas ideas consisten en usar anillos en donde existan raíces de la unidad más simples que el anillo de los complejos.
Métodos de multiplicación anteriores.
El primer método de Schönhage-Strassen.
Esencialmente el que hemos descrito. Convierte el producto en un producto de polinomios, con coeficientes de tamaño \(\log n\). Y usa las raíces de la unidad de \(\textbf{C}\), para realizar la FFT Esto conduce a la recurrencia $$M(n)\ll n M(\log n)+ n\log n.$$ (\(\ll\) quiere decir que es \(\le \), salvo que debemos añadir un factor constante en el lado derecho de la desigualdad).
Esta recurrencia conduce a un tiempo del tipo \(M(n)\approx (n\log n) f(n)\) donde \(f(n)\) es una función complicada de \(n\), que tiende a infinito con \(n\), pero más lentamente que el logaritmo.
Segundo método de Schönhage-Strassen.
Es el que se utiliza actualmente en los ordenadores. Se sustituye \(\textbf{C}\) por el anillo \(R_h=\textbf{Z}/(2^h+1)\textbf{Z}\) de los restos módulo \(2^h+1\). Este anillo tiene raíces de la unidad adecuadas para realizar la FFT. Para multiplicar números de \(n\) cifras se reduce el problema a multiplicar polinomios \(R_h[x]\) cuyo grado es del orden de \(\sqrt{n}\) y se toma \(h\) también de orden \(\sqrt{n}\).
En este caso llegamos a la cota \(M(n)\approx n\log n\log\log n\).
Hay otros métodos posteriores que mejoran la función \(f(n)\) en \(M(n)\approx (n\log n) f(n)\), usando otros anillos que combinan las mejores características de los dos métodos anteriores.
El nuevo método.
Polinomios de varias variables.
El nuevo método introduce dos ideas. La primera usar un anillo de polinomios en varias variables del tipo $$R[x_1,\dots, x_d]/(x_1^{t_1}-1, \dots x_d^{t_d}-1), \qquad R=\textbf{C}[y]/(y^r+1),$$ donde \(r=2^h\) es una potencia de \(2\) y \(t_j\mid 2r\) lo son también. En estos anillos el producto no requiere más que sumas y restas (no productos) en \(\textbf{C}\), el cuerpo de los números complejos. Pero notar que usando la FFT con las raíces de la unidad, no las de \(\textbf{C}\) sino las que vienen de los \(y^{2r/t_j}\). Estos anillos habían sido considerados antes por Nussbaumer en el final de los años 70 del pasado siglo.
Pero queda el problema de como convertimos el problema de la multiplicación de enteros, para usar estos anillos de muchas variables. Lo que hacemos es buscar primos \(s_1\), \(\dots\), \(s_d\) cada uno de tamaño \((n/\log n)^{1/d}\) y tales que el producto \(s_1\cdots s_d\approx (n/\log n)\). De la manera habitual reducimos el problema a multiplicar polinomios de grado \(s_1\cdots s_d\) y coeficientes de tamaño \(\log n\). Usando el teorema chino del resto, gracias a que los \(s_j\) son primos, vemos que $$\textbf{Z}[x]/(x^{s_1\dots s_d}-1)$$ es isomorfo a $$\textbf{Z}[x_1,\dots, x_d]/(x_1^{s_1}-1, \dots, x_d^{s_d}-1).$$ De este modo pasamos el problema a uno de multiplicar polinomios en varias variables.
Gaussian Resampling.
Finalmente queda el problema que la FFT debe usar potencias de \(2\) y los primos \(s_j\) no lo son. Creo que esta es la idea más sorprendente del método.
Los coeficientes de nuestros polinomios, al ser de varias variables dependen de \(d\) números $$\sum_{n_i} c(n_1,n_2, \dots, n_d) x^{n_1} x^{n_2}\dots x^{n_d},$$ donde \(0\le n_i\le s_i\). Queremos hacer una transformada de Fourier de estos coeficientes \(c(n_1,n_2, \dots, n_d)\). Nuestro problema es que quisiéramos que las \(s_i\) fueran potencias de \(2\) (caso en que el método de la FFT funciona bien), pero son primos distintos de cierto tamaño.
Para ver más simplemente lo que hacen, pensemos en el caso simple de ser \(d=2\). En ese caso podemos pensar que nuestros datos \(c(n_1,n_2)\), son valores de una función en los puntos de un retículo contenido en un rectángulo de tamaño \(s_1\times s_2\). Es como si tuviéramos los valores de una función tomados en un retículo de \(s_1\times s_2\) puntos igualmente espaciados.
En su trabajo ellos ponen el ejemplo de \(s_1\times s_2=13\times11\). En la figura nuestros \(c(n_1,n_2)\) corresponden a los datos en los círculos blancos. Superponen un retículo de tamaño \(16\times 16\) (los círculos negros en la figura) y asocian a cada uno de estos puntos un valor que es combinación lineal de los valores \(c(n_1,n_2)\) en los puntos blancos próximos. Ellos toman pesos gaussianos de manera que cada nuevo coeficiente depende esencialmente solo de los muy cercanos.
A continuación obtienen la transformada de estos nuevos valores (a los que sí se puede aplicar la FFT). Demuestran que con ellos se puede reconstruir una aproximación suficiente de la transformada original.
Es curioso que tienen que hacer uso del teorema de los números primos para escoger los primos \(s_j\), próximo cada uno a \(t_j\) una potencia de \(2\). Para ello deben usar un teorema de J. B. Rosser y L. Schoenfeld de 1962. Rosser y Schoenfeld usaron los resultados conocidos en aquel momento acerca de que los primeros ceros de la función zeta están situados en la recta crítica.
De manera que el algoritmo presentado necesita usar de los cálculos de los primeros ceros de la función zeta para justificar que procesa en el tiempo requerido.
Naturalmente el método no es práctico tal como está ahora. La ventaja sobre el segundo método de Schönhage-Strassen: \(n\log n\) frente a \(n\log n\log\log n\) es demasiado pequeña. Tal como lo describen el nuevo algoritmo es de difícil implementación práctica. Hay mucho que simplificar hasta que el método sea práctico, si llega a serlo algún día.
Para saber más.
El artículo es difícil de leer, tiene mucha dificultad técnica. Pero para el que lo quiera ver está disponible libre en la red:
David Harvey, Joris Van Der Hoeven, Integer multiplication in time \(O(n\log n)\).
Hay todavía poca repercusión en la red, pero Richard Lipton ya tiene una entrada en su conocido blog «Gödel’s Lost Letter and P=NP: Integer multiplication in NlogN Time.
Dejar una contestacion