web analytics

Archivo de septiembre 4th, 2019

Los secretos de la multiplicación perfecta

En una entrada previa reseñamos el excelente libro de Raúl Ibáñez Torres dedicado a desvelar los secretos de la multiplicación. Esa multiplicación que viene de tiempos antiguos pero que encierra todavía muchos secretos más, como los recientes resultados de David Harvey y Joris van der Hoeven (Integer multiplication in time O(n log n))   han puesto de manifiesto.

Joris van der Hoeven

David Harvey

En un artículo de marzo en Quantamagazine, la revista divulgativa que la filantropía de Jim Simons ha ofrecido al colectivo matemático mundial, el periodista Kevin Hartnett se hacía eco de estos descubrimientos: Mathematicians Discover the Perfect Way to Multiply . Sin duda alguna que la publicación del libro de Raúl Torres es un momento perfecto para recordar estos hechos.

Digamos en primer lugar que ese algoritmo para la multiplicación que parece tan simple y que aprendemos en la escuela, es hoy en día un tema de investigación relevante. La razón es que muchos de los cálculos que se hacen con los ordenadores se basan en la multiplicación, de manera que cuanto más rápidos sean los cálculos de las multiplicaciones, más rápides y exactos serán los que hacemos por ejemplo para calcular nuevos números primos.

Si recordamos el algoritmo para la multiplicación (veáse este video, por ejemplo)

Imagen de previsualización de YouTube

Sabemos que si multiplicar dos números de 2 cifras precisa de 4 productos, si son de 3, entonces necesitaríamos 9 productos parciales, y en general, si son dos números uno de n cifras y otro de m, estaríamos hablando de nm. Y si n y m son muy grandes, entonces nos daremos cuenta de la complejidad del cálculo (un ordendor podría precisar de años para terminar estas multiplicaciones gigantescas).

Si queremos multiplicar dos números de n cifras, necesitamos n2 productos parciales. En 1952, el matemático ruso Andrey Kolmogorov intentó probar que el algoritmo usual era óptimo asintóticamente, o, en lenguaje coloquial, esta era la mejor manera de multiplicar. En otoño de 1960, Kolmogorov organizó un seminario en Moscú sobre las matemáticas de la computación: Este tema de la multiplicación fue uno de ellos, y para sorpresa de Kolmogorov, n estudiante de 25 años, Anatolii Alexeevitch Karatsuba, encontró un algoritmo que mejoraba la hipótesis de Kolmogorov. Este video explica el método de Karatsuba

Imagen de previsualización de YouTube

El método ideado por Karatsuba se podría llamar de “dibvide y vencerás”, ya que, como se ve en el video, se tarta de descomponer los dos grandes números en trozos pequeños y operar con ellos.

A.A. Karatsuba

Eeste método fue mejorado en 1971 por Arnold Schönhage y Volker Strassen, quiénes conjeturaron que debería haber alguno mejor que el suyo. Y ese ha sido el logro de Harvey y van der Hoeven, usando la transformada rápida de Fourier, un sofisticado y utílisimo instrumento matemático. El resultado es teórico y la mejora real es pequeña, pero nos sirve para demostrar que incluso los temas que parecen resueltos, esconden secretos que los matemáticos seguimos investigando.

___

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias).

Etiquetas: ,
Categorias: General