- Multiplicar números grandes es difícil. En 1971, dos profesores alemanes predijeron un algoritmo que lo haría más fácil, pero nadie lo demostró nunca.
- Hasta ahora.
- Los matemáticos de Australia y Francia dicen que su algoritmo puede hacer que la multiplicación y otros tipos de aritmética sean mucho más eficientes.
Desde la escuela primaria, la multiplicación compleja ha sido un dolor de cabeza. Pero un profesor asistente de la Universidad de Nueva Gales del Sur de Sidney, en Australia, ha desarrollado un nuevo método para multiplicar números gigantes juntos que es más eficiente que la «multiplicación larga» que se enseña a muchos a una edad temprana.
«Más técnicamente, hemos demostrado una conjetura de 1971 de Schönhage y Strassen sobre la complejidad de la multiplicación de números enteros», dice el profesor asociado David Harvey en el vídeo de abajo.
El algoritmo de Schönhage-Strassen, desarrollado por dos matemáticos alemanes, fue en realidad el método más rápido de multiplicación desde 1971 hasta 2007. Aunque en 2007 se desarrolló un método más rápido, rara vez se utiliza hoy en día.
Schönhage y Strassen predijeron que debía existir un algoritmo que multiplicara números de n dígitos utilizando n * log(n) operaciones básicas, dice Harvey. Su artículo es la primera prueba conocida de que existe.
Harvey escoge el ejemplo de 314 multiplicado por 159 -una ecuación grande, sin duda, pero las más grandes se utilizan todos los días en la vida real. Para resolver el problema, a la mayoría de la gente se le enseña a multiplicar cada uno de los números por separado y luego a sumarlos:
9 se multiplica por 4, 1 y 3; luego 5 se multiplica por 4, 1 y 3, y así sucesivamente. El resultado termina con 9 productos dígitos por dígitos.
Este método se llama n2 o n al cuadrado, porque hay que multiplicar n por n un número de veces. Obtendrá la respuesta correcta, pero Schönhage y Strassen diseñaron un método más rápido. Fue capaz de ir más allá de n2 y llegar a algo más pequeño, pero todavía se presentaba un reto en forma de n * log(n).
Para algunos, ver una palabra en medio de un problema matemático puede ser suficiente para que se les pongan los ojos como en la clase de álgebra. Para refrescar la memoria: log es la abreviatura de logaritmo, que ayuda a la gente a descifrar los exponentes que hacen que los números se eleven al cuadrado o al cubo o incluso algo más. Así que 2⁵ es 32, pero expresado logarítmicamente, sería log₂(32)=5. Aunque parezca un trabalenguas, los logaritmos son cruciales cuando los números son mucho más grandes.
El método de Schönhage-Strassen es muy rápido, dice Harvey. Si un ordenador utilizara el método del cuadrado que se enseña en la escuela en un problema en el que dos números tuvieran mil millones de dígitos cada uno, tardaría meses. Un ordenador que utilizara el método de Schönhage-Strassen podría hacerlo en 30 segundos.
Pero si los números siguen aumentando hasta los trillones y más allá, el algoritmo desarrollado por Harvey y su colaborador Joris van der Hoeven en la École Polytechnique de Francia podría encontrar soluciones más rápidamente que el algoritmo de Schönhage-Strassen de 1971.
«Significa que puedes hacer todo tipo de aritmética de forma más eficiente, por ejemplo la división y las raíces cuadradas», dice. «También se pueden calcular los dígitos de pi de forma más eficiente que antes. Incluso tiene aplicaciones a problemas relacionados con números primos enormes.
«La gente ha estado buscando un algoritmo así durante casi 50 años», continúa. No era una conclusión inevitable que alguien acabara teniendo éxito. Podría haber resultado que Schönhage y Strassen estaban equivocados, y que tal algoritmo no es posible.
«Pero ahora lo sabemos mejor», dice.