多项式桶1-NTT(快速数论变换以及任意模数形式)以及FFT的一点杂谈

目录

FFT杂谈

因为之前的我已经不想去动他了。QAQ

其实FFT并不难学,大纲是这样:

  1. 前置知识
  2. 分治
  3. 蝴蝶变换
  4. 学完了,没了

之前那个前面不是是抄你谷多项式奆佬的,后面的各种优化没什么实际意义还疯狂掉精度,基本在实战中不会去碰他,所以那篇文章我可以说是弃飞了。

FFT的前置知识并不多,向量和单位根,向量相乘的两个性质一个用相似,一个用两点距离公式爆算都能证明,也就没什么难度。

会用到的性质:

  1. 向量相乘模相乘
  2. 向量相乘辐角相加

单位根的定义百度一下,你就知道。

当然,单位根用到的性质在下面列出来了:

  1. \(w_{n}^0=1,w_{n}^k=w_{n}^{k\mod n}\)
  2. {\(x∈C\)|\(x=w_{n}^i(i∈[0,n-1],i∈Z)\)}的元素个数是\(n-1\)个(其实意思就是\(w_{n}^i\)互不相等)
  3. \(w_{n}^k=w_{2n}^{2k}\)
  4. \(w_{n}^k=-w_{n}^{k+\frac{n}{2}}(n≡0\mod2)\)
  5. \(\sum\limits_{i=0}^{n-1}(w_{n}^{j-k})^i=n*[j=k]\)(\([A]\)表示如果\(A\)条件成立,则\([A]=1\),否则为\(0\))
  6. \(w_{n}^k*w_{n}^t=w_{n}^{k+t}\)

只要用到这几个性质,就可以完美的推导出FFT。

这里也不展开,主要就是奇偶分治。

至于蝴蝶迭代,这个我之前的博客也就,在这里就不展开了,代码以前也是有的,我看了一下,我之前的代码长得还行(⊙﹏⊙)。

但是如果这里就这么一点东西,那我还做个P的杂谈啊(╯‵□′)╯︵┻━┻

首先,关于快速傅里叶变换,你可以觉得其很神奇,因为他巧妙的利用了单位根的性质,之前那个IDFT的推导,也很神奇,好像一气呵成似的。

当然,这里介绍一种不同的理解方式(听说卷积跟线性代数有关,但是那个我不会,就不展开了)

其实你会发现,其实DFT和IDFT就是一个\(1*n\)的矩阵乘一个\(n*n\)的矩阵的过程,所以理论上只要\(IDFT\)和\(DFT\)的矩阵互逆,这样就可以完美的相互抵消。

当然,DFT中的矩阵叫范德蒙德矩阵。

图片来自参考链接的奆佬博客Orz中
多项式桶1-NTT(快速数论变换以及任意模数形式)以及FFT的一点杂谈
所以,这看似运气十足的FFT背后也有其科学的数学道理。

NTT

全称:快速速论变换

请注意,本文中对于一个多项式模一个整数,只是对每一个系数取模而已。

优点:

  1. 全是整数,不用担心掉精度的问题。
  2. 可以计算特定模数的卷积。
  3. 因为不用计算复数,所以乘法少了不少,貌似常数加快了b( ̄▽ ̄)d 。

缺点:

  1. 不能计算小数,过程涉及到取模,所以一旦数域超过了模数,就难以计算。
  2. 模数必须是\(k*2^t+1\)的形式,且必须是一个质数。
  3. 由于模运算比较慢,所以常数经常不如FFT。

你是不是以为NTT十分的妙?

不,其实就是FFT的过程然后把单位根换了一个更加神奇的东西。

上面也列了,我们会利用到单位根的一些性质,但是其实只要我们能在整数中找到一个同样能满足上述性质的东西,就可以完美的换成整数啦。

当然,在一般的整数域我们很难找到满足条件的数字。

但是如果套上一个模,如果这个模有原根,则有个与原根相关的东西刚好可以满足上面。

设模为\(p\),\(p\)是形式为\(k*2^t+1\)形式的质数,同时原根为\(g\)。

(原根定义:在模\(p\)的时候,如果对于\(n\),\(φ(p)\)是最小的正整数 \(t\) 满足 \(n^t≡1\),则 \(n\) 为\(p的原根\), \(φ(p)\)表示小于\(p\)的正整数中与 \(p\) 互质的数字个数)

则我们可以把\(w_{n}^i\)替换成\(g^{\frac{p-1}{n}*i}\)(假设\(n|p-1\)),用\(g_{n}^i\)简化符号。

