Multiplicação de inteiros com FFT
Como é que isto se faz? (https://blol.org/94-multiplicacao-com-fft)
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á.) [interessante]
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.
do site LeGauss
entendimento passa pela Matriz de Vandermonde (é uma matriz em que os termos de cada linha estão em progressão geométrica, ela surge naturalmente do problema de interpolação polinomial.)
mais ou menos assim (da wikipedia Algoritmo Schönhage-Strassen)
para multiplicar 147 e 258 (em decimal), serão realizadas as seguintes operações:
Representação de 147 como x^2+4x+7 e 258 - como 2x^2+5x+8, onde x = 10.
Multiplique polinômios x^2+4x+7 e 2x^2+5x+8 usando a transformada rápida de Fourier. Obter o produto dos polinômios 2x4+13x^3+42x^2+67x+56.
Ao fazer transferências entre as fileiras, temos 3x4+7x^3+9x^3+2x+6., ou seja, 37.926.
interpolar - método que permite construir um novo conjunto de dados a partir de um conjunto discreto de dados pontuais previamente conhecidos (wikipedia)
interolação polinomial - dado um conjunto de dados (pontos) achar um polinomio que passe por estes pontos
Nenhum comentário:
Postar um comentário