Transformée de Fourier rapide - Multipliant Polynomials?

StackOverflow https://stackoverflow.com/questions/776719

  •  13-09-2019
  •  | 
  •  

Question

Je ne comprends pas comment effectuer une FFT sur deux polynômes tels que X ^ 2 + 1 et X + 1 ... quelqu'un peut-il pas à pas passer par le processus avec moi?

Merci beaucoup

Était-ce utile?

La solution

Il suffit d'utiliser vos coefficients polynôme comme entrée pour fft: 

octave:16> poly1=[1 0 1 0]
poly1 =

   1   0   1   0

Note: cela signifie x ^ 2 + 1 

octave:17> poly2=[1 1 0 0]
poly2 =

   1   1   0   0

octave:18> ifft( fft(poly1).*fft(poly2))
ans =

   1   1   1   1

Ceci est le résultat. Interpréter comme x ^ 3 + x ^ 2 + x + 1, qui est le produit de deux polynômes.

Autres conseils

Mais vraiment ce qui se passe est convolution ici.

  

IFFT (fft (poly1). * Fft (Poly2))

est l'équivalent de convolution (bien rembourré). Et convolution peut être interprété comme la multiplication de deux polynômes. Allez voir la définition de convolution (il est très simple) et le travailler à la main sur papier. Je pense que ce sera versé beaucoup de lumière sur ce pour vous ...

Paul
Logiciel CenterSpace

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top