Multiplicación de Comba

La multiplicación de Comba (también conocida como algoritmo de Comba) es un procedimiento matemático ideado por Paul G. Comba para optimizar el cálculo del producto de dos números cuando se necesita que el resultado contenga todas sus cifras significativas. Está inspirado en el procedimiento que se utiliza para realizar multiplicaciones con papel y lápiz.

Historia

El artículo en el que se describe el algoritmo fue publicado en 1990 por el matemático italoestadounidense Paul G. Comba en la revista IBM Systems Journal.​

Sin embargo, existen referencias anteriores a un procedimiento con puntos en común denominado reducción de Barrett​ (publicado en 1986),​ e incluso mucho más antiguas, en la Aritmética de Treviso de 1478.

Utilidad

El algoritmo se diseñó para cuando es necesario manejar números muy grandes con todas sus cifras significativas, como en el caso de los procesos de encriptación mediante claves privadas y públicas, donde es habitual operar con números primos con centenares de cifras significativas.

Cuando el algoritmo fue publicado a comienzos de la década de 1990, los procesadores usuales disponibles (del tipo Intel 8086) no estaban optimizados para realizar determinadas operaciones, y el procedimiento de Comba podía implicar reducciones del tiempo de cálculo necesario de hasta un 30%.​

Idea básica

Comba sabía que muchos programadores que necesitaban realizar cálculos con números de "precisión múltiple" (los ordenadores manejan con soltura números de precisión simple y de precisión doble, pero no son capaces de operar directamente con números de centenares de cifras significativas), diseñaban rutinas para multiplicar que reproducían los procedimientos utilizados manualmente con papel y lápiz, utilizando las posiciones de memoria de una matriz para almacenar el resultado.

El método manual clásico de multiplicar, cuando se aplica a un ordenador, consiste en descomponer los dos números del producto (en sus correspondientes unidades, decenas, centenas, millares, con valores comprendidos entre el 0 y el 9); multiplicarlos ordenadamente uno a uno según la columna que ocupan; y almacenar los resultados en la matriz de memoria, teniendo en cuenta las llevadas.

Tras analizar esta rutina, Comba se dio cuenta de que el proceso de acumular las llevadas a cada paso complicaba los cálculos, y que resultaba mucho más eficiente almacenar los resultados intermedios sin descomponer (guardando los dos dígitos del cálculo intermedio), realizando la acumulación de las llevadas al final.

Ejemplo

Supóngase que se desea multiplicar 23 por 89:​

Método normal: Método normal: 2 3 x 8 9 ======= 2_0_7 1_8_4 ======= 2_0 4 7 Comba observó que este orden de cálculo produce demasiadas llevadas de una posición de dígitos a la siguiente (cada subrayado entre dígitos denota un acarreo o llevada), y esto es costoso computacionalmente, requiriendo instrucciones y registros adicionales. En este ejemplo, no tiene mucho sentido que haya 5 acarreos, cuando el resultado final solo tiene 4 dígitos.

Método de Comba: Método de Comba: 2 3 x 8 9 =========== 18 27 16 24 =========== 2 _0 _4 _7 Comba también observó que se podían evitar las llevadas entre los resultados intermedios, computándose todas a la vez en la etapa final. Esto tiene un costo: los resultados intermedios tienen ahora dos dígitos en vez de uno en cada columna. De esta forma, todos los acarreos de columna a columna se llevan a cabo en el resultado final.

Enlaces externos

• Explicación completa del algoritmo de Comba (en inglés)

• Datos: Q28375325