Dos matemáticos de Australia y Francia han creado una novedosa forma de multiplicar números, al tiempo que han resuelto un rompecabezas algorítmico que dejaría, como mínimo, desconcertadas a algunas de las más grandes mentes de las matemáticas de hace casi medio siglo.

Multiplicar números pequeños puede ser muy fácil. ¿Pero qué pasa si los números se hacen más grandes? Bueno, si las cifras se hacen pesadas la mayoría de nosotros pasaríamos a la multiplicación larga: otro truco útil que aprendimos en la escuela y una técnica fiable para multiplicar básicamente dos números juntos. Pero la multiplicación larga tiene un problema: es lenta.

Más significativamente, es un problema para los ordenadores, ya que sus propios cuellos de botella en la realización de cálculos vienen impuestos por los límites de las matemáticas abstractas que nosotros mismos podemos entender.

Básicamente, la multiplicación larga es un algoritmo, pero no es especialmente eficiente, porque el proceso es inevitablemente laborioso.

LEA TAMBIÉN: Las matemáticas tienen por fin una explicación científica de por qué se agrietan las articulaciones

Resulta que los matemáticos han descubierto una nueva forma de calcular la dificultad de la multiplicación larga.

Como explica el matemático David Harvey, de la UNSW (Australia), en una multiplicación en la que ambos números tienen tres dígitos ( n = 3), el número de operaciones de multiplicación separadas es en realidad 9, que es n 2:

A medida que aumentan los números, también aumenta la cantidad de trabajo, que siempre se representa con n a la potencia de 2.

Aunque ineficiente, el algoritmo de la multiplicación larga era en realidad el algoritmo de multiplicación más avanzado que teníamos hasta la década de 1960, cuando el matemático ruso Anatoly Karatsuba descubrió que n 1,58 era posible.

Una década más tarde, dos matemáticos alemanes hicieron otro descubrimiento: el algoritmo de Schönhage-Strassen, que conjeturaba -pero nunca demostró- que también eran posibles otros refinamientos.

"Predijeron que debería haber un algoritmo que multiplicara números de n dígitos utilizando esencialmente operaciones básicas de n * log ( n )", explica Harvey.

"Nuestro trabajo ofrece el primer ejemplo conocido de un algoritmo que lo consigue".

Según los investigadores, multiplicar dos números con mil millones de dígitos cada uno mediante el largo proceso de multiplicación llevaría meses.

Utilizando el algoritmo de Schönhage-Strassen, se tardaría menos de 30 segundos, y con la prueba teórica , sería incluso más rápido -teóricamente- y podría incluso representar el algoritmo de multiplicación más rápido matemáticamente posible.

LEA TAMBIÉN: Las matemáticas pueden ayudar a predecir cómo se desarrollan las células cancerosas

"En ese sentido, nuestro trabajo es, con suerte, el final del camino para este problema, aunque todavía no sabemos cómo demostrarlo rigurosamente", dice Harvey .

"La gente ha estado buscando ese algoritmo durante casi 50 años, no era con una conclusión inevitable que alguien acabaría teniendo éxito".

Cabe destacar que el nuevo algoritmo sólo sería útil para multiplicar números muy grandes. ¿Cómo de grandes exactamente?

"No tenemos ni idea", explican los investigadores en una pregunta frecuente, aunque un ejemplo que dan en el artículo es 10 214857091104455251940635045059417341952 , que es un número muy, muy, muy grande. La comunidad matemática mundial aún está asimilando los nuevos hallazgos, que todavía deben ser revisados por pares.

El propio Fürer intentó reformular el algoritmo de Schönhage-Strassen hace más de una década, pero finalmente abandonó el trabajo, ya que dijo que "parecía bastante inútil".

"Si el resultado es correcto, es un gran logro en la teoría de la complejidad computacional", dijo a la New Scientist o El matemático e informático Fredrik Johansson, del INRIA de Burdeos y del Instituto de Matemáticas de Burdeos.

LEA TAMBIÉN: La definición del kilogramo ha cambiado para siempre. Ahora se basa en la física cuántica

"Es probable que los nuevos conocimientos de este trabajo inspiren nuevas investigaciones y puedan conducir a mejoras prácticas en el futuro".

Mientras tanto, Harvey y su co-investigador, Joris van der Hoeven, de la École Polytechnique de Francia, dicen que su algoritmo necesita ser optimizado, y sólo esperan haber revelado algo en sus pruebas.

"Gran parte del trabajo consistió en convencernos de que es realmente correcto", dijo Harvey a AAP, "todavía tengo miedo de que pueda acabar saliendo mal".

Los resultados están disponibles en el archivo de acceso abierto HAL .

FUENTE / Alerta científica