युग्‍मानूसार योग

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

विशेष रूप से, n संख्याओं x के अनुक्रम का जोड़ीवार योग_nरिकर्सन (कंप्यूटर विज्ञान) द्वारा अनुक्रम को दो हिस्सों में तोड़ना, प्रत्येक आधे का योग करना और दो योगों को जोड़ना: एक विभाजन और जीत एल्गोरिथ्म का काम करता है। इसकी सबसे खराब स्थिति में राउंडऑफ़ त्रुटियां बिग ओ अंकन को अधिकतम ओ (ε लॉग एन) के रूप में बढ़ाती हैं, जहां ε मशीन परिशुद्धता है (एक निश्चित स्थिति संख्या मानते हुए, जैसा कि नीचे चर्चा की गई है)। इसकी तुलना में, योग को क्रम में जमा करने की सरल तकनीक (प्रत्येक x को जोड़कर)।_ii = 1, ..., n) के लिए एक समय में एक में राउंडऑफ़ त्रुटियां होती हैं जो O(εn) के रूप में सबसे खराब रूप से बढ़ती हैं। कहन सारांश में एक त्रुटि बाध्य है | सबसे खराब स्थिति में मोटे तौर पर O(ε) की त्रुटि है, जो n से स्वतंत्र है, लेकिन इसके लिए कई गुना अधिक अंकगणितीय परिचालन की आवश्यकता होती है। यदि राउंडऑफ़ त्रुटियाँ यादृच्छिक हैं, और विशेष रूप से यादृच्छिक संकेत हैं, तो वे एक यादृच्छिक चाल बनाते हैं और त्रुटि वृद्धि औसतन कम हो जाती है $O(\varepsilon {\sqrt {\log n}})$ जोड़ीवार योग के लिए. योग की एक बहुत ही समान पुनरावर्ती संरचना कई तेज़ फास्ट फूरियर ट्रांसफॉर्मएफएफटी) एल्गोरिदम में पाई जाती है, और उन एफएफटी के समान धीमी राउंडऑफ़ संचय के लिए ज़िम्मेदार है।

एल्गोरिदम

छद्मकोड में, एक ऐरे डेटा प्रकार के लिए जोड़ीवार योग एल्गोरिथ्म x लंबाई का n ≥ 0 लिखा जा सकता है:

s = 'जोड़ी में'(x[1…n])
      'अगर' एन ≤ एन बेस केस: पर्याप्त रूप से छोटे सरणी के लिए अनुभवहीन योग
          एस = 0
          'के लिए' i = 1 से n
              s = s + x[i]
      'अन्यथा' विभाजित करें और जीतें: सरणी के दो हिस्सों को पुनरावर्ती रूप से जोड़ें
          एम = फर्श और छत के कार्य(एन/2)
          s = 'जोड़ीवार'(x[1...m]) + 'जोड़ीवार'(x[m+1...n])
      'अगर अंत'

कुछ के लिए पर्याप्त रूप से छोटा N, यह एल्गोरिदम रिकर्सन#बेस केस के रूप में एक अनुभवहीन लूप-आधारित योग पर स्विच करता है, जिसकी त्रुटि सीमा O(Nε) है। पूरे योग में सबसे खराब स्थिति वाली त्रुटि है जो किसी दिए गए शर्त संख्या के लिए बड़े एन के लिए ओ (ε लॉग एन) के रूप में स्पर्शोन्मुख रूप से बढ़ती है (नीचे देखें)।

