Mais um blog inútil.

Janeiro 15, 2008

Multiplicação com FFT

Filed under: Serious Business — dongs @ 20:06

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.

7 comentários a “Multiplicação com FFT”

  1. luminoso diz:

    qual a vantagem dos calculos serem logaritmicos?

  2. dcoder diz:

    O número de operações cresce muito mais devagar do que com complexidade polinomial ou exponencial.

    Faz aí o grafico de log(x), x^2 e e^x e vê qual cresce mais depressa e mais devagar.

  3. mirage diz:

    Fiquei todo húmido ao ler isto.

  4. Armorfist diz:

    adorava perceber a 100% os teus posts. dão-me uma tesão descomunal

  5. sadik diz:

    adorava ter o cerebro do dcoder

Comentar

widgeon
widgeon
widgeon
widgeon