Algoritmo de multiplicação de Booth: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: ar:خوارزمية بوث; mudanças triviais |
|||
Linha 5:
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.
* 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 ==
Linha 29:
Encontre 3 × (-4):
* A = 0011 0000 0
* S = 1101 0000 0
* P = 0000 1100 0
* Execute o loop quatro vezes :
*# P = 0000 110'''0 0'''.
*#* P = 0000 0110 0.
*# P = 0000 011'''0 0'''. Os últimos dois bits são 00.
*#* P = 0000 0011 0.
*# P = 0000 001'''1 0'''.
*#* P = 1101 0011 0.
*#* P = 1110 1001 1.
*# P = 1110 100'''1 1'''.
*#* P = 1111 0100 1.
* 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:
Linha 66:
* 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 :
: <math> 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 </math>
Linha 83:
: <math> 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 </math>
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úmerios negativos.
== {{Ligações externas}} ==
* [http://www.geoffknagge.com/fyp/booth.shtml Radix-4 Booth Encoding]
* [http://www.russinoff.com/libman/text/node38.html Radix-8 Booth Encoding] in [http://www.russinoff.com/libman/ A Formal Theory of RTL and Computer Arithmatic]
== Referências ==
# Collin, Andrew. [http://www.cs.man.ac.uk./CCS/res/res05.htm#e Andrew Booth's Computers at Birkbeck College]. ''Resurrection'', Issue 5, Spring 1993. London: Computer Conservation Society.
# 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.
Linha 97:
[[Categoria:Aritmética computacional]]
[[ar:خوارزمية بوث]]
[[cs:Boothův algoritmus]]
[[de:Booth-Algorithmus]]
| |||