इस प्रकार के एल्गोरिदम में (बांटो और जीतो एल्गोरिदम के लिए# सामान्य रूप से आधार मामलों को चुनना), रिकर्सन के ओवरहेड का परिशोधन विश्लेषण करने के लिए एक बड़े बेस केस का उपयोग करना वांछनीय है। यदि N = 1, तो प्रत्येक इनपुट के लिए लगभग एक पुनरावर्ती सबरूटीन कॉल होती है, लेकिन अधिक सामान्यतः प्रत्येक N/2 इनपुट के लिए (लगभग) एक पुनरावर्ती कॉल होती है यदि पुनरावृत्ति बिल्कुल n = N पर रुकती है। N को पर्याप्त रूप से बड़ा बनाकर, रिकर्सन के ओवरहेड को नगण्य बनाया जा सकता है (रिकर्सिव योग के लिए बड़े बेस केस की यह तकनीक उच्च-प्रदर्शन एफएफटी कार्यान्वयन द्वारा नियोजित होती है).

एन के बावजूद, बिल्कुल एन-1 जोड़ कुल मिलाकर किए जाते हैं, जो कि अनुभवहीन योग के समान है, इसलिए यदि रिकर्सन ओवरहेड को नगण्य बना दिया जाता है तो जोड़ीदार योग में अनिवार्य रूप से वही कम्प्यूटेशनल लागत होती है जो अनुभवहीन योग के लिए होती है।

इस विचार पर एक भिन्नता प्रत्येक पुनरावर्ती चरण में योग को बी ब्लॉक में तोड़ना है, प्रत्येक ब्लॉक को पुनरावर्ती रूप से जोड़ना है, और फिर परिणामों को जोड़ना है, जिसे इसके प्रस्तावकों द्वारा सुपरब्लॉक एल्गोरिदम करार दिया गया था। उपरोक्त जोड़ीवार एल्गोरिथ्म अंतिम चरण को छोड़कर प्रत्येक चरण के लिए b = 2 से मेल खाता है जो कि b = N है।

सटीकता

मान लीजिए कि कोई n मान x का योग है_i, i = 1, ...,n के लिए। सटीक योग है:

$S_{n}=\sum _{i=1}^{n}x_{i}$

(अनंत परिशुद्धता के साथ गणना की गई)।

आधार मामले N = 1 के लिए जोड़ीवार योग के साथ, इसके बजाय एक प्राप्त होता है $S_{n}+E_{n}$, त्रुटि कहां है $E_{n}$ ऊपर से घिरा है:

$|E_{n}|\leq {\frac {\varepsilon \log _{2}n}{1-\varepsilon \log _{2}n}}\sum _{i=1}^{n}|x_{i}|$

जहां ε नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (जैसे ε ≈ 10)⁻¹⁶मानक दोहरी सुनिश्चितता फ़्लोटिंग पॉइंट के लिए)। आमतौर पर, ब्याज की मात्रा सापेक्ष त्रुटि होती है $|E_{n}|/|S_{n}|$, जो इसलिए ऊपर से घिरा है:

${\frac {|E_{n}|}{|S_{n}|}}\leq {\frac {\varepsilon \log _{2}n}{1-\varepsilon \log _{2}n}}\left({\frac {\sum _{i=1}^{n}|x_{i}|}{\left|\sum _{i=1}^{n}x_{i}\right|}}\right).$

सापेक्ष त्रुटि सीमा के लिए अभिव्यक्ति में, अंश (Σ|x_i|||Σx_i|) योग समस्या की शर्त संख्या है। अनिवार्य रूप से, शर्त संख्या त्रुटियों के लिए योग समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, भले ही इसकी गणना कैसे की जाती है। निश्चित परिशुद्धता में एक निश्चित एल्गोरिदम द्वारा प्रत्येक (पीछे की ओर स्थिर) योग विधि की सापेक्ष त्रुटि (यानी वे नहीं जो मनमानी-सटीक अंकगणित का उपयोग करते हैं, न ही एल्गोरिदम जिनकी स्मृति और समय की आवश्यकताएं डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के लिए आनुपातिक है . एक खराब स्थिति वाली योग समस्या वह होती है जिसमें यह अनुपात बड़ा होता है, और इस मामले में जोड़ीवार योग में भी बड़ी सापेक्ष त्रुटि हो सकती है। उदाहरण के लिए, यदि सारांश x_iशून्य माध्य के साथ असंबंधित यादृच्छिक संख्याएं हैं, योग एक यादृच्छिक चलना है और स्थिति संख्या आनुपातिक रूप से बढ़ेगी ${\sqrt {n}}$. दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को एक परिमित स्थिरांक के रूप में दर्शाती है $n\to \infty$. यदि सभी इनपुट गैर-नकारात्मक हैं, तो शर्त संख्या 1 है।

ध्यान दें कि $1-\varepsilon \log _{2}n$ चूँकि व्यवहार में हर प्रभावी रूप से 1 है $\varepsilon \log _{2}n$ जब तक n क्रम 2 का न हो जाए तब तक 1 से बहुत छोटा होता है^1/ε, जो लगभग 10 है¹⁰¹⁵दोगुनी परिशुद्धता में।

इसकी तुलना में, सरल योग के लिए बाध्य सापेक्ष त्रुटि (केवल अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण पर पूर्णांक बनाना) इस प्रकार बढ़ती है $O(\varepsilon n)$ शर्त संख्या से गुणा किया गया। व्यवहार में, इसकी बहुत अधिक संभावना है कि पूर्णांकन त्रुटियों में शून्य माध्य के साथ एक यादृच्छिक चिह्न होता है, जिससे वे एक यादृच्छिक चाल बनाते हैं; इस मामले में, सरल योग में मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो बढ़ती है $O(\varepsilon {\sqrt {n}})$ और जोड़ीवार योग में एक त्रुटि है जो बढ़ती है $O(\varepsilon {\sqrt {\log n}})$ औसत पर।

सॉफ़्टवेयर कार्यान्वयन

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

अन्य सॉफ़्टवेयर कार्यान्वयन में HPCsharp लाइब्रेरी शामिल है सी शार्प (प्रोग्रामिंग भाषा) भाषा और मानक पुस्तकालय सारांश के लिए डी (प्रोग्रामिंग भाषा) में।