Mais um blog inútil.

Contra toda a lógica, isto é possível. Isto é possível pelo teorema da convolução (uma vez que uma multiplicação também pode ser considerada uma convolução).

OK. Como é que isto se faz?

1 - Transformar os números a multiplicar num polinómio, escolhendo uma base apropriada (e.g. 10, 16, 2^32, etc).

2 - Calcular a DFT de ambos, através do uso de uma FFT. (Não é necessário ser estritamente a FFT, qualquer convolução em teoria dá.)

3 - Multiplicar ponto a ponto ao longo do array obtido (multiplicação diádica).

4 - Calcular a DFT inversa do resultado.

5 - Avaliar o polinómio para obter o número final.

Tanto passo para uma mísera multiplicação. Qual é a vantagem?

A vantagem reside no facto de uma FFT ter complexidade logarítmica O(N log N), assim como os outros passos. A multiplicação clássica tem complexidade O(log N^2), e outros métodos recursivos como Karatsuba ou Toom-Cook têm complexidades inferiores, mas nunca completamente logarítmicos (geralmente na forma O(log N^1+e), 1.4 < e < 2 aproximadamente).

Portanto este método é útil para multiplicar números gigantescos (para ai 10000+ bits), uma vez que a overhead só compensa a esse nível de grandeza.

Aqui está um exemplo de uma multiplicação recorrendo à FFT.

mov ecx, eax
mov eax, 0CCCCCCCDh
mul ecx
shr edx, 3

Em 1994, o Torbjorn Granlund e o Peter Montgomery (o mesmo gajo que inventou a multiplicação de Montgomery do outro post) publicaram um artigo que descrevia como dividir um inteiro N por uma constante d, sem utilizar divisões. A partir daí todos os compiladores que se prezem passaram a usar este tipo de técnicas, e podemos ver no artigo como e’ feito.

a) Calcular a recíproca da divisão (arredondada) - f = 2^r / d => r = W+floor(log2(d) )

b) Multiplicar por f

c) dividir por 2^log2(d)

Assim, no caso acima, temos uma divisão por 10. f = Round(2^32+3/10) = 0xCCCCCCCD

Floor(Log2(10)) = 3;

Infelizmente, devido à perda de precisão não podemos recuperar facilmente as constantes a serem usadas como divisor. No entanto, é fácil criar uma tabela com a maioria das recíprocas e dos factores de escala usados e assim poupar tempo a olhar para contas.

Quem estiver interessado veja isto.

Oi. Eu ia explicar o significado do código abaixo, mas nao tenho tempo agora. Portanto vou pastar aqui o código e escrevo noutro dia.

mov     ecx, eax
mov     eax, 0CCCCCCCDh
mul     ecx
shr     edx, 3

Generalizar o processo pelo qual estas sequencias são criadas facilita bastante a leitura e recuperação de código. O Hex-Rays sabe fazer isso, e eu vou-vos ensinar quando me apetecer.