Multiplicação Binária Inteira - Organização de Computadores

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Multiplicação binária inteira
Algoritmos para multiplicação de números inteiros positivos
Algoritmo 1
Algoritmo 1 – Problemas
Os computadores trabalham com números fixos de bits, portanto, multiplicar valores com diferente quantidade de bits é mais complicado.
Necessita de um circuito somador de tamanho 2N, sendo N o número de bits do Multiplicando ou Multiplicador.
Necessita de um registrador de 2N bits para armazenar um multiplicando de N bits.
Também necessita de um registrador de 2N bits para armazenar o produto, mas disso não tem como fugir.
Algoritmo 1 - características
O bit menos significativo do resultado só é afetado pela primeira parcela da soma e não é alterado após isso.
O bit de ordem N, portanto, será afetado somente pelas primeiras N somas.
Conclusão: se deslocarmos o resultado para a direita, podemos obter um resultado similar a deslocar o multiplicando para a esquerda.
Vantagem: podemos manter o multiplicando com seu tamanho original de N bits.
Algoritmo 2
Algoritmo 2 - características
Não é necessário inicializar r, pois qualquer valor inicial que contenha será sobreposto pelos sucessivos deslocamentos à direita contidos no algoritmo.
Uma vez analisado, um bit do multiplicador não será mais utilizado, podendo, portanto, ser descartado.
Algoritmo 3
Para facilitar a análise dos bits do multiplicador, podemos analisar sempre seu bit menos significativo, e deslocar seu valor para a direita a cada passagem. 
A variável i passa a ser usada apenas para controle do laço de repetição, portanto, podemos fazer contagem decrescente, e comparar seu valor com zero (comparar números com zero é uma tarefa simples e rápida de ser efetuada pelo computador).
Algoritmo 3
Algoritmo de booth
O Algoritmo 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.
Algoritmo de booth - variáveis
Algoritmo de booth – resultado final
Despreza-se o bit menos significativo em P: 
R = P[2n : 1]
EXTRA: Divisão binária inteira