## 2.1.1 MULTIPLICACIÓN ENTERA

Cuando un cálculo requiere manipular enteros muy grandes, puede suceder que los operandos se vuelvan demasiado largos para almacenarlos en una sola palabra de la computadora que se está utilizando. Por tanto tales operaciones dejan de ser elementales. Cuando sucede esto, se puede utilizar la aritmética de precisión múltiple. Ahora debemos preguntarnos cómo aumenta el tiempo necesario para sumar, restar, multiplicar, o dividir dos enteros muy grandes con el tamaño de los operandos. Podemos medir este tamaño bien por el número de palabras de computadora necesarias para representar los operandos en una máquina o bien por la longitud de su representación en decimal o en binario. Puesto que estas medidas difieren sólo por una constante multiplicativa, esta opción no altera nuestro análisis del orden de eficiencia de los algoritmos en cuestión.Consideraremos solamente la operación de multiplicación.

El análisis de las suma y de la resta es mucho más sencillo. Supóngase que hemos de multiplicar dos enteros grandes de tamaño m y n respectivamente. El algortimo clásico, multiplica cada cifra de uno de los operandos por la cifra del otro, y ejecuta aproximadamente una adición elemental para cada una de estas multiplicaciones. En una máquina multiplicamos cada palabra de uno de los operandos por cada palabra de la otra, y después hacemos aproximadamente una adición de longitud doble para cada una de estas multiplicaciones, pero el principio es exactamente el mismo. El tiempo requerido es por tanto del orden mn.

Para ver como funciona este método, primero vamos utilizar un ejemplo en base 10 para luego cambiarlo a base 2. Supongamos que tenemos que multiplicar 36×217. Lo que normalmente hacemos es lo siguiente:

36
× 217
252
36
72
7812

Lo que estamos haciendo es descomponer la multiplicación de la siguiente forma: 36×217= 36×7 + (36×1)×10 + (36×2)×100. El algoritmo sería el siguiente: tomamos el primer dígito del multiplicador y realizamos la operación, seguimos con el segundo dígito y hacemos lo mismo pero el resultado lo movemos un lugar a la izquierda (lo desplazamos), nos vamos al último dígito, realizamos la misma operación y el resultado lo movemos dos lugares. Podemos seguir con este proceso en caso de que el número contenga más dígitos. Al final sólo necesitamos sumar todos los resultados para obtener toda la multiplicación.
Haciendo de manera similar en base 2, lo que efectuamos es descomponer la multiplicación de la siguiente manera: 36×217 = 36×1 + (36×0)×2 + (36×0)×4 + (36×1)×8 + (36×1)×16 + (36×0)×32 + (36×1)×64 + (36×1)×128. Como podemos apreciar, dentro de los paréntesis sólo multiplicamos ya sea por uno o por cero, por lo que en realidad no necesitamos efectuar la operación. En caso de multiplicar por uno el resultado es el mismo, y en caso multiplicar por cero el resultado es cero.
Ahora lo que nos interesa es multiplicar por las potencias, lo cual podemos conseguir fácilmente. Empezando por 1, las siguientes potencias las obtenemos multiplicando por dos la potencia anterior, pero está operación la podemos cambiar por un corrimiento a la izquierda.
El tiempo de ejecución de este algoritmo es de O(n2), donde n es la cantidad de bits del número. Esto sin importar en que base trabajemos, ya que al efectuar la multiplicación necesitamos recorrer todos los dígitos de los dos números. La ventaja de la base 2 es que el costo de las operaciones es mucho menor.

Existen algoritrmos más eficientes para resolver el problema de la multiplicación de dos enteros muy grandes, como el algoritmo Divide y vencerás.

El primero de ellos es la multiplicación de Karatsuba, que utiliza una estrategia “divide y vencerás”, y con el cual se obtiene un tiempo de ejecución de O(n1.58). Este método se basa en que si tenemos dos números x e y, los podemos descomponer de la siguiente forma x = x1b + x0 e y = y1b + y0. Habitualmente, lo que hacemos al multiplicar es x×y = (x1b + x0) × (y1b + y0) = x1y1b2 + (x1y0 + x0y1)b + x0y0. No obstante, esto lo podemos reacomodar de la siguiente forma x×y = (b2 + b)x1y1 -b(x1 – x0)(y1 – y0) + (b + 1)x0y0. Con esto, logramos efectuar sólo tres multiplicaciones mientras que si multiplicáramos de la forma convencional tendríamos que hacer cuatro. Para hacer las operaciones correspondientes podemos utilizar los algoritmos que ya tenemos.

Existen algoritmos más sofisticados, y el más rápido en la actualidad requiere un tiempo del orden de n log n para multiplicar dos enteros de tamaño n. Sin embargo estos algoritmos más sofisticados son en su mayor parte de interés teórico; las constantes ocultas son tales que solamente llegan a ser competitivos para operandos mucho más grandes. Para casos pequeños que multipliquen operandos de unos pocos miles de dígitos, resultan considerablemente más lentos que los algoritmos mencionados arriba.

###