MATDIS

1

Capítulo 11.

Algoritmos de multiplicación y división.
A continuación se estudiarán algoritmos para efectuar las operaciones de multiplicación y
división entera. Usualmente estas operaciones están soportadas por hardware dedicado,
adicional a la unidad aritmética que efectúa las operaciones básicas de sumar y restar números
con y sin signo. Al estudiar los algoritmos podrá advertirsela naturaleza secuencial de éstos, en
contraposición al carácter combinacional de las operaciones de suma y resta.

11.1. Multiplicación como suma repetitiva.
La operación de multiplicación se puede estudiar como la suma repetitiva del multiplicando las
veces que indique el multiplicador.
Por ejemplo la operación 7*3, en sistema binario puede realizarse según:
0111*0011 = 0111+0111+0111 =010101
Si los factores son de N cifras, el producto puede expresarse con 2N dígitos.
Con N=3 en sistema decimal se tiene que con operandos sin signo, el mayor factor es 999, y se
tiene que 999*999= 998.001 requiere 6 cifras.
Si se considera factores positivos, pero con signo, el mayor positivo es 499 y en este caso
también se requieren 6 dígitos para el producto: 499*499 = 249.001
Seconsidera:

Producto = Multiplicando * Multiplicador.

Sean P el producto, R el multiplicando y Q el multiplicador. Se define el multiplicador como el
factor que indica las veces que el multiplicando se ha de tomar como sumando. Y como
multiplicando al factor que ha de ser multiplicado.
Empleando el lenguaje C, puede describirse la idea anterior según:
/*Algoritmo a.
P y R de largo 2N. Q largo N.Sumador ancho 2N. */
/* Q y R positivos
P=R*Q
*/
for( j = Q; j>0 ; j--)
{
P+=R;
}

Profesor Leopoldo Silva Bijit

18-07-2007

2

Estructuras de Computadores Digitales

Nótese que P y R deben ser de largo 2N, y el sumador también debe ser de largo 2N. En este
algoritmo el número de sumas es proporcional a Q, lo cual es demasiado elevado.

11.2. Multiplicación mediantedesplazamientos.
El siguiente algoritmo, corresponde a la multiplicación manual (con papel y lápiz) en la cual se
va multiplicando las cifras del multiplicando por cada una de las cifras del multiplicador:
0111*0011
0111
0111
0000
0000
0010101
Puede reducirse el número de veces que se repite la operación, notando que, en el sistema
binario, sólo debe efectuarse la suma del multiplicando si lacifra correspondiente del
multiplicador es uno; ya que la multiplicación por cero no cambia el producto parcial.
Entonces en lugar de efectuar todas las sumas del multiplicando (desplazado una posición hacia
la izquierda) por cada una de las cifras del multiplicador, podría efectuarse:
0111*0011
0111
0111
0010101
La detección si debe realizarse o no la suma del multiplicando R, puede lograrseobservando
solamente la cifra menos significativa de Q, siempre que después de realizada la suma, se divida
(en forma entera) el valor de Q. Esto logra un corrimiento hacia la derecha de Q, en una
posición. Además el multiplicando debe desplazarse en una posición hacia la izquierda.
El siguiente algoritmo desarrolla las ideas anteriores, y la suma se realiza a lo más en N pasos;
es decir unavez por cada cifra de Q.
Nótese que (Q&1), que determina el valor del bit menos significativo de Q, equivale a la
condición: Q impar.
/*Algoritmo b
P y R de largo 2N. Q largo N. Sumador ancho 2N */
/* Q y R positivos
P=R*Q
*/
for(j=N; j>=0; j--)
{
if(Q&1) P+=R; Q=Q/2; R=R*2;
}
La secuencia anterior destruye los valores originales de Q y R.

Profesor Leopoldo Silva Bijit18-07-2007

Algoritmos de multiplicación y división

3

Si reemplazamos la división y multiplicación entera por 2, por funciones que realicen
corrimientos, se tiene el siguiente algoritmo:
/*Algoritmo 1
P y R de largo 2N. Q largo N
/* Q y R positivos
P=R*Q
*/
for(j=N;j>=0;j--)
{
if(Q&1) P+=R;
lls(R); lrs(Q);
}

Sumador ancho 2N. */

Se emplean las funciones lls y lrs, por logical...