Toda tu vida multiplicaste en forma ineficiente: El algoritmo de Karatsuba

Publicadas por


Multiplicar dos números enteros es un procedimiento que realizamos habitualmente. Con valores pequeños es un proceso mental automático. Si el requerimiento es con cantidades más grandes, nos podemos ayudar con lapiz y papel.... o le confiamos el resultado a una calculadora digital.

Aprendemos a multiplicar en la escuela primaria (elemental). El concepto es sumar "P" veces el número "Q" (suma reiterada) y lo expresamos mediante notación matemática como P x Q.  Cada vez que nos encontramos con la necesidad de este cálculo, utilizamos un procedimiento o algoritmo de multiplicación al que llamaremos "tradicional".

Tablas de multiplicar.
En el método tradicional, utilizando la numeración posicional arábiga con base 10 (existen diez símbolos y el número se compone de unidades, decenas, centenas.... etc de aquellos) debemos como prerequisito memorizar las tablas de multiplicar del 0 al 9. El procedimiento involucra emparejar los dos números y realizar multiplicaciones básicas entre cada dígito de cada número. Los resultados se van encolumnando.  Finalmente se realizan las adiciones columna a columna ("llevando 1 a la siguiente columna" cuando corresponda).

Este método no es el único conocido en la hitoria. Gracias al papiro de Rhind, descubierto por Alexander Henry Rhind en 1858 en Luxor (Egipto) conocemos como multiplicaban los antiguos egipcios. Tambien se ha podido reconstruir como multiplicaban los babilonios (que usaban 60 símbolos para la numeración). Cómo ejemplo de esto, la imagen que abre este artículo es una tabla de multiplicar babilonia en escritura coniforme (aquí más detalles). Además existen otros mecanismos que sobreviven en nuestros dias como la multiplicación japonesa (o china), el método hindú (o de celdillas) entre otros. Todos estos métodos tienen en comun que comparten la misma complejidad.


¿A que llamamos complejidad? Al tiempo que nos llevará resolver la operación (una ampliación de este concepto lo puede encontrar en el artículo "Comprendiendo la complejidad de los algoritmos mediante ejemplos simples"). Volvamos a la multiplicación tradicional para visualizarla. Supongamos que tengo que multiplicar los números P y Q.  Digamos que ambos números tienen "n" digitos. Usando nuestro método aprendido en la escuela, tendremos que realizar n^2 (n cuadrado) multiplicaciones básicas (recurriendo a nuestras tablas de multiplicar) y luego un número similar de sumas para calcular el resultado final.

Por ejemplo, queremos multiplicar 4572 con 3169 usando el método  numeros tietradicional. Estos números tienen 4 dígitos. Por lo que tendremos que realizar 16 multiplicaciones basicas y un número similar de sumas (en la imagen siguiente se pueden contabilizar).

Ejemplo de multiplicación
tradicional
Si el promedio de ejecución de cada mutiplicación lleva c1 y el de cada suma lleva c2. Podemos aproximar el tiempo promedio total del proceso en  c1*n^2 + c2*n^2. Tanto si utilizamos una computadora o realizandolo nosotros a mano, el tiempo que nos lleva multiplicar es mayor al de la suma. Por lo tanto para números con una cantidad de dígitos muy grande podremos aproximar, sin temer a un error muy grande, a c1*n^2. Es decir que el tiempo de ejecución de la multiplicación aumentará a razón del cuadrado de la cantidad de dígitos de los números a multiplicar.

Pero, ¿se puede realizar mejor?

Andrey Nikolaevich Kolmogorov (25 Abril de 1903 - 20 Octubre 1987) fue un matemático sovietico que tuvo un impacto en diferentes áreas de la ciencia (probabilidad, topología, complejidad computacional y teoría de la información entre otras). En sus presentaciones sobre complejidad de algoritmos solía utilizar como ejemplo el problema de la multiplicación. Dentro de su discurso proponía la conjetura n-cuadrado (más tárde también conocida como conjetura kolmogorov). En resumidas cuentas: La multiplicación conocida, que utilizaba promedio de n^2 multiplicaciones era lo más eficiente que se podía obtener.

Una inesperada caida de la conjetura.


