PDF de programación - Algoritmos de Multiplicación y División

Estructuras de Computadores

ELO311

Digitales

Algoritmos de Multiplicación y División

Tomás Arredondo Vidal

Este material está basado en:

material de apoyo del texto de David Patterson, John Hennessy,
"Computer Organization & Design", (segunda y tercera edición),
Morgan Kaufmann, CA. 2005

material del curso anterior ELO311 del Prof. Leopoldo Silva

www.wikipedia.org

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á advertirse la

naturaleza secuencial de éstos, en contraposición al
carácter combinacional de las operaciones de suma y
resta.

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.

Producto = Multiplicando * Multiplicador

P: Producto
R: Multiplicando
Q: Multiplicador

P = R * Q

Multiplicación como Suma Repetitiva (cont)
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 dígitos, 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

Multiplicación como Suma Repetitiva (cont)
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;

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.

Multiplicación Mediante Desplazamientos
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:

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 la cifra
correspondiente del multiplicador es uno; ya que la
multiplicación por cero no cambia el producto parcial.

Multiplicación Mediante Desplazamientos (cont)
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:

La detección si debe realizarse o no la suma del

multiplicando R, puede lograrse observando 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 se logra con un corrimiento hacia la derecha de Q,

en una posición. Además el multiplicando debe
desplazarse en una posición hacia la izquierda.

Multiplicación Mediante Desplazamientos (cont)
El siguiente algoritmo desarrolla las ideas anteriores, y la

suma se realiza a lo más en N pasos; es decir una vez
por cada cifra de Q.

Nótese que (Q&1), determina el valor del bit menos

significativo del multiplicador Q.

/*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;

Multiplicación Mediante Desplazamientos (cont)

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 Sumador ancho 2N. */

/* Q y R positivos P = R * Q */

for( j = N; j >= 0; j-- )

{

}

if (Q&1) P += R;

lls(R); lrs(Q);

Se emplean las funciones lls y lrs, por logical left shift y logical right

shift respectivamente.

Como los bits de signo de Q y R siempre serán ceros, pueden

efectuarse corrimientos lógicos o aritméticos.

Fundamentos de Algoritmos de Multiplicación
Para analizar los algoritmos, si Q positivo( qn es cero), entonces:

El Algoritmo a, descrito usando ecuaciones de diferencias :

S0 = 0 + R q0 20
S1 = S0 + R q1 21
S2 = S1 + R q2 22
S3 = S2 + R q3 23
.......
Sn-1 = Sn-2 + R qn-1 2n-1
Sn = Sn-1 + R qn 2n

La cifra de Q, en la etapa i-ésima, qi sólo puede ser cero o uno. Si es

uno, el término asociado se suma.

Fundamentos de Alg. de Multiplicación (cont)
El término R 2i es el multiplicador desplazado i posiciones

hacia la izquierda.

Esto justifica el algoritmo ya visto, que corresponde a la

multiplicación tradicional, efectuada con papel y lápiz.

Si Q está en notación complemento dos y Q es positivo,

entonces: qn = 0.

El producto final queda en Sn.

Fundamentos de Alg. de Multiplicación (cont)
El Algoritmo 1, expresado por ecuaciones de diferencias:

Agregando el multiplicador anterior multiplicado por dos (ri)
S0 = 0 + R q0 20 = 0 + r0 q0
S1 = S0 + R q1 21 = S0 + r1 q1
S2 = S1 + R q2 22 = S1 + r2 q2
S3 = S2 + R q3 23 = S2 + r3 q3
.......

, r0 = R
, r1 = 2 r0
, r2 = 2 r1
, r3 = 2 r2

Sn-1 = Sn-2 + R qn-1 2n-1 = Sn-2 + rn-1 qn-1 , rn-1 = 2 rn-2
, rn = 2 rn-1
Sn = Sn-1 + R qn 2n

= Sn-1 + rn qn

El producto queda en Sn.

Fundamentos de Alg. de Multiplicación (cont)

También pueden escribirse:

q0 = Q0 & 1 , Q0 = (Q/20)
q1 = Q1 & 1 , Q1 = (Q/21) = Q0/2
q2 = Q2 & 1 , Q2 = (Q/22) = Q1/2

....

qn = Qn & 1 , Qn = (Q/2n) = Qn-1/2

Resumiendo se tienen las siguientes ecuaciones:

qi = Qi & 1
Si = Si-1 + riqi
ri = ri-1 * 2
Qi = Qi-1 / 2

con S-1= 0
con r0 = R
con Q0 = Q

Entonces en la etapa i-ésima, si qi es 1, se suma al producto parcial
anterior Si-1, el multiplicador anterior multiplicado por dos (que es ri).

Algoritmos más eficientes

Se desea desarrollar ahora un algoritmo más eficiente, que emplee

