博士

やあ、ロボ子！今日は多項式の乗算について話すのじゃ。

ロボ子

多項式の乗算ですか。分配法則を使うと計算量がO(N^2)になりますね。

博士

そう！でも、高速フーリエ変換（FFT）を使うとO(N log N)でできるのじゃ！

ロボ子

FFTを使うと、そんなに速くなるんですか？

博士

そうなのじゃ。n-1次の多項式はn個の係数かn個のサンプル点で表現できる。係数表現だと乗算はO(N^2)だけど、値表現ならO(N)で済む！

ロボ子

なるほど。FFTは、その係数表現と値表現をO(N log N)で変換してくれるんですね。

博士

その通り！多項式F(x)を偶数項と奇数項に分けると、F(x)とF(-x)の計算が楽になるのじゃ。

ロボ子

偶数項と奇数項に分けるんですか。具体的にはどうやるんですか？

博士

F(x) = F_e(x^2) + xF_o(x^2)と表せるのじゃ。こうすると、x^n=1の解であるn乗根を使って、効率的に計算できる。

ロボ子

n乗根を使うんですね。FFTの肝ですね。

博士

そう！逆FFT（IFFT）は、FFTの共役転置行列に1/nをかけたものとして計算できるのじゃ。

ロボ子

FFTとIFFTを組み合わせることで、多項式の乗算を効率的に行えるんですね。

博士

その通り！DFT行列は係数からサンプル点を計算する時に、IDFT行列はサンプル点から係数を計算する時に使うのじゃ。

ロボ子

ω = e^(2πi/n)というのも重要そうですね。

博士

そう！FFTの実装は10行程度のコードでできるから、ロボ子も試してみるのじゃ！

ロボ子

10行ですか！意外と短いんですね。試してみます。

博士

例えば、f(x) = 4x^4 - 2x^3 - 6x^2 + 4x + 3とg(x) = -x^4 + 11x^3 - 9x^2 - x + 6の積は、-4x^8 + 46x^7 - 52x^6 - 56x^5 + 121x^4 - 9x^3 - 67x^2 + 21x + 18になるのじゃ。

ロボ子

すごい！それをFFTとIFFTで計算するんですね。

博士

そう！テストすると、出力された係数は[18, 21, -67, -9, 121, -56, -52, 46, -4, 0, 0, 0, 0, 0, 0, 0]になるはずじゃ。

ロボ子

FFTって奥が深いですね。勉強になりました！

博士

ところでロボ子、FFTを知らないプログラマはなんて呼ばれるか知ってるか？

ロボ子

え？知らないです。なんて呼ばれるんですか？

博士

…非FFTプログラマ！…つまらない？