Algoritmo De Booth

Algoritmo de Booth

s un procedimiento algorítmico para realizar la multiplicación de dos números con signo, expresados en base binaria en notación complemento a dos.

Supongamos dos números, multiplicando y multiplicador, con longitudes en bits, x para el primero, e y para el segundo:

Procedimiento del algoritmo de Booth

Construimos una matriz de tres filas y x+y+1 columnas. Identificaremos las filas como, A la primera, S la segunda y P la tercera.

Se inician los x primeros bits de cada fila con:

A.- El multiplicando.

S.- El complemento a dos del multiplicando.

P.- Ceros.

Los siguientes y bits se completan con:

A.- Ceros.

S.- Ceros.

P.- El multiplicador.

Para finalizar la matriz, se inician a 0 todos los valores de la última columna.

Una vez iniciada esta matriz, se realiza el algoritmo.

Se realizan y iteraciones del siguiente bucle.

Comparar los dos últimos bits de P, para realizar la siguiente acción:

00 o 11: no se hace nada.

01: P = P + A. Se ignora el acarreo.

10: P = P + S. Se ignora el acarreo.

2. Desplazamiento aritmético de P a la derecha (se conserva el bit de signo).

Finalmente, tras y iteraciones, se elimina el último bit de la derecha (menos significativo), obteniendo el resultado.

Algoritmo de la división

Definición.

Dados enteros a, b con b(Diferente de)0 existen enteros q & r tales que

a = b q + r y 0(Menor/Igual)r(Menor/Igual)|b|

Al número A se le llama dividendo.

Al número B se le llama divisor.

Al número Q se le llama cociente.

Al número R se le llama residuo.

En el caso particular que a y b sean enteros positivos, se trata de hallar el número de veces que el dividendo contiene al divisor. Este número se llama cociente, y lo que queda se llama residuo.

...