清华集训总结

任意模数的FFT

shinbokuow posted @ Jan 05, 2016 03:54:59 PM in Something with tags FFT 中国剩余定理 NTT , 3667 阅读

 

我现在也不知道是不是对的,反正也只是口胡,如果有错误的话请大家指出。

我们使用NTT对两个长度均为$n$的序列进行FFT,需要模数$P$为质数,且$P=2^{k}+1$,其中$2^k\geq{n}$。

这样的话,并不是所有的模数都能满足这个条件的。

但是,我们考虑直接算出卷积而不进行取模,这样卷积序列的每个位置上的数字大小必定不超过$P^2n$。

这样的话,我们可以选择若干能够进行NTT的质数$p_1,p_2,...,p_m$,使得$N=\prod_{i=1}^{m}p_i>P^2n$,我们对于这些质数均进行一次NTT,对于结果再使用CRT合并起来,得到的就是在模$N$意义下的卷积,实际上就是这个卷积本身,再取出每个系数模上$P$就能得到答案了。

只要合理的选择质数就能达到这种效果了。

Alyssa 说:
Jan 10, 2023 07:42:19 PM

"The discrete Fourier transform (DFT) of a sequence is defined as a sequence of Phasors. Given a sequence $x[n]$, its DFT is given by: $$X[k] = \sum_{n=0}^{N-1} x[n] \; e^{-i 2 \pi \frac{kn}{N}} \;\;\;\; k=0,1,2,...,N-1 $$ where $N$ is the length of the sequence. If we <a href="http://charnastewart.com/properties/sold/">real estate companies Cohutta</a> let $N$ be a power of 2, i.e. $N=2^m$, then the DFT can be computed using the Fast Fourier Transform"

milan 说:
Jan 10, 2023 07:43:07 PM

"The discrete Fourier transform (DFT) of a sequence is defined as real estate companies Cohutta a sequence of Phasors. Given a sequence $x[n]$, its DFT is given by: $$X[k] = \sum_{n=0}^{N-1} x[n] \; e^{-i 2 \pi \frac{kn}{N}} \;\;\;\; k=0,1,2,...,N-1 $$ where $N$ is the length of the sequence. If we let $N$ be a power of 2, i.e. $N=2^m$, then the DFT can be computed using the Fast Fourier Transform"

Emma 说:
Jan 12, 2023 01:37:35 PM

The Fast Fourier Transform (FFT) is a more efficient way to calculate the Discrete Fourier Transform (DFT). The FFT can be used on any modulus, but it is most efficient when the <a href="http://berkshirecountyma4sale.com">real estate services Great Barrington</a> number of data points is a power of 2. The FFT is a divide and conquer algorithm that breaks down a dataset into smaller pieces, then recombines them to form the final result. The FFT is faster than the DFT because it takes advantage of the symmetry of the data.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter