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

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

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

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

एल्गोरिदम

एल्गोरिदम में, लंबाई n ≥ 0 की सरणी x के लिए युग्‍मानूसार योग एल्गोरिथ्म लिखा जा सकता है:

s = pairwise(x[1…n])
   if n ≤ N   base case: naive summation for a sufficiently small array
     s = 0
     for i = 1 to n
       s = s + x[i]
   else     divide and conquer: recursively sum two halves of the array
     m = floor(n / 2)
     s = pairwise(x[1…m]) + pairwise(x[m+1…n])
   end if

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

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

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

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

त्रुटिहीनता

मान लीजिए कि i = 1, ..., n के लिए n मान x_i का योग है। त्रुटिहीन योग है:

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

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