convertidor excel

ELO311
Estructuras de Computadores
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 deMultiplicació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, encontraposició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, elmayor
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 largo2N, 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 laoperació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 lascifras 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 unaposició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;...