मुझे थोड़ा असामान्य समस्या है, लेकिन मैं फिर से कोडिंग एफएफटी से बचने की कोशिश कर रहा हूं।जेनेरिक प्रोग्रामिंग: लॉग एफएफटी या उच्च परिशुद्धता संकल्प (पायथन)
सामान्य तौर पर, मैं इस जानना चाहता हूँ: जहाँ भी आपरेशन के एक विशिष्ट समूह (जैसे जटिल संख्या है, जिसके लिए भी परिभाषित परिभाषित किया गया है कि यह काम करेगा अगर मैं एक एल्गोरिथ्म है कि प्रकार float के लिए लागू किया गया है है, लेकिन +, *, ...), उस ऑपरेशन का समर्थन करने वाले किसी अन्य प्रकार पर उस एल्गोरिदम का उपयोग करने का सबसे अच्छा तरीका क्या है? अभ्यास में यह मुश्किल है क्योंकि आमतौर पर संख्यात्मक एल्गोरिदम गति के लिए लिखे जाते हैं, सामान्यता नहीं।
विशेष रूप :
मैं एक बहुत ही उच्च गतिशील रेंज के साथ मूल्यों के साथ काम कर रहा हूँ, और इसलिए मैं उन्हें लॉग अंतरिक्ष में स्टोर करने के लिए चाहते हैं (ज्यादातर अधःप्रवाह से बचने के लिए)।
x = [1,2,3,4,5]
fft_x = [ log(x_val) for x_val in fft(x) ]
यहां तक कि इस महत्वपूर्ण अधःप्रवाह में परिणाम होगा:
क्या मैं चाहता हूँ कुछ श्रृंखला के FFT के लॉग है। क्या मैं करना चाहते हैं, लॉग मान संग्रहीत और + के स्थान पर * और logaddexp के स्थान पर + उपयोग करने के लिए आदि
ऐसा करने के तरीके के बारे में सोचा मेरे एक सरल LogFloat वर्ग है कि इन आदिम संचालन को परिभाषित करता है लागू करने के लिए किया गया था (है लेकिन लॉग स्पेस में काम करता है)। तो मैं इसे अपने लॉग मूल्यों का उपयोग करके एफएफटी कोड चला सकता था।
x_log_float = [ LogFloat.from_float(x_val) for x_val in x ]
fft_x_log_float = fft(x_log_float)
यह निश्चित रूप से अगर मैं फिर से लागू FFT किया जा सकता है (और केवल:
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
फिर, विचार LogFloat रों की सूची का निर्माण, और फिर FFT में इसका इस्तेमाल किया जाएगा LogFloat का उपयोग करें जहां भी मैं float का उपयोग करता हूं, लेकिन मैंने सोचा कि मैं सलाह मांगूंगा। यह एक काफी आवर्ती समस्या है: मेरे पास एक स्टॉक एल्गोरिदम है जिसे मैं लॉग स्पेस में संचालित करना चाहता हूं (और यह केवल कुछ हद तक संचालन का उपयोग करता है जैसे + ',' - ',' ','/', आदि)
यह मुझे टेम्पलेट्स के साथ जेनेरिक फ़ंक्शंस लिखने की याद दिलाता है, ताकि वापसी तर्क, पैरामीटर इत्यादि उसी प्रकार से बने हों। Exmaple के लिए, यदि आप फ्लोट्स का एफएफटी कर सकते हैं, तो आप जटिल मूल्यों पर आसानी से एक करने में सक्षम होना चाहिए (केवल उस वर्ग का उपयोग करके जो जटिल मूल्यों के लिए आवश्यक संचालन प्रदान करता है)।
जैसा कि वर्तमान में यह खड़ा है, ऐसा लगता है कि सभी एफएफटी कार्यान्वयन रक्तस्राव-किनारे की गति के लिए लिखे गए हैं, और इसलिए यह बहुत सामान्य नहीं होगा। तो अब के रूप में, यह है कि मैं सामान्य प्रकार के लिए FFT reimplement करने के लिए ...
कारण मैं इस है कर रहा हूँ होगा, क्योंकि मैं बहुत उच्च परिशुद्धता convolutions (और एन^2 क्रम दिखाई देने लगे बेहद धीमी है)। किसी भी सलाह की सराहना की जाएगी।
* नोट, मुझे LogFloat के लिए त्रिकोणमितीय कार्यों को लागू करने की आवश्यकता हो सकती है, और यह ठीक होगा।
संपादित करें: क्योंकि LogFloat विनिमेय रिंग (और यह LogFloat के लिए त्रिकोणमितीय कार्यों के कार्यान्वयन की आवश्यकता नहीं है) है यह काम करता है।ऐसा करने का सबसे आसान तरीका एफएफटी को पुन: कार्यान्वित करना था, लेकिन @ जेएफ। एसबेस्टियन ने Python जेनेरिक कन्वोल्यूशन का उपयोग करने का एक तरीका भी बताया, जो एफएफटी को कोडिंग से बचाता है (जो फिर से, डीएसपी पाठ्यपुस्तक या the Wikipedia pseudocode का उपयोग करके काफी आसान था)।
मुझे यकीन नहीं है कि आपकी समस्या क्या है। अगर एफएफटी पायथन में लिखा गया है, तो उपरोक्त (महत्वाकांक्षी पागलपन modulo) काम करना चाहिए। यदि यह सी कार्यान्वयन के लिए कहता है तो यह काम नहीं करेगा, क्योंकि सी कोड है, ठीक है, सी कोड जो कि पाइथन करने वाला नहीं है। तो सवाल क्या है? –
[जेनेरिक कन्वोल्यूशन] है (http://www.math.ucla.edu/~jimc/mathnet_d/sage/reference/sage/rings/polynomial/convolution.html)। 'लॉगफ्लैट' अंडरफ्लो से निपटने का सबसे अच्छा तरीका नहीं हो सकता है। – jfs
डीएसपी पाठ्यपुस्तकों और ट्यूटोरियल वेबसाइटों में बहुत से एफएफटी बहुत सरल एफएफटी स्रोत कोड उदाहरण प्रदान करते हैं, आमतौर पर कोड के लगभग 1 या 2 पृष्ठ। (मेरी डीएसपी वेबसाइट पर कुछ एफएफटी हैं जो बेसिक की केवल 30 से 40 लाइनें हैं।) – hotpaw2