Algoritmo Booth

Una aproximación más elegante para multiplicar y dividir números asignados. Se comienza haciendo la observación de que con la posibilidad de sumar y restar hay múltiples formas de calcular un producto.

ALGORITMO DE BOOTH MULTIPLICACIÓN Y DIVICIÓN

¿Qué es el algoritmo de Booth?

Una aproximación más elegante para multiplicar y dividir números asignados. Se comienza haciendo la observación de que con la posibilidad de sumar y restar hay múltiples formas de calcular un producto.

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.

En el cual se examina pares adyacentes de bits del multiplicador Y de N-bits donde la representación de complemento a dos con signo, se incluye un bit implícito debajo del bit menos significativo, y-1 = 0.

Este es un método rápido y sencillo para obtener el producto de dos números binarios con signo en notación complemento a dos.

Debemos saber que un número binario está formado por bits de ceros y unos, y que se puede traducir a decimal fácilmente.

Realizar una suma con dos números binarios es tarea fácil, pero la multiplicación resulta algo más complicada. Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Genera multiplicaciones de 2n bits y trata por igual tanto números positivos como negativos.

El algoritmo toma en cuenta cada bit yi, para i corriendo desde 0 hasta N-1, los bits yi y yi-1 . Cuando estos dos bits son iguales, el acumulador del producto P es dejado sin cambios. Cuando yi = 0 y yi-1 = 1, el multiplicando multiplicado por 2i es agregado a P; y cuando yi = 1 y yi-1 = 0, el multiplicando multiplicado por 2i es restado de P. El valor final de P es el producto con signo.

El multiplicando y el producto no son especificadas; típicamente, ésta representación de complemento a dos, como el multiplicador, pero cualquier sistema de numeración que soporte la adición y la substracción trabajará igual de bien. Según lo indicado aquí, el orden de los pasos no está determinado. Típicamente, procede desde el bit menos significativo (LSB) al bit mas significativo (MSB), comenzando en i = 0; la multiplicación por 2i es entonces típicamente reemplazado por el desplazamiento (shifting) incremental del acumulador P a la derecha entre los pasos; los bits bajos pueden ser desplazados hacia fuera, y las adiciones y substracciones subsecuentes entonces pueden ser hechas justo en los N bits más altos de P. Hay muchas variaciones y optimizaciones sobre estos detalles.

El algoritmo es a menudo descrito como convertir secuencias de 1s en el multiplicador con un +1 de orden alto y un -1 de orden inferior en los extremos de la secuencia. Cuando una secuencia corre por el MSB, no hay +1 de orden alto, y el efecto neto es la interpretación como un negativo de valor apropiado.

Este algoritmo se basa en el hecho de que cuando tenemos un multiplicando el cual tiene una serie de unos en su representación, el valor se puede descomponer en la resta de otros dos números con una cantidad de unos menores, por ejemplo:

0 0 1 1 1 1 0 = 0 1 0 0 0 0 0 - 0 0 0 0 0 1 0

Así la multiplicación se puede descomponer en una operación de adición para el primer número y de una resta para el segundo:

M*0 0 1 1 1 1 0) = M(0 1 0 0 0 0 0) - M(0 0 0 0 0 1 0)

El nuevo multiplicador lo podemos representar por:

m’ = 0 1 0 0 0 -1 0

Pero este método se puede generalizar para cualquier cadena de bits en el multiplicando. Para ello realizamos un algoritmo de forma que cuando realicemos la multiplicación, nos fijaremos en el multiplicador viendo los bits de dos en dos: mi y mi-1, de forma que cuando tengamos estas cuatro posibles secuencias, determinarán el valor de m’i, y realizaremos las acciones indicadas:

00 ó 11 : m’i = 0 : Solo desplazaremos el multiplicador -->

01 : m’i = 1 : Realizaremos el producto por 1 y desplazado.

10 : m’i = -1 : Realizaremos el complemento a dos del multiplicador con extensión de signo y desplazado. Pero surge el problema del primer bit, para lo cual introducimos un bit previo a m0, el m-1.

Ejemplo:

m = 1 0 1 1 0 1 0 1(0) = mpos - mneg

m’ =-1 1 0-1 1-1 1-1

mpos = 0 1 0 0 1 0 1 0 (unos en los 1’s de m’)

mneg = 1 0 0 1 0 1 0 1 (unos en los -1’s de m’)

Para realizar la multiplicación podemos utilizar dos métodos, codificar el el multiplicador como hemos visto antes (con signos negativos en los unos) o no codificarlo y tener en cuenta la secuencia de bits de dos en dos como hemos visto.

El algoritmo en

...