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 :
Encontre 3 × (-4):
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 :
M × ′ ′ 0 0 1 1 1 1 1 0 ′ ′ = M × ( 2 5 + 2 4 + 2 3 + 2 2 + 2 1 ) = M × 62 {\displaystyle 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 × ′ ′ 0 1 0 0 0 0 -1 0 ′ ′ = M × ( 2 6 − 2 1 ) = M × 62 {\displaystyle 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:
( … 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.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 × ′ ′ 0 0 1 1 1 0 1 0 ′ ′ = M × ( 2 5 + 2 4 + 2 3 + 2 1 ) = M × 58 {\displaystyle 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 × ′ ′ 0 1 0 0 -1 1 -1 0 ′ ′ = M × ( 2 6 − 2 3 + 2 2 − 2 1 ) = M × 58 {\displaystyle 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.