Shift of Sampling Points of Polynomialの実装

左辺も右辺も$N$次多項式なので、$f(0), f(1), \dots ,f(N)$で一致することを示す。
$k$が$N$以下の非負整数のとき、
$$ \begin{eqnarray} \sum_{i=0}^{N} \left( \sum_{j=0}^i \frac{(-1)^{i-j}}{(i-j)!j!} f(j) \right) \cdot k^{\underline{i}} &=& \sum_{i=0}^{k} \sum_{j=0}^i \frac{(-1)^{i-j}}{j! (i-j)!} \cdot \frac{k!}{(k-i)!} \cdot f(j) \\ &=& \sum_{j+m+n=k} \frac{(-1)^{m} k! }{j! m! n!} \cdot f(j) \\ \end{eqnarray} $$
ここで
$$ \begin{eqnarray} \sum_{m+n=k} \frac{(-1)^{m}}{m! n!} &=& \frac{1}{k!} \sum_{m+n=k} {}_k C_n (1)^n(-1)^m \\ &=& \frac{1}{k!} (1-1)^k = \left\{ \begin{array}{l} \frac{1}{k!} & (k = 0) \\ 0 & (k > 0) \end{array} \right. \end{eqnarray} $$
なので
$$ \begin{eqnarray} \sum_{j+m+n=k} \frac{(-1)^{m} k! }{j! m! n!} \cdot f(j) &=& f(k) \\ \end{eqnarray} $$
よって、
$$ \sum_{i=0}^{N} \left( \sum_{j=0}^i \frac{(-1)^{i-j}}{(i-j)!j!} f(j) \right) \cdot k^{\underline{i}} = f(k) $$

畳み込みで計算するためには、

$$ \begin{eqnarray} \mathbf{x}_i &=& \left\{ \begin{array}{l} \frac{f(i)}{i!} & (0 \leq i \leq N) \\ 0 & (その他) \end{array} \right. \\ \mathbf{y}_i &=& \left\{ \begin{array}{l} \frac{(-1)^i}{i!} & (0 \leq i \leq N) \\ 0 & (その他) \end{array} \right. \\ (\mathbf{x} * \mathbf{y})_{i} &=& \sum_{j=0}^{i} \frac{(-1)^{i-j}}{(i-j)!j!} f(j) \end{eqnarray} $$

とすればよい

$n$についての帰納法で示す。
$n=0$のとき、$ \displaystyle (x+y)^{\underline{0}} = 1 = {}_0 C_0 x^{\underline{0}} y^{\underline{0}}$で成立
$\displaystyle (x+y)^{\underline{n}} = \sum_{i=0}^{n} {}_n C_i x^{\underline{i}} y^{\underline{n-i}}$を仮定すると、
$$ \begin{eqnarray} (x+y)^{\underline{n+1}} &=& (x+y)^{\underline{n}} \cdot (x + y - n) \\ &=& \sum_{i=0}^{n} {}_n C_i x^{\underline{i}} y^{\underline{n-i}} ( (x-i) + (y-(n-i))) \\ &=& \sum_{i=0}^{n} {}_n C_i x^{\underline{i+1}} y^{\underline{n-i}} + \sum_{i=0}^{n} {}_n C_i x^{\underline{i}} y^{\underline{n-i+1}} \\ &=& \sum_{i=0}^{n+1} {}_n C_{i-1} x^{\underline{i}} y^{\underline{n+1-i}} + {}_n C_{i} x^{\underline{i}} y^{\underline{n+1-i}} \\ &=& \sum_{i=0}^{n+1} {}_{n+1} C_{i} x^{\underline{i}} y^{\underline{n+1-i}} \\ \end{eqnarray} $$
よって示された。

$$ \begin{eqnarray} f(x+c) &=& \sum_{n=0}^{N} \sum_{i=0}^{n} a_n \cdot \frac{n!}{i!(n-i)!} c^{\underline{n-i}} x^{\underline{i}} \\ &=& \sum_{i=0}^{N} \sum_{n=i}^{N} a_n \cdot \frac{n!}{i!(n-i)!} c^{\underline{n-i}} x^{\underline{i}} \\ &=& \sum_{i=0}^{N} \frac{x^{\underline{i}}}{i!} \sum_{n=i}^{N} a_n n! \cdot \frac{c^{\underline{n-i}}}{(n-i)!} \\ &=& \sum_{i=0}^{N} \frac{x^{\underline{i}}}{i!} \sum_{n=i}^{N} a_n n! \cdot \frac{c^{\underline{n-i}}}{(n-i)!} \\ \end{eqnarray} $$
ここで、
$$ \begin{eqnarray} \mathbf{x}_i &=& \left\{ \begin{array}{l} a_i (i!) & (0 \leq i \leq N) \\ 0 & (その他) \end{array} \right. \\ \mathbf{y}_i &=& \left\{ \begin{array}{l} \frac{c^{\underline{N-i}}}{(N-i)!} & (0 \leq i \leq N) \\ 0 & (その他) \end{array} \right. \\ (\mathbf{x} * \mathbf{y})_{N+i} &=& \sum_{n=i}^{N} a_n n! \cdot \frac{c^{\underline{N-(N+i-n)}}}{(N-(N+i-n))!} \\ &=& \sum_{n=i}^{N} a_n n! \cdot \frac{c^{\underline{n-i}}}{(n-i)!} \end{eqnarray} $$
なので、
$$ f(x+c) = \sum_{i=0}^{N} \frac{(\mathbf{x} * \mathbf{y})_{N+i}}{i!} x^{\underline{i}} $$

$$ \begin{eqnarray} f(n) &=& \sum_{i=0}^{N} a_i n^{\underline{i}} \\ &=& \sum_{i=0}^{min(n, N)} a_i n^{\underline{i}} \quad (n < i のときn^{\underline{i}}=0)\\ &=& \sum_{i=0}^{min(n, N)} a_i \frac{n!}{(n-i)!} \\ &=& n! \sum_{i=0}^{min(n, N)} \frac{a_i}{(n-i)!} \\ \end{eqnarray} $$

$0 \leq n \leq M$の部分を畳み込みで計算するためには、

$$ \begin{eqnarray} \mathbf{x}_i &=& \left\{ \begin{array}{l} a_i & (0 \leq i \leq N) \\ 0 & (その他) \end{array} \right. \\ \mathbf{y}_i &=& \left\{ \begin{array}{l} \frac{1}{i!} & (0 \leq i \leq M) \\ 0 & (その他) \end{array} \right. \\ (\mathbf{x} * \mathbf{y})_{i} &=& \sum_{i=0}^{min(n, N)} \frac{a_i}{(n-i)!} \end{eqnarray} $$

とすればよい。

長さ$N$の列と長さ$M$の列の畳み込みは高速フーリエ変換した空間で掛け算をすることにより、$O((N+M)\log(N+M))$で計算できる。
ステップ1と2は長さ$N$と長さ$N$、ステップ3は長さ$N$と長さ$M$の列を畳み込むので、
それぞれ上の計算量で計算でき、全体も$O((N+M)\log(N+M))$で計算できる。