我是新来的FFTs，所以我对一些概念有点困惑到目前为止，我所看到的方程乘法的fft例子涉及具有连续指数的方程（即A(x) = 1 + 3x + 5x^2 +...和B(x) = 4 + 6x + 9x^2 + ...以及C(x) = A(x)*B(x)）。然而，有可能对两个指数不相等的方程使用FFT例如，是否可以使用FFT进行乘法：
A(x) = 1 + 3x^2 + 9x^8
和
B(x) = 5x + 6 x^3 + 10x^8
在
O(nlogn)时间内？如果不是，是否存在运行时将
O(nlogn)的情况？例如，如果产品中的术语数是O(n)而不是O(n^2)？即使运行时大于
O(nlogn)，我们如何使用FFT来最小化运行时？ 最佳答案
是的，可以对非等指数多项式使用DFFT。。。
丢失的指数只是乘以0这也是一个数字…只要重写你的多项式：
A(x) = 1 + 3x^2 + 9x^8
B(x) = 5x + 6x^3 + 10x^8
像这样的：
A(x) = 1x^0 + 0x^1 + 3x^2 + 0x^3 + 0x^4+ 0x^5+ 0x^6+ 0x^7 + 9x^8
B(x) = 0x^0 + 5x^1 + 0x^2 + 6x^3 + 0x^4+ 0x^5+ 0x^6+ 0x^7 + 10x^8
所以DFFT的向量是：
A = (1,0,3,0,0,0,0,0, 9)
B = (0,5,0,6,0,0,0,0,10)
加上0，则向量是正确的结果大小（max a exponent+1+max b exponent+1），对于dfft的使用，也可以舍入到最接近的
2幂，因此原始大小9,9 -> 9+9 -> 18 -> round up -> 32A = (1,0,3,0,0,0,0,0, 9,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0)
B = (0,5,0,6,0,0,0,0,10,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0)
// | original | correct result | nearest power of 2 |
做你想做的事…我想你想做这样的事：
A' = DFFT(A)
B' = DFFT(B)
C(i)' = A'(i) * B'(i) // i=0..n-1
C= IDFFT(C')
即
O(n*log(n))不要忘记，如果使用dfft（非dft）n=32而不是18！！！因为对于DFT的快速算法来说，n必须是2的幂，而且如果您希望性能的改进，而不是查看DFFT（A）的DFFT权重矩阵，DFFT（B）它们是相同的，因此不需要计算两次。。。