はじめに

前回の記事で形式的冪級数の逆元を求める式を書いたのですが, $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 することになるためです

つまり,

とすることで, 回数を減らします

ここで注意なのが, DFT するときに元の数列の長さを $N = 2^n$ とすると普段は長さ $2N$ で計算すればよかったですが今回は $4N$ 必要だということです

三つかけるので補間のために最終的な次数の分計算しないといけないわけですね

これによってどれくらい速くなるのかですが, もともとは

長さ $2N$ の DFT 二回 $+$ 長さ $2N$ の IDFT 一回
$+$ 長さ $4N$ の DFT 二回 $+$ 長さ $4N$ の IDFT 一回

だったのが

長さ $4N$ の DFT 二回 $+$ 長さ $4N$ の IDFT 一回

だけで済みます

うれしい！

実装量のわりに結構速くなるのでおすすめです

とはいえ循環をうまく利用する？やつもいつかは理解しないとね...