Biraz sıra dışı bir sorunum var, ancak FFT'yi yeniden kodlamaktan kaçınmaya çalışıyorum. GeneldeGenel programlama: Log FFT VEYA yüksek hassasiyetli evrişim (python)
, bunu bilmek istiyorum: Ben tip float için uygulanan bir algoritma var, ama varsa operasyonların belirli seti de tanımladığımız için (örneğin karmaşık sayılar, tanımlanan her yerde işe yarar mıydı +, *, ...), bu algoritmayı bu işlemleri destekleyen başka bir türde kullanmanın en iyi yolu nedir? Pratikte bu zordur, çünkü genel olarak sayısal algoritmalar, genel olarak değil hız için yazılır. Özellikle
:
Ben çok yüksek dinamik aralığı ile değerlerle çalışıyorum ve bu yüzden günlük alanda toplama olanağı istiyorum (çoğunlukla Yetersizlik durumu önlemek için).
x = [1,2,3,4,5]
fft_x = [ log(x_val) for x_val in fft(x) ]
Hatta bu önemli boşalmasına neden olur:
Ne istediğim bazı serilerinin FFT günlüğüdür. Ne istiyorum vb Bunun nasıl Benim düşünce bu ilkel işlemleri tanımlayan basit LogFloat sınıfını uygulamaktı
(günlük değerlerini saklamak ve+ yerine
* ve
logaddexp yerine
+ kullanmaktır ancak günlük alanında çalışır). Ardından, kayıtlı değerlerimi kullanmasına izin vererek FFT kodunu çalıştırabilirim.
x_log_float = [ LogFloat.from_float(x_val) for x_val in x ]
fft_x_log_float = fft(x_log_float)
Bu kesinlikle ben FFT yeniden uygulamak durumunda yapılan (ve basitçe yapılabilir:
class LogFloat:
def __init__(self, sign, log_val):
assert(float(sign) in (-1, 1))
self.sign = int(sign)
self.log_val = log_val
@staticmethod
def from_float(fval):
return LogFloat(sign(fval), log(abs(fval)))
def __imul__(self, lf):
self.sign *= lf.sign
self.log_val += lf.log_val
return self
def __idiv__(self, lf):
self.sign *= lf.sign
self.log_val -= lf.log_val
return self
def __iadd__(self, lf):
if self.sign == lf.sign:
self.log_val = logaddexp(self.log_val, lf.log_val)
else:
# subtract the smaller magnitude from the larger
if self.log_val > lf.log_val:
self.log_val = log_sub(self.log_val, lf.log_val)
else:
self.log_val = log_sub(lf.log_val, self.log_val)
self.sign *= -1
return self
def __isub__(self, lf):
self.__iadd__(LogFloat(-1 * lf.sign, lf.log_val))
return self
def __pow__(self, lf):
# note: there may be a way to do this without exponentiating
# if the exponent is 0, always return 1
# print self, '**', lf
if lf.log_val == -float('inf'):
return LogFloat.from_float(1.0)
lf_value = lf.sign * math.exp(lf.log_val)
if self.sign == -1:
# note: in this case, lf_value must be an integer
return LogFloat(self.sign**int(lf_value), self.log_val * lf_value)
return LogFloat(self.sign, self.log_val * lf_value)
def __mul__(self, lf):
temp = LogFloat(self.sign, self.log_val)
temp *= lf
return temp
def __div__(self, lf):
temp = LogFloat(self.sign, self.log_val)
temp /= lf
return temp
def __add__(self, lf):
temp = LogFloat(self.sign, self.log_val)
temp += lf
return temp
def __sub__(self, lf):
temp = LogFloat(self.sign, self.log_val)
temp -= lf
return temp
def __str__(self):
result = str(self.sign * math.exp(self.log_val)) + '('
if self.sign == -1:
result += '-'
result += 'e^' + str(self.log_val) + ')'
return result
def __neg__(self):
return LogFloat(-self.sign, self.log_val)
def __radd__(self, val):
# for sum
if val == 0:
return self
return self + val
Sonra fikri LogFloat s listesini oluşturur ve daha sonra FFT kullanmak olacaktır LogFloat'u, daha önce float kullanıyorum nerede kullanın, ama tavsiye isteyeceğimi düşündüm. Bu oldukça yinelenen bir sorundur: Günlük uzayda çalışmak istediğim bir stok algoritmam var (ve sadece bir kaç işlem kullanır. ',' - ',' ','/', vb).
Bu, genel işlevlerin şablonlarla yazılmasını hatırlatır, böylece geri dönüş argümanları, parametreler vb. Aynı türden oluşturulur. Örneğin, eğer bir FFT şamandıra yapabilirseniz, karmaşık değerlerde kolayca yapabilmelisiniz (sadece karmaşık değerler için gerekli işlemleri sağlayan bir sınıf kullanarak).
Şu anda olduğu gibi, tüm FFT uygulamalarının kanama hızı için yazıldığını görüyoruz ve bu yüzden çok genel olmayacak. Yani bugün itibariyle ben çok yüksek duyarlıklı helezonlar (ve N^2 çalışma zamanı istediğim için ... jenerik türleri için
bunun ne yapıyorum nedeni FFT tekrar uygulamanız gerekir gibi görünüyor son derece yavaştır). Herhangi bir tavsiye büyük takdir edilecektir.
* Not, LogFloat için trigonometrik işlevler uygulamak gerekebilir ve bu iyi olurdu.
DÜZENLEME: LogFloat değişmeli bir halka (ve LogFloat için trigonometrik fonksiyonlar uygulanmasını gerektirmez) olduğu için bu işi yapar.Bunu yapmanın en basit yolu, FFT'yi yeniden düzenlemekti, fakat @ J.F.Sebastian, FFT'yi kodlamadan kaçınan Python genel konvolüsyonunu kullanmanın bir yolunu da işaret etti (ki bu da bir DSP ders kitabını veya the Wikipedia pseudocode'u kullanarak oldukça kolaydı).
Sorununuzun ne olduğundan emin değilim. Eğer fft python dilinde yazılıyorsa, o zaman yukarıdaki (idol kabiliyetli delilik) çalışmalıdır. Eğer bir c uygulamasına çağırırsa o zaman işe yaramaz, çünkü c kodu, python'un yapacağı şeyi yapmayacak c kodudur. sorusu nedir? –
[genel konvolüsyon] var (http://www.math.ucla.edu/~jimc/mathnet_d/sage/reference/sage/rings/polynomial/convolution.html). "LogFloat", alt akışla başa çıkmak için en iyi yaklaşım olmayabilir. – jfs
DSP ders kitaplarındaki ve öğretici web sitelerinde bulunan çok sayıda FFT, çok basit FFT kaynak kodu örnekleri sunar; genellikle yaklaşık 1 veya 2 sayfa kod. (DSP web sitemde sadece 30 ila 40 satırlık BASIC olan bir çift FFT var.) – hotpaw2