python - numpy fft 对于小素数乘积的长度很快，但是有多小？

Question

我见过几个例子，表明如果输入长度是 2、3、5、7 等的乘积，那么 numpy 的 fft 实现速度很快。但是这里仍然被认为是“小”的最大素数是多少？

Answer 1

请注意，scipy 的 FFT 的基数为 2、3、4 和 5 (reference)。我假设 numpy 可能有类似的实现，这将使 5 成为 FFT 长度中最大的有效质因数。

---

根据经验，出于 FFT 性能的目的，我认为“小”的最大质数是 11。但是任何小于 30 的输入长度对于实际目的来说都非常快。任何算法性能的提升肯定会因 Python 的执行开销而相形见绌。对于更高的输入长度，事情会变得更有趣。

以下是小型 FFT 的一些性能结果(超过 500 个批处理，每个批处理 1000 个 FFT 的中值执行时间):

我已经标记素值n红色为二次幂，绿色为二次幂。

标记以下观察结果:

• 一般来说，FFT 对于素数的速度较慢，但​​对于二次方的速度则很快。这在意料之中并验证了结果。

• n <=11 没有性能差异是可衡量的。这可能是由于 FFT 实现或执行开销所致。

• 31(可能是 29)及更高的素数显然比附近的其他值慢。

• 有一些非二次幂的值也能提供良好的性能。这可能是高度合数。

测量是这样进行的:

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as time


N = np.arange(2, 65)
times = np.empty((500, N.size))
for i, n in enumerate(N):
    for r in range(times.shape[0]):
        x = np.random.randn(1000, n)
        t = time()
        y = np.fft.fft(x, axis=-1)
        t = time() - t
        times[r, i] = t


med = np.median(times, axis=0)
plt.plot(N, med, 'k')

primes = np.array([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61])
plt.plot(primes, med[primes-2]+0.0005, 'rx', label='n = prime')

ptwos = np.array([2, 4, 8, 16, 32, 64])
plt.plot(ptwos, med[ptwos-2]-0.0005, 'gx', label='n = 2**k')

plt.legend(loc='best')
plt.xlabel('n')
plt.ylabel('time')
plt.grid()
plt.show()