La forma perfecta de multiplicar

El 18 de marzo, dos investigadores describieron el método más rápido jamás descubierto para multiplicar dos números muy grandes. Su artículo es la culminación de una larga búsqueda del procedimiento más eficiente para realizar una de las operaciones más básicas de las matemáticas. 

«Todo el mundo piensa que el método que se aprende en la escuela es el mejor, pero en realidad esa es un área activa de investigación», dice Joris van der Hoeven, matemático del Centro Nacional Francés de Investigación Científica y uno de los coautores.

La complejidad de muchos problemas computacionales, desde calcular nuevos dígitos de π hasta encontrar grandes números primos, depende, en esencia, de la velocidad a que se multiplique. Según Van der Hoeven, su resultado no consiste sino en establecer una especie de límite matemático de velocidad que afecta a la rapidez con que se pueden resolver muchos otros tipos de problemas.

«En física hay constantes importantes, como la velocidad de la luz, que permiten describir todo tipo de fenómenos», explica Van der Hoeven. «Si se quiere saber con qué rapidez pueden los ordenadores resolver ciertos problemas matemáticos, la multiplicación de números enteros se presentará como una especie de bloque básico con respecto al cual se podrán expresar las velocidades correspondientes».

Casi todo el mundo aprende a multiplicar de la misma manera: se pone un número sobre otro, se multiplica cada dígito del número inferior por cada dígito del número superior y se hace la suma al final. Si se multiplican dos números de dos dígitos, se habrán realizado cuatro multiplicaciones más pequeñas para llegar al producto final.

El método del colegio, el de «llevar», requiere alrededor de n² pasos, donde n es el número de dígitos de los números que se estén multiplicando: los de tres dígitos requieren nueve multiplicaciones, mientras que los de 100 requieren 10.000. 

El método de llevar números funciona bien mientras haya solo unos pocos dígitos, pero se atasca cuando multiplicamos números con millones o miles de millones de dígitos (que es lo que hacen las computadoras para calcular con precisión π o como parte de la búsqueda mundial de primos grandes). Multiplicar dos números con mil millones de dígitos requiere mil millones de multiplicaciones al cuadrado (es decir, 10¹⁸), lo que le llevaría unos treinta años a una computadora moderna.

Durante milenios se dio por sentado que no había una manera más rápida de multiplicar. Pero en 1960 un matemático ruso de 23 años de edad, Anatoly Karatsuba, asistió a un seminario dirigido por Andrei Kolmogorov, uno de los grandes matemáticos del siglo XX. Kolmogorov afirmó que no había un procedimiento general para realizar la multiplicación que requiera menos de n² pasos. Karatsuba pensó que sí, y tras una semana de búsca lo encontró.

El método de Karatsuba consiste en fragmentar la serie de dígitos de un número y recombinarlos de una manera nueva, de modo que un pequeño número de sumas y restas haga lo mismo que un gran número de multiplicaciones. El método ahorra tiempo porque la adición sólo requiere 2n pasos, en lugar de n^2.

«Con las sumas, en el colegio se puede hacerlo un curso antes; es mucho más fácil, se puede hacerlo en tiempo lineal, casi tan deprisa como se leen los números de derecha a izquierda», dice Martin Fürer, matemático de la Universidad del Estado de Pensilvania que en 2007 creó el que en ese momento fue el algoritmo de multiplicación más rápido.

Cuando se trata de números grandes, se puede repetir el procedimiento de Karatsuba y fragmentar el número original en casi tantas partes como dígitos tenga. Y con cada fragmentación se reemplazan las multiplicaciones que requieren muchos pasos con sumas y restas que requieren mucho menos.

«Se pueden convertir algunas de las multiplicaciones en adiciones: la idea es que las computadoras suman más deprisa que multiplican», como dice David Harvey, matemático de la Universidad de Nueva Gales del Sur y coautor del nuevo artículo.

