任意模数的FFT
我现在也不知道是不是对的，反正也只是口胡，如果有错误的话请大家指出。
我们使用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$就能得到答案了。
只要合理的选择质数就能达到这种效果了。
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"
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"
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.
Jul 04, 2024 03:02:20 AM
Befuddling dispatch! I'm reason in truth expecting to over this data, is truly satisfying my mate. In like manner shocking web diary here among wearisome the end data you get. Hold up the best correspondence you are doing here. youibot autonomous mobile robots amr amr robot
Jul 04, 2024 03:02:29 AM
Befuddling dispatch! I'm reason in truth expecting to over this data, is truly satisfying my mate. In like manner shocking web diary here among wearisome the end data you get. Hold up the best correspondence you are doing here. youibot autonomous mobile robots amr amr robot