Hace CUATRO MIL AÑOS , los babilonios inventaron la multiplicación. El mes pasado, los matemáticos lo perfeccionaron.
El 18 de marzo, dos investigadores describieron el método más rápido jamás descubierto para multiplicar dos números muy grandes . El documento marca la culminación de una búsqueda de larga duración para encontrar el procedimiento más eficiente para realizar una de las operaciones más básicas en matemáticas .
«Todos piensan básicamente que el método que aprendes en la escuela es el mejor, pero en realidad es un área activa de investigación», dijo Joris van der Hoeven , matemática del Centro Nacional de Investigaciones Científicas de Francia que fue coautora del documento.
La complejidad de muchos problemas de cálculo , desde calcular nuevos dígitos de pi hasta encontrar números primos grandes, se reduce a la velocidad de la multiplicación. Van der Hoeven describe su resultado como un tipo de límite de velocidad matemática para la rapidez con la que se pueden resolver muchos otros tipos de problemas.
«En física, tienes constantes importantes, como la velocidad de la luz, que te 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 aparece como una especie de ladrillo de construcción básico con respecto al cual puedes expresar ese tipo de velocidades».
La mayoría de todos aprenden a multiplicarse de la misma manera. Apilamos dos números, multiplicamos cada dígito en el número inferior por cada dígito en el número superior, y hacemos suma al final. Si estás multiplicando dos números de dos dígitos, terminas realizando cuatro multiplicaciones más pequeñas para producir un producto final.
El método de la escuela primaria o «llevar» requiere aproximadamente n 2 pasos, donde n es el número de dígitos de cada uno de los números que estás multiplicando. Así que los números de tres dígitos requieren nueve multiplicaciones, mientras que los números de 100 dígitos requieren 10.000 multiplicaciones.
El método de transporte funciona bien para números con solo unos pocos dígitos, pero se atasca cuando estamos multiplicando números con millones o billones de dígitos (que es lo que hacen las computadoras para calcular con precisión pi o como parte de la búsqueda mundial de números primos grandes ) . Multiplicar dos números con mil millones de dígitos requiere 10 18 multiplicaciones (1 mil millones de cuadrados), lo que llevaría a una computadora moderna aproximadamente 30 años.
Durante milenios se asumió ampliamente que no había una manera más rápida de multiplicarse. Luego, en 1960, el matemático ruso de 23 años Anatoly Karatsuba tomó un seminario dirigido por Andrey Kolmogorov, uno de los grandes matemáticos del siglo XX. Kolmogorov afirmó que no había ningún procedimiento general para hacer la multiplicación que requiriera menos de n 2 pasos. Karatsuba pensó que había, y después de una semana de búsqueda, lo encontró.
El método de Karatsuba consiste en dividir los dígitos de un número y combinarlos de una manera novedosa que le permita sustituir un pequeño número de sumas y restas por un gran número de multiplicaciones. El método ahorra tiempo porque la suma solo toma 2 n pasos, en lugar de n 2 pasos.
Cuando se trata de números grandes, puede repetir el procedimiento de Karatsuba, dividiendo el número original en casi tantas partes como dígitos. Y con cada división, reemplazas las multiplicaciones que requieren muchos pasos para calcular con sumas y restas que requieren mucho menos.
«Puede convertir algunas de las multiplicaciones en adiciones, y la idea es que las adiciones sean más rápidas para las computadoras», dijo David Harvey , matemático de la Universidad de Nueva Gales del Sur y coautor del artículo.
El método de Karatsuba hizo posible multiplicar números usando solo n 1.58 multiplicaciones de un solo dígito. Luego, en 1971, Arnold Schönhage y Volker Strassen publicaron un método capaz de multiplicar números grandes en n × log n × log (log n ) pasos multiplicativos, donde log n es el logaritmo de n . Para dos números de 1 billón de dígitos, el método de Karatsuba requeriría unos 165 billones de pasos adicionales.
El método de Schönhage y Strassen, que es la forma en que las computadoras multiplican los números enormes, tuvo otras dos consecuencias importantes a largo plazo. Primero, introdujo el uso de una técnica del campo del procesamiento de señales llamada transformada rápida de Fourier. La técnica ha sido la base para cada algoritmo de multiplicación rápida desde entonces.
Segundo, en ese mismo documento, Schönhage y Strassen conjeturaron que debería haber un algoritmo aún más rápido que el que encontraron, un método que solo necesita n × log n operaciones de un solo dígito, y que tal algoritmo sería el más rápido posible. Su conjetura se basó en el presentimiento de que una operación tan fundamental como la multiplicación debe tener un límite más elegante que n × log n × log (log n ).
«Fue una especie de consenso general que la multiplicación es una operación básica tan importante que, solo desde un punto de vista estético, una operación tan importante requiere una buena complejidad», dijo Fürer. «De la experiencia general, las matemáticas de las cosas básicas al final siempre resultan ser elegantes».
El método de n × log n × log (log n ) de Schönhage y Strassen se mantuvo durante 36 años. En 2007 Fürer lo venció y se abrieron las compuertas. 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 ha acercado a n × log n , sin llegar a alcanzarlo. Luego, el mes pasado, Harvey y van der Hoeven llegaron allí.
Su método es un refinamiento de la obra principal que vino antes de ellos. Divide los dígitos, utiliza una versión mejorada de la rápida transformación de Fourier y aprovecha otros avances realizados en los últimos 40 años. «Usamos [la transformada rápida de Fourier] de una manera mucho más violenta, la usamos varias veces en lugar de una sola vez, y reemplazamos incluso más multiplicaciones con sumas y restas», dijo van der Hoeven.
El algoritmo de Harvey y van der Hoeven demuestra que la multiplicación se puede realizar en n × log n pasos. Sin embargo, no prueba que no haya una manera más rápida de hacerlo. Establecer que este es el mejor enfoque posible es mucho más difícil. A fines de febrero, un equipo de científicos informáticos de la Universidad de Aarhus publicó un documento en el que argumentaba que si otra conjetura no probada también es cierta, esta es la manera más rápida de hacer la multiplicación.
Y si bien el nuevo algoritmo es teóricamente importante, en la práctica no cambiará mucho, ya que solo es ligeramente mejor que los algoritmos que ya se están utilizando. «Lo mejor que podemos esperar es que somos tres veces más rápidos», dijo van der Hoeven. «No será espectacular».
Además, el diseño del hardware de la computadora ha cambiado. Hace dos décadas, las computadoras funcionaban mucho más rápido que la multiplicación. La brecha de velocidad entre la multiplicación y la adición se ha reducido considerablemente en los últimos 20 años hasta el punto en que la multiplicación puede ser incluso más rápida que la adición en algunas arquitecturas de chips. Con algo de hardware, «en realidad podría hacer una adición más rápida si le dice a la computadora que haga un problema de multiplicación, lo cual es una locura», dijo Harvey.
El hardware cambia con los tiempos, pero los mejores algoritmos de su clase son eternos. Independientemente de cómo se vean las computadoras en el futuro, el algoritmo de Harvey y van der Hoeven seguirá siendo la forma más eficiente de multiplicar.
Fuente: www.wired.com.
