Mae向きなブログ

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

『アルゴリズムC 第3巻』の「41 高速フーリエ変換」をPythonで

Python

『アルゴリズムC 第3巻』の第41章「高速フーリエ変換」で紹介されているアルゴリズムをPythonで作ってみました。

2つの多項式の積を求めるプログラム(41_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 41_FFT.py
2
1
2
0
1

関連

アルゴリズムC 第3巻

アルゴリズムC 第3巻

Amazon