競プロをはじめた家事手伝いロボットのブログ

競技プログラミングをしている家事手伝いロボットのブログです

FFTもDFTもNTTもFMTもよくわからないところから始める任意mod畳み込み(WIP)

はじめに

畳み込みを任意のmodで計算できると嬉しいですよね！私も嬉しいので書こうと思ったんですけどよく知らなかったので書けませんでした！

ということで、この記事では畳み込みをフーリエ変換でいい感じ(\mathcal{O}(N\log N))にするまでを調べて書きます
私が理解したところまで書くので、追記に次ぐ追記になる予定です！
はじめの方は「いかがでしたか？」レベルでふわふわなことが書かれていきます 後半はがんばります

畳み込み とは？

畳み込み

長さ n の2つの列 (a_k) と (b_k) について、それらの畳み込みとは、次を満たす長さ 2n の列 (c_k) のことである。

\displaystyle c_i=\sum^{i}_{j=0}a_jb_{i-j}
ただし、便宜上 n\leqq i に対する a_i,b_i は 0 とする。

畳み込みは2つの列に関する操作です！
和と積の定義された任意のものについて畳み込みを考えることができて、愚直に実装すると \mathcal{O}(N^2) のものを書くことができます

フーリエ変換 とは？

フーリエ変換、音声処理や関数解析の文脈でしか聞いたことがありませんでした。みなさんはどうですか？

フーリエ変換は、関数をまた別の関数に変換するものです。

フーリエ変換

|f(x)| が (-\infty,\infty) 上可積分であるとき、fのフーリエ変換とは、\displaystyle\hat{f}(\xi)=\int^\infty_{-\infty}f(x)e^{-2\pi ix\xi}dx で定まる関数 \hat{f} である。

これは少なくとも\mathbb{R}上の関数の話っぽいので、あんまり数列に関係ある気がしてきません

そこで出てくるのが離散フーリエ変換(DFT)です

離散フーリエ変換(DFT) とは？

その前に、数列とは何かを少し考えてみましょう
数列は数が並んだ列ですが、整数 n を入れると n 番目の数を返してくれる関数とも言えます

n -> a[n] // 数列
n -> f(n) // 関数 この2つは同じ

このように、定義域が整数になるような関数に対してもフーリエ変換みたいなことができたら嬉しそうです
実際、フーリエ変換みたいなことを考えることができ、これを 離散フーリエ変換(DFT, Discrete Fourier Transform) といいます。

離散フーリエ変換は、数列をまた別の数列(関数)に変換するものです。

離散フーリエ変換

\mathbb{Z}上で定義された関数fの離散フーリエ変換とは、\displaystyle\hat{f}(t)=\sum^{N-1}_{i=0}f(i)e^{\frac{-2\pi ixt}{N}}dx で定まる関数 \hat{f} である。

競技プログラミングで使われている定義とはちょっと違うので困るかもしれません(高速フーリエ変換 こことか FFT で高速に畳込みを計算する - もう更新しません こことかでは数列を係数にもつ多項式を考えてごにょごにょしています。発祥はどこなのでしょう...?)

もちろん、\hat{f} も定義域を \mathbb{Z} に限定すると数列と考えることができます。

そして、変換があれば多くの場合逆変換もあります。[要出典]

フーリエ変換も例に漏れず、逆フーリエ変換が存在しています。ですが、これはフーリエ変換を少し変えるだけで実現できてわかりやすいので、詳しくは解説しません。定数倍をよしなにするとなんとなんとかなります。

さて、この離散フーリエ変換に関して、一つ成り立つ定理があります。この定理が今回のテーマのキモです。

畳み込み定理

畳み込み定理

それぞれ長さ n の数列 (a_k),(b_k) およびその畳み込み (c_k) について、その離散フーリエ変換をそれぞれ (\hat{a}_k),(\hat{b}_k),(\hat{c}_k) とする。ただし、離散フーリエ変換に使う自然数 N は2n より大きいとする。
このとき、次が成り立つ。

\hat{c}_j = \hat{a}_j \hat{b}_j

畳み込みを \ast 、 項ごとの積を \times とすると、見慣れた(かもしれない)式 \widehat{a\ast b}=\hat{a}\times\hat{b} となります。

証明は、定義にもどって \displaystyle \hat{c}_j=\sum_{k=0}^{N-1} \sum_{l=0}^{N-1}a_l b_{k-l} e^{\frac{-2\pi ijk}{N}} を計算していくと出ます。

ここまでの結果から、普通は\mathcal{O}(n^2)かかっていた畳み込みの処理が、\mathcal{O}(n)回の項ごとの掛け算に帰着されることがわかりました！！！すごい！！
これでDFTが早ければ終了なのですが、DFTはそのまま実装すると\mathcal{O}(n^2)になります！ががーん！

ですが、DFTが高速化できれば畳み込みが高速化できることがわかりました。そして実際そのようなものは考案されていて、次節からはDFTの高速化であるFFTについてがはじまります。

// FFT 実装はできました まだちょっと記事を書くにはわかり度が足りません...

// 任意mod畳み込み実装できました！ わーい！ まだちょっと記事を書くには実装が汚いのでがんばります

ここまではわかる <- ここまでわかるゲージ 理解が進むと下がります それに伴って内容が増えます