El algoritmo de multiplicación de Booth

Historia

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.

Creador

Andrew Donald Booth (11 febrero 1918 hasta 29 noviembre 2009 fue un británico ingeniero eléctrico, físico y científico de la computación que dirigió el desarrollo temprano de la memoria de tambor magnético para las computadoras e inventó el algoritmo de multiplicación de Booth.

Booth fue criado en Weybridge, Surrey, y estudió en la Escuela “Haberdashers' Aske's Boys' School”. En 1937, ganó una beca para leer matemáticas en el “Jesus College”, Cambridge. Booth dejó Cambridge sin tener un título, habiéndose convertido descontento con las matemáticas puras como sujeto. Eligió un grado externo de la Universidad de Londres en vez, que obtuvo por primera vez.

De 1943 a 1945, el Booth trabajó como físico matemático en el equipo de rayos X en la Asociación de Productores de Caucho británicos Investigación (BRPRA), Welwyn Garden City, Hertfordshire, obteniendo su doctorado en la cristalografía de Birmingham en 1944. En 1945, se trasladó a Birkbeck College, Universidad de Londres, donde su trabajo en el grupo de cristalografía le llevó a construir algunas de las primeras computadoras electrónicas en el Reino Unido, incluyendo el uso múltiple del ordenador electrónico, instalado por primera vez en la Asociación de Investigación Rayon británica. Booth fundó el departamento de automatización numérica de Birkbeck y fue nombrado recientemente a un compañero de la universidad. Él también hizo un trabajo pionero temprano en la traducción automática.

Booth desempeñó como Presidente de la Universidad Lakehead 1972 a 1978.

Métodos

El algoritmo de Booth 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.

Complemento a1

Para obtener el complemento a uno del número en binario solo consta en cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1:101101)

Complemento a2

El complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el número es negativo): mi número en decimal es 86

Realizar una multiplicación con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos

...