当然,其是否满足上面的式子,我们来看一下:

  1. \(g_{n}^0≡1,g_{n}^i≡g_{n}^{i\mod n}\)
    证明:\(g_{n}^0≡g^0=1\),将 \(i\) 表示成 \(kn+t(0≤t<n)\) 的形式,所以\(g_{n}^i≡g_{n}^{kn+t}≡g^{\frac{p-1}{n}*(kn+t)}≡g^{\frac{p-1}{n}*kn}*g^{\frac{p-1}{n}*t}≡g^{\frac{p-1}{n}*t}≡g_{n}^t\),证毕,同理,因为都等于\(g_{n}^t\),所以\(g_{n}^i≡g_{n}^{i±n}\)
  2. {\(x∈Z\)|\(x=g_{n}^i(i∈[0,n-1],i∈Z)\)}的元素个数是\(n-1\)个(意思就是\(g_{n}^i\)互不相等)
    证明:假设\(g_{n}^i≡g_{n}^j(i>j)\)
    \(g^{\frac{p-1}{n}*i}≡g^{\frac{p-1}{n}}*j\)
    \((g^{\frac{p-1}{n}*(i-j)}-1)*g^{\frac{p-1}{n}*j}≡0\)
    那么\(p|(g^{\frac{p-1}{n}*(i-j)}-1)*g^{\frac{p-1}{n}*j}\),但是如果\(p∤g\),则\(p∤p^k(k∈Z^{*})\)
    所以\(p|(g^{\frac{p-1}{n}*(i-j)}-1)\)
    所以\(g^{\frac{p-1}{n}*(i-j)}≡1\),这显然是不成立的,因为\(\frac{p-1}{n}*(i-j)<p-1=φ(p)\)
  3. \(g_{n}^i≡g_{2n}^{2i}\)
    证明:\(g_{n}^i≡g^{\frac{p-1}{n}*i}≡g^{\frac{p-1}{2n}*2i}\)。
  4. \(g_{n}^i≡-g_{n}^{i+\frac{n}{2}}(2|n)\)
    证明:\(g_{n}^{i+\frac{n}{2}}≡g^{\frac{p-1}{n}*(i+\frac{n}{2})}≡g^{\frac{p-1}{n}*i}*g^{\frac{p-1}{n}*\frac{n}{2}}≡g_{n}^i*g^{\frac{p-1}{2}}=-g_{n}^i\)
    当然,至于为什么\(g^{\frac{p-1}{2}}≡-1\),我们还需要证明一个东西:
    对于模质数\(p\),\(x^2≡1\)的解只有两个\(1,-1\)(或者说是其的同余)。
    \(x^2≡1\)
    则\((x+1)(x-1)≡0\),那么\(p|(x+1)\)或者\(p|(x-1)\),所以\(x≡p+1≡1\)或\(x=p-1≡-1\)。
    但是因为\(g\)是原根,所以\(g^{\frac{p-1}{2}}\)只能是\(-1\)。
  5. \(g_{n}^{i}*g_{n}^j≡g^{i+j}_{n}\)。
    5,6点换了一个顺序,海星。
    证明:展开即可,没什么好说的
  6. \(\sum\limits_{i=0}^{n-1}(g_{n}^{j-k})^i≡n*[j=k]\)
    证明:其实完全没有什么必要证明的,反正这个东西只要用相同的性质套到FFT中便可以证明了:
    先求\(\sum\limits_{i=0}^{n-1}(g_{n}^j)i\)
    当\(j≠0\)时
    \(\sum\limits_{i=0}^{n-1}(g_{n}^j)i≡\frac{g_{n}^{nj}-1}{g_{n}^j-1}≡0\)。
    但是,如果\(j=0\)
    那么显然\(\sum\limits_{i=0}^{n-1}(g_{n}^j)i≡n\)
    那么什么时候\(j=0\)呢?也就是上述式子中的\(j=k\)时成立,证毕。

然后就没有什么了,直接把代码中的单位根换成\(g\),就可以求解了,但是,仅适用于整数卷积。

当然,需要注意的是:

  1. \(g_{n}^i\)中\(n\)必须整除\(p-1\),而\(FFT\)中\(n=2^i(i∈[1,r])\),所以\(p=k*2^{t}+1\)就是这么一个道理。
  2. 同样的,对于补充到\(2\)的次幂的多项式长度\(len'=2^r\),我们要求\(r<=t\),所以对于原来的多项式长度\(len\),我们要求\(len≤2^t\),所以\(p\)的\(2^t\)要尽可能的大,那是最好的。
  3. 其次,值域的上届减下界\(+1\)要小于\(p\),因为模\(p\)最怕的就是在值域中有两个数字同余。
  4. 对于\(g_{n}^i(i<0)\),此时\(g_{n}^i≡\frac{1}{g^{\frac{p-1}{n}*(-i)}}≡(\frac{1}{g})^{\frac{p-1}{n}*(-i)}\),所以只要求出\(g\)的逆就可以计算\(g_{n}^i(i<0)\)了,当然,\(g\)的逆也是一个原根,证明如下:
    \(g'^{i}≡(g^i)'\)(其中\(x'\)表示\(x\)的逆)
    而\(1\)的逆是其本身,且因为一个数不存在两个不同余的逆,所以很容易知道\(g'\)也是原根。
  5. 在IDFT中应当用\(g_{n}^{-i}\)替换\(w_{n}^i\),应该不会只有我一个憨憨用\(-g_{n}^i\)去代替吧QAQ。
  6. 在最后输出除长度\(n\)时,需要注意的是,不能直接除\(p\),即使值域中的每个数字都小于\(p\),因为虽然值域的长度小于\(p\),但是不代表要求值域的长度\(*n\)以后还小于\(p\),所以还是乘 \(n'\) 的更加保险,当然,如果你这值域长度小的可怜,当我没说。
  7. 没什么好提示了,还不快去
上一篇:拉格朗日插值2


下一篇:Python:用于验证模式和自定义错误消息的jsonschema包