Andrey Nikolaevich Kolmogorov
Una conjetura, en el lenguaje matématico (y también en el método científico) corresponde a una afirmación que se supone cierta pero que no ha podido ser ni probada ni refutada. En caso de ser probada pasa a ser un teorema y se puede utilizar dentro del andamiaje matemático (si se refuta pasa a ser desechada).

¿Cuál era su carta fuerte para esta afirmación? Consideraba la antiguedad del problema (milenios) y la necesidad económica que mueve a la humanidad para encontrar caminos que reduzcan su esfuerzo. En síntesis: Si existiese mejor método, ya tendría que haber sido encontrado.

Un análisis cercano a la proposición, develará que consiste en un Argumento ad ignorantiam. Es decir, una falacia que presupone que la falta de evidencias (o su ignorancia) en contra de la afirmación es prueba suficiente de la misma.

Se pueden encontrar en diferentes fuentes la defensa de la conjetura "Kolmogorov" en manos de su autor. Entre 1956 a 1960 la afirmó en donde pudo. Fue en otoño de 1960 en un seminario de problemas matemáticos en cibernetica, dictado en la Facultad de mecánica y matemáticas de la universidad de Moscu que la pronunció por última vez. Dentro de los presentes se encontraba un joven estudiante de 23 años a quien le bastó una semana para refutarla: Anatoly Karatsuba

Anatoly Karatsuba
Karatsuba presentó su descubrimiento al finalizar la siguiente reunión del seminario. Kolmogorov se mostró sumamente agitado. No solo su conjetura resultaba falsa, se habría un camino para repensar procesos matemáticos de miles de años. Kolgomorov, mismo se ocupó de comentar a los presentes en el seminario en la última reunión la noticia.  Dos años despues (1962) se publicaba "Multiplication of Many-Digital Numbers by Automatic Computers" en Proceedings of the USSR Academy of Sciences. Los autores de este paper eran A. Karatsuba y Yu. Ofman. Extrañamente, Karatsuba no tuvo nada que ver con la publicación y se enteró de la misma cuando ya estaba impresa. El responsable fue Kolmogorov, quien nunca explicó el motivo de este extraño comportamiento. En 1963 el artículo se tradujo del ruso y provocó una estampida matemática tanto en métodos de multiplicación como en otros que continua hasta nuestros dias.

¿Cómo funciona el algoritmos de Karatsuba?

El algoritmo de karatsuba para multiplicar divide el problema en subproblemas menores (Metodología conocido como division y conquista). En concreto, parte el problema de la multiplicación en sub problemas de multiplicación de menor cantididad de dígitos. Luego los resultados obtenidos los suma para construir la solución final.

Para eso, se ayuda de propiedades de la multiplicación. En primer lugar representando los números a multiplicar como la suma de números:

P*Q = (P1 + P2) * (Q1+Q2) = (p1*10^(n/2) + p2) * (q1*10^(n/2)+q2)

Donde n corresponde a la cantidad de dígitos de los números que multiplicamos.

En nuestro ejemplo anterior (n=4):

4572 * 3169 = (4500 + 72) * (3100 + 69) = (45*10^2 + 72) * (31*10^2 + 69)

Luego distribuye la multiplicación:

= (p1*q1)*10^n + (p1*q2 + p2*q1)*10^(n/2) + p2*q2

Nuevamente en el ejemplo:

= (45*31)*10^4 + (45*69 + 72*31)*10^2 + (72*69)

