Algoritmo de booth

ALGORITMO DE BOOTH
El algoritmo de Booth es 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.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:
 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 estamatriz, se realiza el algoritmo.
 Se realizan y iteraciones del siguiente bucle.
1. 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 últimobit de la derecha (menos significativo), obteniendo el resultado.

ALGORITMO DE LA DIVISION
En la aritmética el algoritmo de la división, también llamado división euclídea, es un teorema queafirma que para cualesquiera enteros d y d, llamados dividendo y divisor respectivamente, con d no nulo, existen enteros únicos c y r, llamados cociente y residuo respectivamente, tales que
Y .
Elalgoritmo de la división es comúnmente representado con una figura similar a


Por ejemplo



Lo que significa que , y además es claro que .
Por el algoritmo de la división sededuce que es un dominio euclídeo tomando como norma el valor absoluto. Una consecuencia inmediata del algoritmo de la división es que puede usarse el algoritmo de Euclides para calcular el máximo...