Como ocorre a divisão em nossos computadores?

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.

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. $$7-3=4$$
2. $$4-3=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:

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

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:

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.

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. $${a \over b} = {{a * reciprocal(b)}\over b * reciprocal(b)}$$

6. $$d == 1 +\epsilon$$ $$d * (2-d) = ( 1+ \epsilon) \times (1-\epsilon) = 1 - \epsilon ^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).

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.

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