By: KEVIN HARTNETT
La mayoría de nosotros confiamos en el “método de carga” cuando multiplicamos. Pero hay una forma mucho más rápida de manejar grandes cantidades.
CUATRO MIL AÑOSHace, los babilonios inventaron la multiplicación. El mes pasado, los matemáticos lo perfeccionaron.
El 18 de marzo, dos investigadores describieron el método más rápido jamás descubierto para multiplicar dos números muy grandes . El documento marca la culminación de una búsqueda de larga duración para encontrar el procedimiento más eficiente para realizar una de las operaciones más básicas en matemáticas .
“Todo el mundo piensa básicamente que el método que aprendes en la escuela es el mejor, pero de hecho es un área activa de investigación”, dijo Joris van der Hoeven , matemático del Centro Nacional de Investigación Científica de Francia y coautor del artículo.
La complejidad de muchos problemas computacionales, desde calcular nuevos dígitos de pi hasta encontrar números primos grandes, se reduce a la velocidad de la multiplicación. Van der Hoeven describe su resultado como el establecimiento de una especie de límite de velocidad matemática para la rapidez con la que se pueden resolver muchos otros tipos de problemas.
“En física tienes constantes importantes como la velocidad de la luz que te permiten describir todo tipo de fenómenos”, dijo van der Hoeven. “Si quieres saber qué tan rápido las computadoras pueden resolver ciertos problemas matemáticos, entonces la multiplicación de enteros aparece como una especie de ladrillo de construcción básico con respecto al cual puedes expresar ese tipo de velocidades”.
Casi todo el mundo aprende a multiplicar de la misma forma. Apilamos dos números, multiplicamos cada dígito del número inferior por cada dígito del número superior y sumamos al final. Si está multiplicando dos números de dos dígitos, terminará realizando cuatro multiplicaciones más pequeñas para producir un producto final.
El método de la escuela primaria o de “llevar” requiere aproximadamente n 2 pasos, donde n es el número de dígitos de cada uno de los números que está multiplicando. Entonces, los números de tres dígitos requieren nueve multiplicaciones, mientras que los números de 100 dígitos requieren 10,000 multiplicaciones.
El método de transporte funciona bien para números con 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 pi o como parte de la búsqueda mundial de números primos grandes ). . Multiplicar dos números con mil millones de dígitos requiere 10 18 (mil millones al cuadrado), lo que a una computadora moderna le llevaría aproximadamente 30 años.
Durante milenios se asumió ampliamente que no había una forma más rápida de multiplicarse. Luego, en 1960, el matemático ruso Anatoly Karatsuba, de 23 años, asistió a un seminario dirigido por Andrey Kolmogorov, uno de los grandes matemáticos del siglo XX. Kolmogorov afirmó que no existía un procedimiento general para hacer la multiplicación que requiriera menos de n 2 pasos. Karatsuba pensó que sí, y después de una semana de búsqueda, lo encontró.
El método de Karatsuba implica dividir los dígitos de un número y recombinarlos de una manera novedosa que le permite sustituir una pequeña cantidad de sumas y restas por una gran cantidad de multiplicaciones. El método ahorra tiempo porque la suma toma solo 2 n pasos, en contraposición a n 2 pasos.
“Con la adición, lo haces un año antes en la escuela porque es mucho más fácil, puedes hacerlo en tiempo lineal, casi tan rápido como leer los números de derecha a izquierda”, dijo Martin Fürer , matemático de la Universidad Estatal de Pensilvania que en 2007 creó lo que era en ese momento el algoritmo de multiplicación más rápido.
Cuando se trata de números grandes, puede repetir el procedimiento de Karatsuba, dividiendo el número original en casi tantas partes como dígitos. Y con cada división, reemplaza las multiplicaciones que requieren muchos pasos para calcular con sumas y restas que requieren muchos menos.
“Puede convertir algunas de las multiplicaciones en sumas, y la idea es que las sumas sean más rápidas para las computadoras”, dijo 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 números usando solo n 1,58 multiplicaciones de un solo dígito. Luego, en 1971, Arnold Schönhage y Volker Strassen publicaron un método capaz de multiplicar números grandes en pasos multiplicativos n × log n × log (log n ), 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 alrededor de 165 billones de pasos adicionales.
El método de Schönhage y Strassen, que consiste en cómo las computadoras multiplican números enormes, tuvo otras dos importantes consecuencias a largo plazo. Primero, introdujo el uso de una técnica del campo del procesamiento de señales llamada transformada rápida de Fourier. La técnica ha sido la base de todos los algoritmos de multiplicación rápida desde entonces.
En segundo lugar, en ese mismo artículo, Schönhage y Strassen conjeturaron que debería haber un algoritmo aún más rápido que el que encontraron (un método que solo necesita n × log n operaciones de un solo dígito) y que dicho algoritmo sería el más rápido posible. Su conjetura se basaba en el presentimiento de que una operación tan fundamental como la multiplicación debe tener un límite más elegante que n × log n × log (log n ).
“Fue una especie de consenso general que la multiplicación es una operación básica tan importante que, solo desde un punto de vista estético, una operación tan importante requiere un límite de complejidad agradable”, dijo Fürer. “Por experiencia general, las matemáticas de las cosas básicas al final siempre resultan elegantes”.
El desgarbado método n × log n × log (log n ) de Schönhage y Strassen se mantuvo durante 36 años. En 2007, el Fürer lo derrotó y se abrieron las compuertas. Durante la última década, los matemáticos han encontrado algoritmos de multiplicación sucesivamente más rápidos, cada uno de los cuales se ha acercado poco a poco a n × log n , sin llegar a alcanzarlo. Luego, el mes pasado, Harvey y van der Hoeven llegaron allí.
Su método es un refinamiento del trabajo principal que les precedió. Divide dígitos, utiliza una versión mejorada de la transformada rápida de Fourier y aprovecha otros avances realizados durante los últimos 40 años. “Usamos [la transformada rápida de Fourier] de una manera mucho más violenta, la usamos varias veces en lugar de una sola vez, y reemplazamos aún más multiplicaciones con sumas y restas”, dijo van der Hoeven.
El algoritmo de Harvey y van der Hoeven demuestra que la multiplicación se puede hacer en n × log n pasos. Sin embargo, no prueba que no exista una forma más rápida de hacerlo. Establecer que este es el mejor enfoque posible es mucho más difícil. A finales de febrero, un equipo de científicos informáticos de la Universidad de Aarhus publicó un artículo en el que argumentó que si otra conjetura no probada también es cierta, esta es de hecho la forma más rápida en que se puede hacer la multiplicación.
Y aunque el nuevo algoritmo es importante en teoría, en la práctica no cambiará mucho, ya que es solo un poco mejor que los algoritmos que ya se están utilizando. “Lo mejor que podemos esperar es que seamos tres veces más rápidos”, dijo van der Hoeven. “No será espectacular”.
Además, el diseño del hardware informático ha cambiado. Hace dos décadas, las computadoras realizaban sumas mucho más rápido que la multiplicación. La brecha de velocidad entre la multiplicación y la suma se ha reducido considerablemente en los últimos 20 años hasta el punto en que la multiplicación puede ser incluso más rápida que la suma en algunas arquitecturas de chips. Con algo de hardware, “en realidad se podría hacer sumas más rápido diciéndole a la computadora que haga un problema de multiplicación, lo cual es una locura”, dijo Harvey.
El hardware cambia con los tiempos, pero los mejores algoritmos de su clase son eternos. Independientemente de cómo se vean las computadoras en el futuro, el algoritmo de Harvey y van der Hoeven seguirá siendo la forma más eficiente de multiplicar.
