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.
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 :
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:
Considere um multiplicador positivo consistindo de um bloco de 1s rodeados por 0s. Por exemplo, 00111110. O produto é dado por : onde M é o multiplicando. O número de operações podem ser reduzidas a duas, reescrevendo a mesma como 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: ( … 0 1 … 1 ⏞ n 0 … ) 2 ≡ ( … 1 0 … 0 ⏞ n 0 … ) 2 − ( … 0 0 … 1 ⏞ n 0 … ) 2 {\displaystyle (\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 {\displaystyle 99=100-1} enquanto multiplicamos por 99.
