CODEWITHSUNDEEP
pythonnumpyscipyfftfftpack
Basj
Basj

Reputation: 46453

scipy.fftpack's FFT freezing

When computing a FFT of an array of size ~ 1.5 million items:

import numpy as np
from scipy.fftpack import fft

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

the FFT computation never finishes, and the program is freezing. If I change 1492828 to 1492827, it seems to work. But if I change 1492828 to 1492826, it still freezes, which is kind of strange.

Is this a known bug?

Note:

Upvotes: 0

Views: 396

Answers (1)

Basj
Basj

Reputation: 46453

The usual FFT algorithms are much faster for length having small prime factors, as explained here.

The solution is to zero-pad the array to the next power of 2:

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

Or, an even easier/nicer solution is to use next_fast_len and the fact that the 2nd argument of fftpack.fft allows to do zero-padding automatically:

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

Upvotes: 3

Related Questions