Al dividir números grandes en números pequeños, los investigadores excedieron el límite matemático fundamental de velocidad
Hace cuatro mil años, los habitantes de
Babilonia inventaron la multiplicación. Y en marzo de este año, los matemáticos lo mejoraron.
El 18 de marzo de 2019, dos investigadores
describieron el método más rápido conocido de multiplicar dos números muy grandes. El trabajo marca la culminación de una larga búsqueda del procedimiento más eficiente para realizar una de las operaciones básicas de las matemáticas.
"Todos piensan que el método de multiplicación que enseñaron en la escuela es el mejor, pero de hecho, se está realizando una investigación activa en esta área", dice
Joris van der Hoeven , matemático del Centro Nacional de Investigación Científica de Francia, uno de los coautores del trabajo.
La complejidad de muchos problemas computacionales, desde contar nuevos dígitos del número π hasta encontrar números primos grandes, se reduce a la tasa de multiplicación. Van der Hoeven describe su resultado como una asignación de una especie de límite de velocidad matemática para resolver muchos otros problemas.
"En física, hay constantes importantes, como la velocidad de la luz, que le 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 surge en forma de un bloque de construcción básico, con respecto al cual puedes expresar tal velocidad".
Casi todos aprenden a multiplicar números de la misma manera. Escribimos los números en una columna, multiplicamos el número superior por cada dígito de la parte inferior (teniendo en cuenta los dígitos) y sumamos el resultado. Cuando multiplica dos números de dos dígitos, debe hacer cuatro multiplicaciones más pequeñas para obtener el resultado final.
El método escolar de "
transferencia " requiere n
2 pasos, donde n es el número de dígitos en cada uno de los números multiplicados. Los cálculos con números de tres dígitos requieren nueve multiplicaciones, y con números de un dígito, 10,000.
El método de transferencia funciona bien con números que consisten en varios dígitos, sin embargo, comienza a deslizarse al multiplicar números que consisten en millones o miles de millones de dígitos (que es lo que hacen las computadoras al calcular con precisión π o al
buscar números primos
grandes en todo el mundo ). Para multiplicar dos números con mil millones de dígitos, necesitará producir mil millones al cuadrado, o 10
18 , multiplicaciones; esto tomará aproximadamente 30 años para una computadora moderna.
Durante varios milenios, se creía que los números no podían multiplicarse más rápido. Luego, en 1960, el matemático ruso y soviético de 23 años
Anatoly Alekseevich Karatsuba asistió a un seminario dirigido por
Andrei Nikolayevich Kolmogorov , un matemático soviético, uno de los mejores matemáticos del siglo XX. Kolmogorov declaró que no existe un método generalizado de multiplicación que requiera menos de n
2 operaciones. Karatsuba decidió que existía tal método, y después de una semana de búsqueda lo descubrió.
Anatoly Alekseevich KaratsubaLa multiplicación de Karatsuba consiste en dividir los dígitos del número y repetir su combinación de una nueva manera, lo que permite, en lugar de una gran cantidad de multiplicaciones, realizar menos sumas y restas. El método ahorra tiempo, ya que la suma solo toma 2n pasos en lugar de n
2 .
El método tradicional de multiplicación de 25x63 requiere cuatro multiplicaciones de un solo dígito y varias adiciones.
La multiplicación de Karatsuba 25x63 requiere tres multiplicaciones por un solo número y varias sumas y restas.
a) rompe los números
b) multiplicar decenas
c) multiplicar unidades
d) sumar los números
e) multiplique estas cantidades
f) considere e - b - c
g) recolectar el total de b, c y fA medida que aumenta el número de caracteres en números, el método Karatsuba se puede utilizar de forma recursiva.
El método tradicional de multiplicar 2531x1467 requiere 16 multiplicaciones por un solo dígito.
La multiplicación de Karatsuba 2531x1467 requiere 9 multiplicaciones."La adición en la escuela tiene lugar un año antes, porque es mucho más simple, funciona en tiempo lineal, con la velocidad de leer números de izquierda a derecha", dijo
Martin Fuhrer , matemático de la Universidad Estatal de Pensilvania, quien creó el algoritmo de multiplicación más rápido en 2007.
Cuando se trata de números grandes, la multiplicación de Karatsuba se puede repetir de forma recursiva, dividiendo los números originales en casi tantas partes como signos hay en ellos. Y con cada partición, cambia la multiplicación, que requiere muchos pasos, a sumas y restas, que requieren muchos menos pasos.
"Varias multiplicaciones pueden convertirse en adiciones, dado que las computadoras podrán hacerlo más rápido", dijo
David Harvey , matemático de la Universidad de Nueva Gales del Sur y coautor del nuevo trabajo.
El método Karatsuba hizo posible multiplicar números usando solo n
1.58 multiplicaciones por un solo dígito. Luego, en 1971, Arnold Schönhage y Volker Strassen publicaron un método para multiplicar números grandes por n × log n × log (log n) pequeñas multiplicaciones. Para multiplicar dos números de mil millones de caracteres, cada método Karatsuba requerirá 165 billones de pasos.
Joris van der Hoeven, matemático del Centro Nacional Francés de Investigación CientíficaEl método de Schönhage-Strassen es utilizado por las computadoras para multiplicar grandes números, y ha llevado a otras dos consecuencias importantes. Primero, introdujo una técnica del campo del procesamiento de señales llamada
Transformada rápida de Fourier . Desde entonces, esta técnica ha sido la base de todos los algoritmos de multiplicación rápida.
En segundo lugar, en el mismo trabajo, Schönhage y Strassen sugirieron la posibilidad de un algoritmo aún más rápido, un método que requiere solo n × log n multiplicaciones por un signo, y que dicho algoritmo sería el más rápido posible. Esta suposición se basó en la sensación de que para una operación tan fundamental como la multiplicación, la restricción de las operaciones debería escribirse de alguna manera más elegante que n × log n × log (log n).
"En general, se acordó que la multiplicación es una operación básica tan importante que, desde un punto de vista puramente estético, necesita una hermosa restricción de complejidad", dijo el Führer. "Por experiencia, sabemos que las matemáticas de las cosas básicas siempre terminan siendo elegantes".
La restricción incómoda de Schönhage y Strassen, n × log n × log (log n), duró 36 años. En 2007, el
Führer rompió este récord, y todo sucedió. Durante la última década, los matemáticos han encontrado algoritmos de multiplicación cada vez más rápidos, cada uno de los cuales se arrastró gradualmente hasta la marca n × log n, sin llegar a alcanzarla. Luego, en marzo de este año, Harvey y van der Hoeven lo alcanzaron.
Su método es una mejora en el gran trabajo realizado antes que ellos. Rompe los números en signos, usa una versión mejorada de la rápida transformación de Fourier y aprovecha otros avances logrados en los últimos 40 años. "Usamos la transformada rápida de Fourier mucho más bruscamente, la usamos varias veces, no solo una, y reemplazamos aún más multiplicaciones con suma y resta", dijo van der Hoeven.
El algoritmo de Harvey y van der Hooven demuestra que la multiplicación se puede hacer en n × log n pasos. Sin embargo, no prueba la ausencia de un método más rápido. Será mucho más difícil establecer que su enfoque sea lo más rápido posible. A finales de febrero, un equipo de informáticos de la Universidad de Aarhus
publicó un artículo en el que afirmaba que si uno de los teoremas no comprobados resulta ser cierto, este método será la forma más rápida de multiplicarse.
Y aunque en teoría este nuevo algoritmo es muy importante, en la práctica no cambiará mucho, ya que solo supera ligeramente a los algoritmos ya utilizados. "Todo lo que podemos esperar es una aceleración triple", dijo van der Hoeven. "Nada más allá".
Además, los circuitos de los equipos informáticos han cambiado. Hace veinte años, las computadoras realizaban la suma mucho más rápido que la multiplicación. La brecha en las tasas de multiplicación y suma ha disminuido desde entonces, como resultado de lo cual, en algunas fichas, la multiplicación puede incluso superar la suma. Usando ciertos tipos de equipos, "puede acelerar la suma obligando a la computadora a multiplicar números, y esto es una especie de locura", dijo Harvey.
El equipo cambia con el tiempo, pero los mejores algoritmos de su clase duran para siempre. No importa cómo se vean las computadoras en el futuro, el algoritmo Harvey y van der Hooven seguirá siendo la forma más eficiente de multiplicar números.