Un par de matemáticos de Australia y Francia han ideado una forma alternativa de multiplicar números juntos, mientras resuelven un rompecabezas algorítmico que ha dejado perplejas a algunas de las mejores mentes matemáticas durante casi medio siglo.
Para la mayoría de nosotros, la forma en que multiplicamos números relativamente pequeños es recordando nuestro tablas de tiempos – Una ayuda increíblemente útil creada por primera vez por los babilonios hace unos 4.000 años.
Pero, ¿y si los números aumentan? Bueno, si las cifras se vuelven difíciles de manejar, y suponiendo que no tengamos una calculadora o computadora, por supuesto, la mayoría de nosotros recurriría a la multiplicación larga: otro truco útil que aprendemos en la escuela y una técnica confiable para multiplicar básicamente dos Números juntos.
Solo hay un problema con la multiplicación larga. Es lento.
La razón por la que es l enta es porque por cada dígito en cada número en el problema, debe realizar una operación de multiplicación por separado, antes de sumar todos los productos.
Esto podría no ser un problema para usted y para mí, que probablemente rara vez recurramos a la multiplicación larga. Pero es un inconveniente con el que los niños de la escuela están familiarizados, trabajando penosamente en sus cálculos mientras aprenden la magia de la multiplicación.
Más significativamente, es un problema para las computadoras, ya que sus propios cuellos de botella al realizar los cálculos están impuestos por los límites de las matemáticas abstractas que nosotros mismos podemos comprender.
Básicamente, la multiplicación larga es un algoritmo, pero no es particularmente eficiente, ya que el proceso es inevitablemente laborioso.
En realidad, los matemáticos tienen una forma de calcular solo cómo la multiplicación larga y minuciosa es.
Como el matemático David Harvey de UNSW en Australia explica en el video a continuación, en una multiplicación donde ambos números tienen 3 dígitos (norte
El problema con esto es que a medida que los números aumentan, la cantidad de trabajo involucrado aumenta también, siempre representada por norte al poder de 2.
Si bien es ineficiente, el algoritmo de multiplicación larga fue en realidad el algoritmo de multiplicación más avanzado que tuvimos hasta la década de 1960, cuando el matemático ruso Anatoly Karatsuba descubierto ese norte1,58 Fue posible.
Una década después, un par de matemáticos alemanes hicieron otro gran avance: el Algoritmo de Schönhage-Strassen, que conjeturó, pero nunca demostró, que también era posible realizar más ajustes.
"Predijeron que debería existir un algoritmo que multiplique nortenúmeros de dígitos usando esencialmente norte * Iniciar sesión(norte) operaciones básicas," Harvey explica.
"Nuestro artículo da el primer ejemplo conocido de un algoritmo que logra esto".
Según los investigadores, multiplicar dos números junto con mil millones de dígitos cada uno por el proceso de multiplicación larga tomaría una computadora meses para calcular.
Usando el algoritmo de Schönhage-Strassen, tomaría menos de 30 segundos, y con su prueba teórica, sería aún más rápido, teóricamente, e incluso puede representar el algoritmo de multiplicación más rápido que sea matemáticamente posible.
"En este sentido, se espera que nuestro trabajo sea el final del camino para este problema, aunque todavía no sabemos cómo demostrarlo rigurosamente". Harvey dice.
"La gente ha estado buscando un algoritmo de este tipo durante casi 50 años. No era una conclusión falsa que alguien finalmente sería exitoso".
Vale la pena señalar que el nuevo algoritmo solo sería útil para multiplicar números muy grandes. ¿Qué tan grande exactamente?
"No tenemos idea", los investigadores explicar en un FAQ, aunque un ejemplo que dan en el documento equivale a 10214857091104455251940635045059417341952, que es un número muy, muy, muy grande.
La comunidad matemática del mundo todavía está absorbiendo los nuevos hallazgos, que aún no se han revisado por pares, pero ya están haciendo olas.
"Me sorprendió mucho que se hubiera hecho", dijo el científico teórico Martin Fürer de la Universidad Penn State. dicho Noticias de ciencia.
Fürer mismo trató de renovar el algoritmo de Schönhage-Strassen hace más de una década, pero finalmente interrumpió el trabajo, contando Noticias de ciencia, "Me pareció bastante desesperado".
Pero la esperanza se ha restablecido, siempre que los matemáticos puedan verificar el trabajo.
"Si el resultado es correcto, es un logro importante en la teoría de la complejidad computacional", dijo el matemático e informático Fredrik Johansson del INRIA Bordeaux y el Institut de Mathématiques de Bordeaux. Científico nuevo.
"Las nuevas ideas en este trabajo probablemente inspirarán más investigación y podrían conducir a mejoras prácticas en el futuro".
Mientras tanto, Harvey y su co-investigador, Joris van der Hoeven de la École Polytechnique en Francia, dicen que su algoritmo necesita ser optimizado, y solo esperan no haber acumulado algo en su prueba.
"Gran parte del trabajo fue convencernos de que en realidad es correcto", Harvey le dijo a AAP. "Todavía estoy aterrorizado de que pueda resultar incorrecto".
Los hallazgos previos a la impresión están disponibles en Archivo de acceso abierto HAL.
Una versión de esta historia se publicó por primera vez en abril de 2019.