странное числовое значение fft

Question

Во время тестирования я заметил что-то странное.

I'm FFT'ing много векторов, и время от времени функция numpy FFT, казалось, сбой.

Я кратко отладил это и обнаружил, что некоторые длины векторов вызвали поведение.

В результате инцидента я сохранил сценарий, и, к моему удивлению, он не разбился, это просто заняло немного больше времени.

Кто-нибудь имеет представление о том, что происходит, и как противодействовать этому. Я видел это со многими различными размерами FFT, ниже приведен пример.

import numpy as np  
import time 

a = np.zeros(166400) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

a = np.zeros(165039) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

a = np.zeros(165038) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

a = np.zeros(165036) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

a = np.zeros(165035) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

a = np.zeros(165034) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

a = np.zeros(165037) 
start = time.time() 
audio_fft = np.fft.fft(a,len(a))       
print "it took %fs"%(time.time() -start) 

print "done" 

Эти выходы: алгоритмы FFT

c:\Users\sol_sf\Desktop\math>fftTest.py 
it took 0.029000s 
it took 0.101000s 
it took 0.176000s 
it took 0.220000s 
it took 0.671000s 
it took 0.065000s 
it took 369.132000s 
done 

c:\Users\sol_sf\Desktop\math> 

Answer 1

Разделить и властвуй, такие, как Cooley-Tukey, работают намного лучше, чем больше длина факторов вход имеет. Силы 2 работают особенно хорошо, тогда как простые числа (например, 165037) требуют альтернативных, более медленных реализаций. Если вы можете вставить свой вход в длину с длиной-2, вы можете значительно ускорить медленные БПФ.

Answer 2

Я думаю, что сила 2 Перетяжки массива несколько раз имеют ряд недостатков:

1. Если вырезать массив для питания 2 длины он будет производить большое теряет данные для больших массивов
2. Если вы прокладочных массив с нулями, он произведет так называемый «краевой эффект»

Я нашел в этом topic, что производительность fft зависит от простой факторизации массива. Если длина массива является простым числом, это приводит к длительному времени вычисления. Поэтому я предлагаю следующий код, который уменьшает длину массива, ища лучшую факторизацию.

from sympy.ntheory import factorint 

FACTOR_LIMIT = 100 

def bestFFTlength(n): 
    while max(factorint(n)) >= FACTOR_LIMIT: 
     n -= 1 
    return n 

a = np.zeros(166400) 
audio_fft = np.fft.fft(a,bestFFTlength(len(a)))