Multipoint Evaluation

個人的メモ

多項式 $r_0(x)$, $r_1(x)$ を $r_0(x) \overset{\mathrm{def}}{=} \left( f(x) \ \mathrm{mod}\ \Pi_{i = 0}^{m / 2 - 1} (x - u_i) \right)$, $r_1(x) \overset{\mathrm{def}}{=} \left( f(x) \ \mathrm{mod}\ \Pi_{i = m / 2}^{m - 1} (x - u_i) \right)$ と定めると, $f(u_0), \dots, f(u_{m-1})$ の値は $f(u_i) (0 \le i < m / 2)$ については $f(u_i) = r_0(u_i)$ より $r_0$ を用いて, $f(u_i) (m / 2 \le i < m)$ については $f(u_i) = r_1(u_i)$ より $r_1$ を用いて計算することができる. $\Pi_{i = l}^{r} (x - u_i)$ の部分については事前に計算を行なっておく.
つまりサイズが $m / 2$ の問題 2 つに分割することができたことになり, 分割統治法によって $m$ 個のクエリに答えることができる. 割られる側の多項式の長さが $n$ の場合の多項式の除算は $\O (n \log n)$ で行うことができ, 少し工夫すると時間計算量は $\O (\max(n, m) \log^2 n)$ でできることが分かる.
再帰の最後の方(実装では $m \le 32$ となったとき)ではそれ以上再帰をたどらず愚直に計算してしまうことで高速化を行なっている.