「学习笔记」Bluestein's FFT Algorithm 任意长度卷积算法

简略介绍Bluestein’s FFT Algorithm,一种用于计算任意长度卷积的算法。

适用范围

简而言之,仅适用于存在单位根的情况

  1. 显然FFT可以,$\omega_n=e^{\frac{2\pi i}{n}}$
  2. NTT需满足$n\mid (Mod - 1),\omega_n=g^\frac{Mod-1}{n}$

推式子

考虑DFT的实质:求单位根处的点值。

设$f(x)=\sum\limits^n_{i=0}a_ix^i$

$f(\omega_n^k)=\sum\limits^n_{i=0}a_i\omega_n^{ik}$

考虑$ik=\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}$(用组合意义或暴力拆开都易证明)

$\begin{aligned}f(\omega_n^k)&=\sum\limits^n_{i=0}a_i\omega_n^{\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}}\\&=\omega_n^{-\binom{k}{2}}\sum\limits^n_{i=0}a_i\omega_n^{-\binom{i}{2}}\omega_n^\binom{i+k}{2}\end{aligned}$

考虑转为卷积的形式,不难发现$(n-i)+(i+k)=n+k$

设$g(x)=\sum\limits^n_{i=0}a_i\omega_n^{-\binom{i}{2}}x^{n-i}$和$h(x)=\sum\limits^{2n}_{i=0}\omega^{\binom{i}{2}}x^i$

$f(\omega_n^k)=\omega^{-\binom{k}{2}}\times([x^{n+k}]g(x)\times h(x))$

考虑IDFT即为对所有单位根取到数后跑DFT,将上文中所有二项式系数取相反数即可。

代码较为简单,不放了

应用

一般算卷积直接拓展到$2$的次幂即可,需要用到的场景主要为任意长度循环卷积,即$a_i\times b_j\rightarrow c_{(i+j)\operatorname{mod}n}$

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/Bluestein/