Algoritmo de multiplicação de Booth

O algoritmo de multiplicação de Booth é um algoritmo de multiplicação para números binários com sinal na notação complemento de 2. O algoritmo foi inventado por Andrew D. Booth em 1951 enquanto fazia pesquisas sobre Cristalografia no Colégio Birkbeck em Bloomsbury, Londres. Booth usava calculadoras que eram mais rápidas em deslocar do que em somar e criou o algoritmo para aumentar sua velocidade. O algoritmo de Booth é interessante para o estudo de arquitetura de computadores.

Processo

Se x é a representação binária em complemento de dois do multiplicando e y a do multiplicador :

• Desenhe uma grade com 3 linhas, com x + y + 1 colunas e um espaço para cada bit. Chame as linhas de A (adição), S (subtração), e P (produto).
• Preencha os primeiros x bits de cada linha com:
  • o A: o multiplicando
  • o S: o negativo do multiplicando
  • o P: zeros
• Preencha os próximos y bits de cada linha com :
  • o A: zeros
  • o S: zeros
  • o P: o multiplicador
• Coloque zero no último bit de cada linha.

• Faça y vezes cada um destes passos:
• 1. Se os dois últimos bits do produto são...
  • o 00 or 11: não faça nada.
  • o 01: P = P + A. Ignore qualquer estouro.
  • o 10: P = P + S. Ignore qualquer estouro.
• 2. Desloque P para a direita um bit.

• Descarte o primeiro (nós contamos da direita para esquerda quando lidamos com bits) bit do produto para o resultado final.

Exemplo

Encontre 3 × -4:

• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0

• Execute o loop quatro vezes :
  1. P = 0000 1100 0. Os últimos dois bits são 00.
     • P = 0000 0110 0. Um deslocamento a direita.
  2. P = 0000 0110 0. Os últimos dois bits são 00.
     • P = 0000 0011 0. Um deslocamento a direita.
  3. P = 0000 0011 0. Os últimos dois bits são 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. Um deslocamento a direita.
  4. P = 1110 1001 1. Os últimos dois bits são 11.
     • P = 1111 0100 1. Um deslocamento a direita.

• O produto é 1111 0100, que representa -12.

A técnica mencionada acima é inadequada quando o multiplicando é um número negativo mais comprido que o que pode ser representado (i.e. se o multiplicando tem 8 bits então esse valor é -128). Uma correção possível para esse probelam é adicionar mais um bit a esquerda de A, S e P. Abaixo, nós demonstramos a técnica melhorada multiplicando -8 por 2 usando 4 bits para o multiplicando e o multiplicador:

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0

• Faça o loop quatro vezes:
  1. P = 0 0000 0010 0. Os últimos dois bits são 00.
     • P = 0 0000 0001 0. Deslocar a direita.
  2. P = 0 0000 0001 0. Os últimos dois bits são 10.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. Deslocar a direita.
  3. P = 0 0100 0000 1. Os últimos dois bits são 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. Deslocar a direita.
  4. P = 1 1110 0000 0. Os últimos dois bits são 00.
     • P = 1 1111 0000 0. Deslocar a direita.

• O produto é 11110000 (depois de descartar o primeiro e o último bit) que é -16.

Ligações externas

• Radix-4 Booth Encoding
• Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmatic

Referências

1. Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
2. Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
3. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.