Shift of Sampling Points of Polynomialの実装

左辺も右辺も$N$次多項式なので、$f(0),f(1),\dots ,f(N)$で一致することを示す。
$k$が$N$以下の非負整数のとき、
$$\begin{array}{rcl}\sum _{i=0}^N(\sum _{j=0}^i\frac{(-1{)}^{i-j}}{(i-j)!j!}f(j))\cdot k^{\underset{―}{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{array}$$
ここで
$$\begin{array}{rcl}\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=\{\begin{array}{cc}\frac{1}{k!}& (k=0)\\ 0& (k>0)\end{array}\end{array}$$
なので
$$\begin{array}{rcl}\sum _{j+m+n=k}\frac{(-1{)}^{m}k!}{j!m!n!}\cdot f(j)& =& f(k)\end{array}$$
よって、
$$\sum _{i=0}^N(\sum _{j=0}^i\frac{(-1{)}^{i-j}}{(i-j)!j!}f(j))\cdot k^{\underset{―}{i}}=f(k)$$

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

$$\begin{array}{rcl}{\mathbf{x}}_i& =& \{\begin{array}{cc}\frac{f(i)}{i!}& (0\le i\le N)\\ 0& (その他)\end{array}\\ {\mathbf{y}}_i& =& \{\begin{array}{cc}\frac{(-1{)}^i}{i!}& (0\le i\le N)\\ 0& (その他)\end{array}\\ (\mathbf{x}\ast \mathbf{y}{)}_i& =& \sum _{j=0}^i\frac{(-1{)}^{i-j}}{(i-j)!j!}f(j)\end{array}$$

とすればよい

$n$についての帰納法で示す。
$n=0$のとき、${\displaystyle (x+y{)}^{\underset{―}{0}}=1={}_0{C}_0{x}^{\underset{―}{0}}{y}^{\underset{―}{0}}}$で成立
${\displaystyle (x+y{)}^{\underset{―}{n}}=\sum _{i=0}^n{}_n{C}_i{x}^{\underset{―}{i}}{y}^{\underset{―}{n-i}}}$を仮定すると、
$$\begin{array}{rcl}(x+y{)}^{\underset{―}{n+1}}& =& (x+y{)}^{\underset{―}{n}}\cdot (x+y-n)\\ & =& \sum _{i=0}^n{}_n{C}_i{x}^{\underset{―}{i}}{y}^{\underset{―}{n-i}}((x-i)+(y-(n-i)))\\ & =& \sum _{i=0}^n{}_n{C}_i{x}^{\underset{―}{i+1}}{y}^{\underset{―}{n-i}}+\sum _{i=0}^n{}_n{C}_i{x}^{\underset{―}{i}}{y}^{\underset{―}{n-i+1}}\\ & =& \sum _{i=0}^{n+1}{}_n{C}_{i-1}{x}^{\underset{―}{i}}{y}^{\underset{―}{n+1-i}}+{}_n{C}_i{x}^{\underset{―}{i}}{y}^{\underset{―}{n+1-i}}\\ & =& \sum _{i=0}^{n+1}{}_{n+1}{C}_i{x}^{\underset{―}{i}}{y}^{\underset{―}{n+1-i}}\end{array}$$
よって示された。

$$\begin{array}{rcl}f(x+c)& =& \sum _{n=0}^N\sum _{i=0}^n{a}_n\cdot \frac{n!}{i!(n-i)!}{c}^{\underset{―}{n-i}}{x}^{\underset{―}{i}}\\ & =& \sum _{i=0}^N\sum _{n=i}^N{a}_n\cdot \frac{n!}{i!(n-i)!}{c}^{\underset{―}{n-i}}{x}^{\underset{―}{i}}\\ & =& \sum _{i=0}^N\frac{x^{\underset{―}{i}}}{i!}\sum _{n=i}^N{a}_{n}n!\cdot \frac{c^{\underset{―}{n-i}}}{(n-i)!}\\ & =& \sum _{i=0}^N\frac{x^{\underset{―}{i}}}{i!}\sum _{n=i}^N{a}_{n}n!\cdot \frac{c^{\underset{―}{n-i}}}{(n-i)!}\end{array}$$
ここで、
$$\begin{array}{rcl}{\mathbf{x}}_i& =& \{\begin{array}{cc}{a}_i(i!)& (0\le i\le N)\\ 0& (その他)\end{array}\\ {\mathbf{y}}_i& =& \{\begin{array}{cc}\frac{c^{\underset{―}{N-i}}}{(N-i)!}& (0\le i\le N)\\ 0& (その他)\end{array}\\ (\mathbf{x}\ast \mathbf{y}{)}_{N+i}& =& \sum _{n=i}^N{a}_{n}n!\cdot \frac{c^{\underset{―}{N-(N+i-n)}}}{(N-(N+i-n))!}\\ & =& \sum _{n=i}^N{a}_{n}n!\cdot \frac{c^{\underset{―}{n-i}}}{(n-i)!}\end{array}$$
なので、
$$f(x+c)=\sum _{i=0}^N\frac{(\mathbf{x}\ast \mathbf{y}{)}_{N+i}}{i!}{x}^{\underset{―}{i}}$$

$$\begin{array}{rcl}f(n)& =& \sum _{i=0}^N{a}_i{n}^{\underset{―}{i}}\\ & =& \sum _{i=0}^{min(n,N)}{a}_i{n}^{\underset{―}{i}}(n<iのときn^{\underset{―}{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{array}$$

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

$$\begin{array}{rcl}{\mathbf{x}}_i& =& \{\begin{array}{cc}{a}_i& (0\le i\le N)\\ 0& (その他)\end{array}\\ {\mathbf{y}}_i& =& \{\begin{array}{cc}\frac{1}{i!}& (0\le i\le M)\\ 0& (その他)\end{array}\\ (\mathbf{x}\ast \mathbf{y}{)}_i& =& \sum _{i=0}^{min(n,N)}\frac{a_i}{(n-i)!}\end{array}$$

とすればよい。

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