Como ocorre a divisão em nossos computadores?

17

Como ocorre a divisão dentro de computadores digitais? Qual é o algoritmo para isso?

Pesquisei bastante no google, mas não obtive resultados satisfatórios. Forneça um algoritmo / fluxograma muito claro para o algoritmo de divisão com uma ilustração de amostra.

program-o-steve
fonte
1
@ program-o-steve A divisão em uma ULA é uma operação complexa. Você não receberá um fluxograma "simples".
Majenko 18/11/11
5
@ Leon Heller Oh! Ela não diz de modo Esta é uma questão de hardware puro
programa o-steve
2
@ Leon Heller Eu acho que não é ...., que incluem eletrônicos, computação física ...
programa-o-steve
2
A divisão em microcontroladores não é direta. Existem maneiras rápidas e lentas de fazê-lo. As formas lentas são mais fáceis de entender, mas as formas rápidas são usadas nas CPUs modernas, o que especificamente você quer saber? Você quer apenas uma compreensão básica dos princípios ou uma análise detalhada das CPUs modernas?
Konsalik
4
@LeonHeller Normalmente, eu concordo com as perguntas que você deseja fechar, mas o design da CPU é muito uma questão de engenharia elétrica. Essa pergunta pode ser útil para tornar muito mais claro o que é desejado (como o que o konsalik está perguntando), mas isso não o torna fora de tópico.
Kellenjb

Respostas:

17

Os algoritmos de divisão em projetos digitais podem ser divididos em duas categorias principais. Divisão lenta e divisão rápida.

Sugiro que você leia como a adição e subtração binárias funcionam se você ainda não estiver familiarizado com esses conceitos.

Divisão Lenta

Os métodos lentos mais simples funcionam da seguinte maneira: Subtraia o denominador do numerador. Faça isso recursivamente com o resultado de cada subtração até que o restante seja menor que o denominador. A quantidade de iterações é o quociente inteiro e a quantidade restante é o restante.

Exemplo:

7/3:

  1. 73=4
  2. 43=1
  3. 1<3

Portanto, a resposta é 2 com um restante de 1. Para tornar essa resposta um pouco mais relevante, aqui estão alguns antecedentes. A subtração binária por adição do negativo é realizada, por exemplo: 7 - 3 = 7 + (-3). Isso é realizado usando o complemento de dois. Cada número binário é adicionado usando uma série de somadores completos:

insira a descrição da imagem aqui

Onde cada somador completo de 1 bit é implementado da seguinte maneira:

insira a descrição da imagem aqui

Divisão Rápida

Embora o método mais lento de divisão seja fácil de entender, ele exige iterações repetitivas. Existem vários algoritmos "rápidos", mas todos eles dependem de estimativas.

Considere o método Goldschmidt:

Farei uso do seguinte:

Q=ND

Este método funciona da seguinte maneira:

  1. Multiplique N e D com uma fração F de modo que D se aproxime de 1.
  2. Quando D se aproxima de 1, N se aproxima de Q

Esse método usa multiplicação binária via adição iterativa, que também é usada nas modernas CPUs AMD.

Konsalik
fonte
1
Alguns fluxogramas para variações no método 'lento' (implementado em montagem em micros sem divisão de hardware, mas ainda útil) são apresentados no appnote AVR200 da Atmel .
22611 Kevin
você pode dar uma ilustração do método de divisão Goldschmidt. Além disso, o fluxograma fornecido aqui é um exemplo de divisão lenta?
programa o-steve
qual é o método no qual temos que mudar repetidamente o dividendo para a esquerda?
program-o-steve
@ program-o-steve Aqui está uma ilustração rápida: encontre 22/7 (aproximação pi). Primeiro, multiplique a parte superior e inferior por 0,1 para obter: 2,2 / 0,7 Multiplique novamente, usando 1,3, fornecendo: 2,86 / 0,91 Usando 1,09 fornece: 3,1744 / 0,9919 1,008 fornece: 3,1423393 / 0,9998352 Continue, em breve chegará à RESPOSTA FINAL 3,1428571 / 1.000000 ...
Alan Campbell
Como você "multiplica por uma fração"? As frações não são representáveis ​​no ponto flutuante. Uma fração por definição é numerador dividido por denominador, então você fica em um argumento circular de ainda ter que dividir. E como se estima essa fração em primeiro lugar?
CogitoErgoCogitoSum
4

