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 dois. 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 é o número de bits da representação binária em complemento de dois do multiplicando e y o número de bits 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.

• Repita o procedimento abaixo 'número de bits de y' vezes:
• 1. Se os dois últimos bits do produto são:
  • o 00 ou 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. Neste passo, o sinal de P deve ser preservado, isto é, se o bit mais significativo for 1, então após o deslocamento o novo bit mais significativo também deve ser 1. Caso o bit mais significativo for 0, após o deslocamento o novo bit mais significativo deve também ser 0.

• 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 problema é 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.

Como funciona

Considere um multiplicador positivo consistindo de um bloco de 1s rodeados por 0s. Por exemplo, 00111110. O produto é dado por :

$M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62$

onde M é o multiplicando. O número de operações podem ser reduzidas a duas, reescrevendo a mesma como

$M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62$

De fato, pode ser mostrado que qualquer seqüência de 1's em um número binário pode ser quebrada na diferença de dois números binários:

$(\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}$.

Daí, podemos efetivamente substituir a multiplicação por uma string de 1s no número original por operações mais simples, adicionando o multiplicador, deslocando o produto parcial assim formado por lugares apropriados e então, finalmente, subtraindo o multiplicador. Isso faz uso do fato de que não se deve fazer nada além de deslocar enquanto lidamos com 0s no multiplicador binário, e é similar a usar propriedade matemática que $99=100-1$ enquanto multiplicamos por 99.

Este esquema pode ser estendido para qualquer número de blocos de 1s no multiplicador (incluindo o caso de um único 1 em um bloco). Assim,

$M\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58$

$M\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58$

O algoritmo de Booth segue esse esquema por executar uma adição quando encontra o primeiro dígito de um bloco de 1s (0 1) e uma subtração quando encontra o final de um bloco (1 0). Isso funciona também para números negativos. Quando os 1s no multiplicador são agrupados em blocos longos, o algoritmo de Booth executa menos adições e subtrações que o algoritmo normal de multiplicação.

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.