Algoritmos De Booth

Algoritmos De Booth

Algoritmo de Booth

El algoritmo de multiplicación de Booth es un algoritmo de multiplicación que multiplica dos números binarios con signo en la notación de complemento a dos. El algoritmo fue inventado por Andrew Donald Booth en 1950 mientras que hacía investigación sobre cristalografía en la universidad de Bloomsbury, en Birkbeck, Londres. Booth usaba calculadoras de escritorio que eran más rápidas en el desplazamiento que sumando, y creó el algoritmo para aumentar su velocidad. El algoritmo de Booth es de interés en el estudio de la arquitectura de computadoras.

Procedimiento

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

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:

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 bits menos significativos de P, para realizar la siguiente acción:

00 o 11: no se hace nada.

01: P = P + A. Se ignora el desbordamiento (overflow).

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

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

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

Obtenido de «https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Booth&oldid=72288810»


Mis sitios nuevos:
Emprendedores
Politica de Privacidad