El método de Karatsuba hizo posible multiplicar los números realizando solamente n^1.58 multiplicaciones de un solo dígito. Luego, en 1971, Arnold Schönhage y Volker Strassen publicaron un método que multiplicaba grandes números con n × log n × log(log n) pasos multiplicativos, donde log n es el logaritmo de n. Para dos números de mil millones de dígitos, el método de Karatsuba requeriría unos 165 billones de pasos adicionales. 

El método de Schönhage y Strassen, el que aplican los ordenadores para multiplicar números enormes, tuvo otras dos consecuencias que serían importantes a largo plazo. En primer lugar, introdujo el uso de una técnica que se aplicaba al procesamiento de señales, la transformada rápida de Fourier. Ha sido la base de todos los algoritmos de multiplicación rápida desde entonces.

En segundo lugar, Schönhage y Strassen conjeturaron en ese mismo artículo que debería haber un algoritmo aún más rápido que el que encontraron, un método que solo necesitase n × log n operaciones de un solo dígito, y que un algoritmo así sería el más rápido posible. Su conjetura se basaba en una intuición: que una operación tan fundamental como la multiplicación debía tener un límite más elegante que n x log n x log(log n).

«Había una especie de consenso general en que la multiplicación es una operación básica tan importante que, aunque solo sea desde un punto de vista estético, ha de tener una cota de complejidad bonita», según Fürer. «La experiencia general enseña que las matemáticas de las cosas básicas al final resulta ser elegante».

El método de Schönhage y Strassen, con su desmañado n x log n x log(log n), aguantó 36 años. En 2007, Fürer lo batió y se abrieron las compuertas de par en par. En los últimos diez años se han ido encontrando algoritmos para la multiplicación cada vez más rápidos, cada uno un poco más cercano que los anteriores a n x log n pero sin llegar a alcanzarlo. Hasta que en marzo Harvey y Van der Hoeven lo lograron.

Su método refina el gran trabajo que lo precedió. Fragmenta los dígitos, se vale de una versión mejorada de la transformada rápida de Fourier y saca partido de otros avances de los últimos cuarenta años. «Usamos [la transformada rápidad de Fourier] de una manera mucho más violenta, la usamos varias veces en vez de una sola, y reemplazamos todavía más multiplicaciones con adiciones y sustracciones», explica Van der Hoeven.

El algoritmo de Harvey y Van der Hoeven prueba que la multiplicación se puede hacer en n x log n pasos. Sin embargo, no prueba que no haya una forma más rápida; establecer que ese método es el mejor posible resulta mucho más difícil. A finales de febrero, un equipo de científicos de la computación de la Universidad de Aarhus prepublicaba un artículo en arXiv donde argumentaban que si otra conjetura aún no demostrada es cierta, no hay, en efecto, forma más veloz de multiplicar.

Y si bien el nuevo algoritmo es importante teóricamente, en la práctica no va a producir grandes cambios, pues solo es ligeramente mejor que los algoritmos que ya se utilizan. «Lo máximo que podemos esperar es que seamos tres veces más rápidos», afirma Van der Hoeven. «No será espectacular».

Además, el diseño físico de los ordenadores ha cambiado. Hace veinte años realizaban la adición mucho más deprisa que la multiplicación. La diferencia de velocidad entre ambas operaciones ha disminuido considerablemente desde entonces, hasta el punto de que la arquitectura de algunos chips hace que la multiplicación sea aún más rápida que la adición. Hay diseños físicos con los que «en realidad se puede sumar más deprisa diciéndole al ordenador que haga un problema de multiplicación, lo que es de locos», según Harvey.

El hardware cambia con los tiempos, pero los mejores algoritmos de su clase son eternos. Sean como sean los ordenadores del futuro, el algoritmo de Harvey y Van der Hoeven seguirá siendo la forma más eficiente de multiplicar.

Kevin Hartnett / Quanta Magazine

Artículo traducido por Investigación y Ciencia con permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión de la ciencia.

Referencia: «Integer multiplication in time O(n log n)», de David Harvey y Joris Van der Hoeven en HAL archives ouvertes, hal-02070778.