Se puede verificar sencillamente que el resultado es el mismo, tenemos 4 multiplicaciones y varias sumas que antes no teniamos. La complejidad no disminuyó (incluso aumento algo por agregado de sumas que antes no estaban). Aqui es donde aparece el truco de karatsuba (que se puede rastrear a un truco de Gauss para números complejos.

La idea es intentar reducir la cantidad de multiplicaciones de 4 a 3. Esto se logra viendo que:

 (p1+p2)*(q1+q2) = p1*q1 + p1*q2 + p2*q1 + p2*q2

Reagrupando podemos ver que, tenemos exactamente todas las multiplicaciones de nuestra ecuación:

(p1+p2)*(q1+q2) = p1*q1 + ( p1*q2 + p2*q1) + p2*q2

y por lo tanto, podemos despejando obtener:

( p1*q2 + p2*q1) = (p1+p2)*(q1+q2) - p1*q1 - p2*q2

Finalmente llevando esto a nuestra cuenta original:

= (p1*q1)*10^n + [(p1+p2)*(q1+q2) - p1*q1 - p2*q2]*10^(n/2) + p2*q2

Si se observa, se puede ver que p1*q1 y p2*q2 aparecen repetidos. Pero solo es necesario calcularlo 1 vez cada una. Por lo que, únicamente tenemos que realizar 3 multiplicaciones! (a costa de agregar sumas). Como habiamos dicho antes, las multiplicaciones son más costosas que la adición (lo que termina siendo una ganancia en complejidad para números de muchos dígitos).

Para resolver las 3 multipliciones que nos quedaron - a menos que sean multiplicaciones elementales que podemos resolver con nuestras tablas- aplicaremos este mismo método. Por lo tanto nos queda un proceso recursivo.

Karatsuba demostró que su solución terminaba realizando menos operaciones de multiplicación elementales que el método tradicional (obviamente agregando algunas operaciones de suma adicionales). En concreto contra el n-cuadrado (n^2) logra mejorar con n elevado al logaritmo en base 2 de 3 (n^[log_2(3)] = n^1,59). Lo que es una ganancia para nada despreciable.

Consecuencias:

El método de karatsuba fue una revolución. Matemáticos de todos el mundo se enfocaron en analizar que otros procesos matemáticos milenarios o centenarios se podían eficientizar (por ejemplo, se comenzó a buscar formas más eficiente de multiplicar matrices). Además, disparó una carrera para encontrar el nuevo límite de la multiplicación.

Entre los avances son dignos de nombrar a Toom y Cook en 1966 que extendieron las ideas de Karatsuba y consiguieron bajar la cota de complejidad. Dos años después, en 1971, lo mismo sucedió en manos de Schönhage y Strassen que aplicaron dentro elde su algoritmo el método "Fast Fourier transform" (FFT).

Schönhage y Strassen también proponen una nueva conjetura: el limite al que se puede llevar la eficiencia es n*log n.

El paso de los años a desplegado nuevos algoritmos que fueron aproximandose a la conjetura. Pero ha sido en el año 2019 cuando se presentó un nuevo método que lo ha alcanzado. Sus creadores: David Harvey y Joris van der Hoeven. El título de su publicación "Integer multiplication in time O(n log n) ". Para llegar a su resultado se apoyan en la FFT pero la llevan a 1729 dimensiones! (el procesamiento de images con formato JPEG "apenas" usa 2 dimensiones de la FFT).

¿Por que seguimos aprendiendo en las escuelas el método tradicional?


El método de Karatsuba saca ventajas al método tradicional a partir de muliplicar numeros de una cantidad de dígitos. Antes de eso es peor (o a lo sumo igual) que el método tradicional. Para los números que se usan en la escuela primaria e incluso secundaria no hay ganancia de tiempo en su aplicación. Es en números grandes, que se aprecia una diferencia.

Los lenguajes de programación que proveen librerias matemáticas para el manejo de enteros grandes implementan algunos de los métodos de multiplicación rápida. Incluso, implementan varios y deciden cual utilizar de acuerdo al tamaño del número en la operación. En métodos recursivos se puede dar un refinamiento donde a medida que se descompone los números en partes más pequeñas se van seleccionando inteligentemente que variante utilizar. Llegando incluso a utilizar la multiplicación standard cuando el número es lo suficientemente pequeño.  

El nuevo algoritmo requiere un número exorbitantemente grande para obtener una ventaja. Ganancia que incluso afirman los creadores no es tan grande en comparación a algunos de los últimos metodos generados. Pero el mérito absoluto es haber llegado a lo que hasta ahora se conjetura como el límite.

¿Será este el punto final a los esfuerzos de hallar métodos de multiplicación más eficientes? No ha sido demostrada la conjetura del límite. Los matemáticos siguen trabajando en ella. Ya sea que un algoritmo más veloz se encuentre o que finalmente se demuestre la validez, no queda otra más que esperar. O sumergirse en este mundo y tratar de buscar respuestas.

Lecturas adicionales sugeridas:

Comentarios

Publicar un comentario