Multiplicação com FFT
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.
qual a vantagem dos calculos serem logaritmicos?
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.
Fiquei todo húmido ao ler isto.
adorava perceber a 100% os teus posts. dão-me uma tesão descomunal
adorava ter o cerebro do dcoder
tesão
amo-te