O hardware para divisão de ponto flutuante faz parte de uma unidade lógica que também faz multiplicação; existe um módulo multiplicador de hardware disponível. Os números de ponto flutuante, digamos A e B, são divididos (formando A / B) por

  1. decompondo os números de ponto flutuante em sinais (+1 ou -1), mantissa ("a" e "b" e (tipo inteiro binário) expoentes
  2. o sinal do resultado é (+1) se ambos os sinais forem iguais, senão (-1)
  3. expoentes são subtraídos (expoente de B subtraído do expoente de A) para formar o expoente do resultado
  4. mantissas (os dígitos binários dos números) são um número binário de ponto fixo entre 1/2 e 1; isso significa que o primeiro dígito após o ponto binário é '1', seguido de zeros e uns ... como primeiro passo, uma tabela de pesquisa encontra a precisão recíproca em seis bits (existem apenas 32 possibilidades, é uma tabela pequena)

  5. ab=areciprocal(b)breciprocal(b)

  6. d==1+ϵ
    d(2d)=(1+ϵ)×(1ϵ)=1ϵ2
  7. O numerador, agora que o denominador é exatamente '1', é a mantissa do resultado e pode ser combinado com o sinal e expoente previamente calculados.
  8. O ponto flutuante IEEE permite algumas exceções (números desnormalizados, NAN; esses devem ser tratados por outras operações lógicas.

Curiosamente, o antigo bug de divisão do Pentium (muito interessante em 1994) foi causado por um erro de impressão que causou valores de tabela recíproca com falha para a etapa (4). Um artigo inicial, "Um método de divisão usando um multiplicador paralelo", Domenico Ferrari, IEEE Trans. Electron. Comput. EC-16 / 224-228 (1967), descreve o método, assim como "O IBM System / 360 Modelo 91: Unidade de Execução de Ponto Flutuante" IBM J. Res. Dev. 11 : 34-53 (1967).

Whit3rd
fonte
1

Existem métodos muito diferentes de divisão, dependendo dos números a serem manipulados. Para números inteiros, o método shift-and-subtract fornecido por outras pessoas funcionará bem. Para números de ponto flutuante, no entanto, pode ser mais rápido calcular primeiro o recíproco do denominador e depois multiplicar esse número pelo seu numerador.

A computação do recíproco do denominador não é tão ruim; isso é feito refinando aproximações sucessivas. Seja g o seu palpite por 1 / d. Para um palpite aprimorado, use g '= g (2-gd). Isso converge quadraticamente, então você duplica os dígitos da precisão em cada aprimoramento.

Exemplo: calcule o recíproco de 3,5.

Seu palpite inicial é 0,3. Você calcula 0,3 * 3,5 = 1,15. Sua estimativa ajustada é de 0,3 * (2 - 1,15) = 0,285. Já está bem perto! Repita o processo e você obtém 0,2857125 e uma terceira tentativa obtém 0,2857142857.

Existem alguns atalhos. No ponto flutuante, você pode extrair potências de dez ou potências de dois, dependendo da base numérica da sua máquina. E, para velocidade às custas de um maior uso de memória, você pode usar uma tabela pré-calculada para números no intervalo de 1 a b (onde b é sua base numérica) para obter uma estimativa imediatamente próxima do valor recíproco e salve uma ou duas etapas de refinamento.

Lembre-se de que, assim como a multiplicação e o constrangimento de Kolmogorov em 1960 por seu aluno Anatoly Karatsuba, você nunca sabe quando um método mais rápido ou melhor será encontrado. Nunca renuncie à sua curiosidade.

richard1941
fonte
-1

Os computadores não fazem adição iterativa para multiplicar números - seria muito lento. Em vez disso, existem alguns algoritmos de multiplicação rápida. Confira: http://en.wikipedia.org/wiki/Karatsuba_algorithm

user59608
fonte
Bem-vindo ao EE.SE. As respostas somente de link são desencorajadas. Por favor, resuma as informações no link.
Null
Eles fazem. Toneladas de CPUs ainda não têm multiplicadores de ciclo único e usam a mutiplicação de software.
user3528438