FFT的FFT冻结

Question

在计算大小为150万项的数组的FFT时：

import numpy as np
from scipy.fftpack import fft

x0 = np.ones(1492828, dtype=np.int32)
fft(x0)
print 'hello'

FFT计算永远不会完成，程序也冻结了。如果我将1492828更改为1492827，它似乎会起作用。但是如果我将1492828改为1492826，它仍然会结冰，这有点奇怪。

这是已知的窃听器吗？

注意：

• CPU保持在25% (正常情况下，我有一个4核CPU)，Python进程的RAM使用量保持在75 MB左右。
• 我在Windows 7 64位上使用Python 2.7.15 64位： 打印scipy.__version__ # 1.1.0打印sys.version # 2.7.15 (v2.7.15:ca079a3e3,2018年4月30日，16: 30 :26) MSC v.1500 64位(AMD64)

Answer 1

通常的快速傅立叶变换算法对于长度小的素数因子来说要快得多，正如here所解释的那样。

解决方案是将数组零点到下一个2倍的幂：

def zeropad_nextpoweroftwo(A):
    return np.concatenate([A, np.zeros(int(2 ** np.ceil(np.log2(len(A))))-len(A), 
        dtype=A.dtype)])

或者，更容易/更好的解决方案是使用next_fast_len和fftpack.fft的第二个参数允许自动执行零填充：

fftpack.fft(a, next_fast_len(len(a)))