सी ++ exp lut (लुकअप तालिका)

Question

एक सी ++ सीपीयू बाध्य सिमुलेशन कि मैं लिख रहा हूँ में, मैं cmath::exp करने के लिए अपने कार्यक्रम में valgrind के माध्यम से एक टोंटी का पता लगाया गया है। यह वर्तमान में मेरे सिमुलेशन समय का 40% से अधिक खाता है। मैं इनपुट को अपेक्षाकृत छोटे डोमेन पर बाध्य कर सकता हूं, लेकिन मैं सटीकता को नियंत्रित करना चाहता हूं। मैं exp को प्रतिस्थापित करने के लिए एक LUT (लुकअप टेबल) पर जाने पर विचार कर रहा था, लेकिन मुझे पूरा यकीन नहीं है कि यह "सही तरीका" (टीएम) कैसे करें। चिंताएं मेरे पास है:

1. बड़े देखने टेबल कैश में फिट नहीं हो इस प्रकार के लिए उपयोग जवाब धीमा
2. सबसे अच्छा तरीका लुकअप तालिका
3. में उपयोग करने के लिए एक पूर्णांक के लिए एक डबल इनपुट कन्वर्ट करने के लिए करता है (2) इनपुट फ़ंक्शन की ढलान पर निर्भर करता है?
4. क्या मैं पहिया को फिर से शुरू कर रहा हूं - क्या यह पहले से ही किया जा चुका है?

exp के लिए एक LUT को लागू करने (/ लाइब्रेरी से शामिल) करने का सबसे अच्छा तरीका क्या है?

Answer 1

इससे पहले एक बहुत ही समान प्रश्न पूछा गया है। यहाँ मेरा उत्तर है:

• Fast Exp calculation: possible to improve accuracy without losing too much performance?

दृष्टिकोण है कि प्रश्न के लेखक द्वारा सुझाव दिया गया था, और मैं इसे कुशलता से लागू करने में सक्षम था (छोटे लुकअप तालिका और देखने के बाद कम से कम अतिरिक्त काम)। यह सी # में है, लेकिन सी ++ में अनुवाद सरल होना चाहिए और अगर आप परेशानी में भाग लेते हैं तो मैं मदद कर सकता हूं।

Answer 2

1. इष्टतम लुकअप टेबल आकार प्रदर्शन, सटीकता और कार्यान्वयन जटिलता के बीच किए गए व्यापार-बंद द्वारा निर्धारित किया जाता है। आपको प्रोफाइल करना होगा, हम आपको जवाब नहीं बता सकते हैं (हम जवाब नहीं जानते हैं)। <math.h> से

2. उपयोग lrintlong int को double कन्वर्ट करने के लिए। मुझे यकीन नहीं है कि यह <cmath> में है या नहीं।

3. मुझे यकीन है कि क्या ढलान पूर्णांकों के लिए चल बिन्दु संख्या परिवर्तित करने के साथ क्या करना है नहीं कर रहा हूँ। क्या आप इस बारे में चिंतित हो सकते हैं कि आप किस बारे में चिंतित हैं?

4. हाँ, आप पहिया पुनर्रचना कर रहे हैं। आप जो भी कर रहे हैं वह बार-बार किया गया है, किसी भी व्यक्ति ने कभी गणित पुस्तकालय को लागू किया है। इस विषय पर बहुत सारे साहित्य हैं।

एक सीधी लुक-अप तालिका इष्टतम से बहुत दूर है। आप किसी प्रकार के बहुपद अनुमान का उपयोग करना चाहेंगे, संभवतः एक लुक-अप तालिका से चुने गए गुणांक वाले टुकड़े वाले। एक समारोह के लिए exp के रूप में चिकनी और अनुमानित के रूप में, एक बहुपद आपको कम्प्यूटेशनल प्रयास की एक ही मात्रा के लिए बहुत अधिक सटीकता प्रदान करेगा। आवश्यक बहुपद जटिलता और सटीकता के बीच ट्रेडऑफ पर निर्भर करते हैं, साथ ही साथ आप अपेक्षित त्रुटि को कम करना चाहते हैं, अधिकतम त्रुटि को कम करना चाहते हैं, या कुछ अन्य हानि कार्य का उपयोग करना चाहते हैं।

सीमित करने exp के डोमेन वास्तव में मदद नहीं करता है कि ज्यादा है, क्योंकि यह संपूर्ण डोमेन पर विस्तार करने के लिए बहुत आसान है।

// only works for x in [0, 1] 
double exp2_limited(double x); 

// works for all x, but doesn't handle overflow properly 
double exp2(double x) 
{ 
    return scalbn(exp2_limited(fmod(x, 1.0)), (long) floor(x)); 
} 

सारांश:

• आप आवश्यक सटीकता पता करने के लिए इससे पहले कि आप इस तरह के एक समारोह डिजाइन कर सकते हैं।

• आपको हानि फ़ंक्शन (यानी, हानि फ़ंक्शन का चयन करना होगा) को भी जानना होगा।

• आप प्रोफ़ाइल में इससे पहले कि आप जानते हैं कि यह कितनी तेजी से है।

• बहुपदों का उपयोग करें।

Answer 3

मुझे यह समस्या है और मैंने इसका निदान करने के लिए कुछ स्टैक नमूने लिया। जो करता है वह बताता है कि कॉल कहां से आ रही हैं और तर्क मूल्य क्या है। मैंने पाया कि जब exp को विशेष स्थानों से बुलाया गया था, तो तर्क मान अत्यधिक दोहराया जा सकता था।

यह एक ज्ञापन दृष्टिकोण का सुझाव दिया, जिसने एक बड़ा अंतर बनाया।

double exp_cached(double arg, double* old_arg, double* old_result){ 
    if (arg== *old_arg) return *old_result; 
    *old_arg = arg; 
    *old_result = exp(arg); 
    return *old_result; 
} 

और जहां भी exp(foo) कहा जाता था, कार्य करें::

static double old_arg = -999999999, old_result; 
... 
... exp_cached(foo, &old_arg, &old_result)... 

इस तरह, exp अगर में अपने तर्क कहा जाता नहीं प्राप्त करता है

यह एक सरल "आवरण" समारोह की जरूरत वह स्थान जहां से इसे कहा जाता है, वही तर्क मान पहले जैसा होता है।