menos recursos electrónicos que el anterior:

Estudiemos la multiplicación binaria de (+26)*(+13) = +338

Se observa que en cada paso sólo se suman 6 cifras (bits), la cifra

menos significativa de la suma acumulada no afecta las sumas
posteriores y puede decirse que es una cifra del producto final.

Tampoco es necesario correr el multiplicando a la izquierda, si en lugar

de esto se desplaza la suma (el producto parcial) hacia la derecha.

De esta forma una de las entradas del sumador quedará fija con el

valor del multiplicando (R). Se requiere un sumador de n+1 bits
solamente.

Algoritmos más eficientes (cont)

A partir de las relaciones de recurrencia del Algoritmo 1, se

procederá a obtener las ecuaciones del Algoritmo 2.

Básicamente consisten en expresar las sumas parciales en

función solamente de R. Se comienza dividiendo por 2i:

S0/20 = 0/20 + Rq0 = 0 + Rq0 = s0
S1/21 = S0/21 + Rq1 = s0/2 + Rq1 = s1
S2/22 = S1/22 + Rq2 = s1/2 + Rq2 = s2
S3/23 = S2/23 + Rq3 = s2/2 + Rq3 = s3
.......

Sn-1/2n-1 = Sn-2/2n-1 + R qn-1 = sn-2/2 + Rqn-1 = sn-1
Sn/2n = Sn-1/2n + R qn = sn-1/2 + Rqn = sn

Algoritmos más eficientes (cont)

Ordenando las relaciones anteriores y definiendo x, que

representa la suma si dividida por dos:
s0 = 0 + Rq0 , x0 = s0/2 , con x-1 = 0
s1 = x0 + Rq1 , x1 = s1/2
s2 = x1 + Rq2 , x2 = s2/2
s3 = x2 + Rq3 , x3 = s3/2
.......

sn-1 = xn-2 + R qn-1 , xn-1 = sn-1/2
sn = xn-1 + R qn , xn = sn/2

Algoritmos más eficientes (cont)

Si qi es uno se suma R con la suma anterior desplazada en
uno hacia la derecha (xi-1). Con qn = 0 para número positivo.

Para la etapa i-ésima:

qi = Qi &1
si = xi-1 + R qi con x-1 = 0
xi = si / 2 con s0 = 0
Qi = Qi-1 / 2 con Q0 = Q

Si qi es uno se suma R con la suma anterior desplazada en

uno hacia la derecha (xi-1).

Si qi es cero sólo se desplazan hacia la derecha las

variables s y Q.

Algoritmos más eficientes (cont)

/*Algoritmo 2 s, Q y R de largo n+1. Sumador ancho n+1 */

/* Q y R positivos. Al salir sQ= R * Q */

for(i=0, s = 0; i<n+1; i++)

{

}

if (Q &1 )

s = s + R ;

Q = Q/2; s = s /2

No hay problemas de rebalse con números sin signo, ya que R es

positivo, y rn siempre es cero.

Q =Q/2; s = s /2 puede escribirse como un desplazamiento lógico a

derecha (lrs).

MIPS almacena este resultado en los registros HI y LO.

Operandos con Signo: Algoritmos de Booth

A partir de las relaciones de recurrencia del Algoritmo 2, se procederá a

obtener un algoritmo para operandos con signo.

Q en complemento 2 se puede escribir como:

Q = - qn2n + qn-12n-1+ qn-2 2n-2+ ....+q121+ q020

Y también como:

Q = - (qn2n + qn-12n-1+ qn-2 2n-2+ .... + q1211+ q020) + 2(qn-12n-1+ qn-2 2n-2 +
....+q121+ q020 )

Introduciendo el factor 2 en las potencias de los términos positivos:

Q = - (qn2n + qn-12n-1+ qn-2 2n-2+ .... + q1211+ q020) + (qn-12n+ qn-2 2n-1+ ....+
q122 + q021 )

Finalmente, agrupando los factores de las potencias iguales, se logra:

Q = (qn-1 - qn ) 2n + (qn-2- qn-1) 2n-1 + (qn-3- qn-2) 2n-2 + .... +(q1- q2) 22 + (q0- q1)
21 + (0 - q0) 20

Algoritmos de Booth (cont)

Entonces las relaciones de recurrencia para el algoritmo dos:

Algoritmo 2.

s0 = 0 + R q0
s1 = s0/2 + R q1
s2 = s1/2 + R q2
....
sn-1 = sn-2/2 + R qn-1
sn = sn-1/2 + R qn

Pueden transformarse en: Algoritmo de Booth

s0 = 0 + R (0 - q0 )
s1 = s0/2 + R (q0 - q1 )
s2 = s1/2 + R (q1 - q2 )
....
sn-1 = sn-2/2 + R (qn-2 - qn-1_)
sn = sn-1