घाटे की गणना कैसे की जाती है?

Question

मैं अपने एल्गोरिदम में से एक के एसिम्प्टोटिक रन-टाइम को निर्धारित करने की कोशिश कर रहा हूं, जो एक्सपोनेंट का उपयोग करता है, लेकिन मुझे यकीन नहीं है कि एक्सपोनेंट की गणना प्रोग्रामेटिक रूप से की जाती है।

मैं विशेष रूप से पाउ() एल्गोरिदम की तलाश कर रहा हूं जो डबल-परिशुद्धता, फ़्लोटिंग पॉइंट नंबरों के लिए उपयोग किया जाता है।

Answer 1

मुझे fdlibm के कार्यान्वयन को देखने का मौका मिला है। टिप्पणियाँ एल्गोरिथ्म इस्तेमाल किया वर्णन:

*     n 
* Method: Let x = 2 * (1+f) 
*  1. Compute and return log2(x) in two pieces: 
*    log2(x) = w1 + w2, 
*   where w1 has 53-24 = 29 bit trailing zeros. 
*  2. Perform y*log2(x) = n+y' by simulating muti-precision 
*   arithmetic, where |y'|<=0.5. 
*  3. Return x**y = 2**n*exp(y'*log2) 

संभाला सभी विशेष मामलों की एक सूची के बाद (0, 1, inf, नेन)।

कोड के सबसे गहन वर्ग, सभी विशेष मामले हैंडलिंग के बाद, log2 और 2** गणना शामिल हैं। और उनमें से किसी में कोई लूप नहीं है। तो, फ्लोटिंग-पॉइंट प्राइमेटिव्स की जटिलता के बावजूद, यह एक असम्बद्ध रूप से स्थिर-समय एल्गोरिदम की तरह दिखता है।

फ्लोटिंग-पॉइंट विशेषज्ञ (जिनमें से मैं नहीं हूं) टिप्पणी करने के लिए स्वागत है। :-)

Answer 2

सामान्य दृष्टिकोण, ख के लिए एक बढ़ाने के लिए, एक पूर्णांक घात के लिए, कुछ इस तरह चला जाता है:

result = 1 
while b > 0 
    if b is odd 
    result *= a 
    b -= 1 
    b /= 2 
    a = a * a 

यह आम तौर पर प्रतिपादक के आकार में लघुगणक है। एल्गोरिदम invariant "a^b * result = a0^b0" पर आधारित है, जहां a0 और b0 ए और बी के प्रारंभिक मान हैं।

नकारात्मक या गैर-पूर्णांक एक्सपोनेंट्स के लिए, लॉगरिदम और अनुमान और संख्यात्मक विश्लेषण की आवश्यकता है। चलने का समय इस्तेमाल किए गए एल्गोरिदम पर निर्भर करेगा और लाइब्रेरी के लिए किस परिशुद्धता को ट्यून किया गया है।

संपादित करें: चूंकि कुछ रूचि दिखाई देती है, यहां अतिरिक्त गुणा के बिना एक संस्करण है।

result = 1 
while b > 0 
    while b is even 
    a = a * a 
    b = b/2 
    result = result * a 
    b = b - 1 

Answer 3

यदि मैं इंटेल को लक्षित करने वाला एक पाउ फ़ंक्शन लिख रहा था, तो मैं exp2 (log2 (x) * y) वापस कर दूंगा। लॉग 2 के लिए इंटेल का माइक्रोक्रोड निश्चित रूप से कुछ भी तेज है जो मैं कोड करने में सक्षम हूं, भले ही मैं अपना पहला साल कैलकुस और ग्रेड स्कूल संख्यात्मक विश्लेषण याद कर सकूं।

Answer 4

