Loading...

​​fpsのニュートン法高速化(簡易版)

​​概要

​​サイズ​​$n$​のFFTを行うときの計算量をF(n)と表します。

​​

​​唐突ですが、​​$f$​のinvを計算するニュートン法は次のようなものでした。

​​

​​​​$g_{2n}=g_n-\epsilon_ng_n$​

​​ここで、

​​​​$\epsilon _n =f_ng_n-1$​

​​

​​

​​上記の式をナイーブに計算すると、​​$\epsilon_n$​の計算で​​$3F(4n)$​、​​$g_{2n}$​の計算で​​$3F(4n)$​かかるので、トータル​​$6F(4n)$​回の計算が行われます。

​​

​​

​​寄り道

​​ところで、演算の順序を工夫すると、かなり速くなります(noshiさんが教えてくれた)：

​​​​$g_{2n}=2g_n-(g_n)^2f_n$​

​​

​​​​$(g_n)^2$​の計算を長さ4nのDFTでやることにすると、​​$F(4n)$​で​​$(g_n)^2$​のDFTが手に入って、​​$deg (g_n)^2 < 2n$​であることから、そのまま​​$(g_n)^2 f_n$​の計算に使えます。

​​​​$f_n$​のDFTと、最後のIDFTで​​$2F(4n)$​使うので、トータルで​​$3F(4n)$​となります。

​​これ実装楽だしかなり速いので、とりあえずこの実装を採用するとコスパよい

​​

​​本題

​​​​$g_n$​から​​$g_{2n}$​を​​$5F(2n)$​で得る方法を紹介します。(先ほどの方法と比べると、こちらのほうがサイズ​​$2n$​のFFT 1回分くらいお得です。また、ここで紹介する手法を転用すると、他の演算(quotient,sqrt,log,exp)が2倍くらい速くなったりします。

​​

​​

​​まずは​​$\epsilon_n=f_ng_n-1 \ \ \ mod \ \ \ x^{2n}$​を計算します:

​​​​$G_n$​、​​$F_n$​を、それぞれ​​$g_n$​、​​$f_n$​のサイズ​​$2n$​のDFTとします。これらは、​​$2F(2n)$​回のFFTで計算できます。

​​次に、​​$G_n$​と​​$F_n$​の要素ごとの積をとります。このとき、​​$deg (f_n g_n) \geq 2n$​であることから、循環が発生します。演算結果をIDFTします。(得られた多項式を​​$h_n$​とおきます(​​$deg h_n <2n$​))

​​

​​​​$h_n$​の​​$[0,n)$​次の係数は、実際には​​$f_ng_n$​の​​$[0,n)$​次の係数と​​$[2n,3n)$​次の係数の重ね合わせとなっています(循環畳み込みなので！)

​​同様に、​​$h_n$​の​​$[n,2n)$​次の係数は、​​$f_ng_n$​の​​$[n,2n)$​次の係数と​​$[3n,4n)$​次の係数の重ね合わせになっています。

​​

​​今、​​$f_ng_n$​の​​$[0,2n)$​次の係数だけが欲しいので、困ってしまいます。

​​ところが、​​$f_ng_n \equiv 1 \ mod \ x^n$​なので、​​$[0,n)$​の係数は​​$1,0,0,...$​です。

​​また、​​$deg \ g_n < n$​より​​$deg \ f_ng_n < 3n$​なので、​​$h_n$​の​​$[n,2n)$​次の係数(​​$f_ng_n$​の​​$[n,2n)$​次の係数と​​$[3n,4n)$​次の係数の重ね合わせ)は、実際には​​$f_ng_n$​の​​$[n,2n)$​次の係数と一致します。

​​

​​上記の計算量は​​$3F(2n)$​です。

​​

​​→解決

​​

​​

​​上記の手法の本質は、​​$f_ng_n$​の​​$[0,n)$​次と​​$[3n,4n)$​次の係数が分かっているおかげで、(サイズを2倍せずに)普通に循環畳み込みをやっても、各係数を復元できることです。

​​

​​次に、

​​​​$g_{2n}=g_n-\epsilon_n g_n$​

​​の計算を考えます。先ほどと同様に​​$deg \ g_n < n$​なので、​​$\epsilon _n g_n$​の​​$[3n,4n)$​次の係数は0です。また、

​​​​$\epsilon_n$​の​​$[0,n)$​次の係数は0(これは、すぐにわかります)なので、​​$\epsilon_ng_n$​の​​$[0,n)$​次の係数は0です。

​​従って先ほどと同様に循環畳み込みを用いることができて、​​$3F(2n)$​回の計算で出来ます。

​​ところで、​​$g_n$​のサイズ​​$2n$​のDFTは使いまわせるので、​​$F(2n)$​回の計算を削減することができて、全体で​​$5F(2n)$​回でできます。