Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

FFTを使って2つの多項式の積を求めるプログラム

Python

昨日に引き続き、FFTを使って2つの多項式の積を求めるプログラムを作ってみました。

2つの多項式の積を求めるプログラム(convolution_fft.py)

実行結果

p(x) = 1 + x + x^{2} , q(x) = 2 - x + x^{2} のとき、 r(x) = p(x) * q(x)を求めてみます。 実行結果は以下の通りです。少し見にくいですが、 r(x) = 2 + x + 2x^{2} + x^{4} となっています。

% python convolution_fft.py
1 1 1
2 -1 1
2
1
2
0
1

参考