Qual é a lógica por trás algoritmo da divisão de Fourier?

Question

da Wikipedia:. Fourier divisão

Aqui está uma imagem do mesmo: ( vista em full-resolução )

Qual é a lógica por trás deste algoritmo?

Eu sei que pode ser usado para dividir números muito grandes, mas exatamente como ele funciona?

Answer 1

este parece ser uma transformação inteligente do algoritmo de divisão longa. As peças inteligentes parece ser que eles estão apenas usando a operação de divisão para o primeiro "dígito", a1, e evitar ter que usar o outro um (x) é da mesma forma, aplicando-os na próxima etapa subtraindo sua produto (contra o quociente parcial) do restante intercalar.

Que este validamente pode ser feito e que sempre funciona é provavelmente devido ao fato de que os "dígitos" (base 100, neste caso) não são dígitos reais e pode legitimamente assumir valores tanto maior do que a sua base (ou seja, , mais de 100) e até mesmo menor que zero. Isto permite uma maior flexibilidade no momento da aplicação de cada "dígito" para o funcionamento como, por exemplo, diferindo a aplicação dos dígitos secundários do divisor (a (x> 1)) até depois de um quociente parcial é criado a partir da divisão do passo anterior por um (1), que por sua vez permite que sejam aplicados como uma subtracção produto, em vez de uma operação de divisão.

Answer 2

É um algoritmo extremamente inteligente. Eu não posso imaginar como ol' JF conseguiu HLD dele desde relação therecurrence é extremamente difícil de ver, mesmo quando você kknow ela existe. Na minha opinião ele formalizou um método que ele estava usando para fazer longhand divisão - ele deve ter feito um grande número de cálculos à mão na era antes calculadoras digitais, e ele provavelmente preferia ser exato sobre o uso de uma régua de cálculo, apenas para ter certeza.

É verdade que se pode ver vagamente o contorno do método no início do algoritmo de divisão longa padrão, mas essa é a única pista. Você poderia procurar muito e duro para isso recorrência sem vê-lo. Há tantos números envolvidos - ele fica confuso olhar para as relações

.

Há uma outra intuição para ser adquirida a partir de estudar o fluxo de dados no algoritmo de multiplicação standard. Se você escrevê-lo em hardware de computador, você pode ver que uma matriz quadrada de 8 bits unidades multiplicativos leva dois números de 32 bits dispostos ao longo de sua parte inferior e os lados direito e move os dados para cima e para a esquerda, saindo na borda superior da matriz de resposta de 64 bits. A unidade mais à esquerda superior proporciona a parte superior dois dígitos do produto (8 bits), utilizando os melhores dígitos dos multiplicandos e transportar no do resto da matriz à sua direita. OK? Bem, imaginar a matriz rodando em sentido inverso para tomar como entrada o divident 64 bits ao longo da borda superior e um divisor de 32 bits, por exemplo ao longo do bordo do lado direito da matriz. Em seguida, ele emite o quociente de 32 bits ao longo da borda inferior (A restante deve ser gerado demasiado .. esquecer aboutit para o MO). Agora a unidade superior esquerda na matriz leva no top dois dígitos do dividendo a partir do topo da matriz, o topo dígito do divisor a partir do lado direito da matriz, e emite o topo dígitos do quociente para baixo na de matriz (e para fora do fundo) e o restante para a direita para a matriz.

Ufa! Isso foi apenas para a primeira saída dígito. É apenas o começo. O gênio de Fourier foi em ver como se pode alimentar nos restos se acumulam de forma a manter as entradas limitadas a apenas três (digamos de 8 bits) dígitos, eo outut em apenas dois (digamos de 8 bits) dígitos para cada unidade na modificado série multiplicativa correndo em sentido inverso (que podemos chamar de uma matriz divisão agora).

E, claro, isso é como nós pode fazer a divisão em hardware, não microcódigo necessário, em um computador ALU.

Pelo menos, presumo este método é usado, onde microcódigo foi evitado em favor de mais bilhões de alguns transistores. Não estou a par do interior das últimas CPUs, mas eles têm transistores para queimar.