はじめに
前回の記事 で形式的冪級数の逆元を求める式を書いたのですが, $O(n\log n)$ とはいってもなかなかに定数倍が重いです
NTT-friendly な mod で計算する場合は, もっと定数倍が高速な方法が知られています
が公開されていました
ところで, 僕はこれを全く理解していません
僕のような初心者には厳しいので, 軽い実装でそこそこ高速になる方法を紹介します (と思ったんですが, 一個目の記事に載っていました...)
本文
前回
g_{n + 1} = 2g_n - f g_n^2
というような漸化式で計算していけばいい と書きましたが, $f g_n^2$ の計算が重いです
そこで, ここを少し速くすることを考えましょう
$g_n^2$ の計算をするとき, まず DFT をして要素ごとに二乗して IDFT をしていると思います
ここで, DFT をして要素ごとに二乗してそのままにしてみましょう
IDFT をしてもどうせ $f$ をかけるのでまた DFT することになるためです
つまり,
- $f, g_n$ の DFT を計算する
- $f g_n^2$ を DFT した先で要素ごとに計算する
- 最後に一回だけ IDFT する
とすることで, 回数を減らします
ここで注意なのが, DFT するときに元の数列の長さを $N = 2^n$ とすると普段は長さ $2N$ で計算すればよかったですが今回は $4N$ 必要だということです
三つかけるので補間のために最終的な次数の分計算しないといけないわけですね
これによってどれくらい速くなるのかですが, もともとは
長さ $2N$ の DFT 二回 $+$ 長さ $2N$ の IDFT 一回
$+$ 長さ $4N$ の DFT 二回 $+$ 長さ $4N$ の IDFT 一回
だったのが
長さ $4N$ の DFT 二回 $+$ 長さ $4N$ の IDFT 一回
だけで済みます
うれしい！
終わりに
実装量のわりに結構速くなるのでおすすめです
とはいえ 循環をうまく利用する？ やつもいつかは理解しないとね...