जब तक कि वे यह करने के लिए एक बेहतर तरीका ढूंढ निकाला है, मेरा मानना ​​है कि (घातीय वृद्धि और क्षय, उदाहरण के लिए के लिए) ट्रिग, लघुगणक और घातीय कार्यों के लिए अनुमानित मान आम तौर पर गणित के नियमों और टेलर श्रृंखला विस्तार से की जाती है कि अनुरोधित परिशुद्धता के भीतर सटीक परिणाम सटीक बनाने के लिए। (पावर श्रृंखला, टेलर श्रृंखला, और मैकॉलोरिन श्रृंखला कार्यों के विवरणों के विवरण के लिए कोई भी कैलकुंस बुक देखें।) कृपया ध्यान दें कि ऐसा कुछ समय हो गया है क्योंकि मैंने इनमें से कोई भी किया है, इसलिए मैं आपको नहीं बता सका, उदाहरण के लिए, वास्तव में गणना कैसे करें श्रृंखला में शर्तों की संख्या को शामिल करने के लिए आपको एक त्रुटि की गारंटी है जो डबल-परिशुद्धता गणना में नगण्य होने के लिए पर्याप्त छोटा है।

उदाहरण के लिए, ई^x के लिए टेलर/मैकलौरिन श्रृंखला विस्तार यह है:

 +inf [ x^k ]   x^2 x^3  x^4  x^5 
e^x = SUM [ --- ] = 1 + x + --- + ----- + ------- + --------- + .... 
     k=0 [ k! ]   2*1 3*2*1 4*3*2*1 5*4*3*2*1 

आप सभी शर्तों के (अनंत को 0 से ट) लेते हैं, इस विस्तार सटीक और पूरा हो गया है (कोई त्रुटि)।

हालांकि, अगर आप अनंत शर्तों पर जाने वाली सभी शर्तों को नहीं लेते हैं, लेकिन आप 5 शब्द या 50 शब्द या जो कुछ भी कहने के बाद रुकते हैं, तो आप अनुमानित परिणाम वास्तविक ई^एक्स फ़ंक्शन मान से अलग होते हैं एक शेष जो गणना करने के लिए काफी आसान है।

exponentials के लिए अच्छी खबर यह है कि यह अच्छी तरह से अभिसरण और उसके बहुपद विस्तार की दृष्टि से काफी iteratively कोड करने के लिए आसान कर रहे हैं, ताकि आप पराक्रम है (दोहराने, सकता - याद रखें, यह एक समय हो गया है) भी जरूरत नहीं पूर्व-गणना करने के लिए कि आपको अपनी त्रुटि की गारंटी देने के लिए कितने नियमों की आवश्यकता है, परिशुद्धता से कम है क्योंकि आप प्रत्येक पुनरावृत्ति पर योगदान के आकार का परीक्षण कर सकते हैं और शून्य होने के करीब होने पर रोक सकते हैं। प्रैक्टिस में, मुझे नहीं पता कि यह रणनीति व्यवहार्य है या नहीं - मुझे इसे आजमा देना होगा। मेरे बारे में भूल जाने के बाद से लंबे समय तक महत्वपूर्ण विवरण हैं। सामग्री जैसे: मशीन परिशुद्धता, मशीन त्रुटि और गोल त्रुटि, आदि

इसके अलावा, कृपया ध्यान दें कि यदि आप ई^एक्स का उपयोग नहीं कर रहे हैं, लेकिन आप 2^x या 10^x जैसे किसी अन्य आधार के साथ विकास/क्षय कर रहे हैं , अनुमानित बहुपद कार्य बदलता है।

Answer 5

आप एक्स ^एन की गणना के लिए एक्स (एन * एलएन (एक्स)) का उपयोग कर सकते हैं। एक्स और एन दोनों डबल-परिशुद्धता, फ़्लोटिंग पॉइंट नंबर हो सकते हैं। प्राकृतिक लॉगरिदम और घातीय कार्य की गणना टेलर श्रृंखला का उपयोग करके की जा सकती है। यहां आप सूत्र ढूंढ सकते हैं: http://en.wikipedia.org/wiki/Taylor_series