युग्‍मानूसार योग: Difference between revisions

Latest revision as of 10:05, 1 December 2023

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

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

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

एल्गोरिदम

एल्गोरिदम में, लंबाई 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ε) है।^[4] पूरे योग में सबसे गुणहीन स्थिति वाली त्रुटि है जो किसी दिए गए शर्त संख्या के लिए बड़े n के लिए O(ε log n) के रूप में स्पर्शोन्मुख रूप से बढ़ती है (नीचे देखें)।

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

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

इस विचार पर एक भिन्नता प्रत्येक पुनरावर्ती चरण में योग को बी ब्लॉक में तोड़ना है, प्रत्येक ब्लॉक को पुनरावर्ती रूप से जोड़ना है, और फिर परिणामों को जोड़ना है, जिसे इसके प्रस्तावकों द्वारा सुपरब्लॉक एल्गोरिदम करार दिया गया था।^[6] इस प्रकार उपरोक्त युग्‍मानूसार एल्गोरिथ्म अंतिम चरण को छोड़कर प्रत्येक चरण के लिए 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}$ ऊपर से घिरा है:^[1]

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

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

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

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

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

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing, 14 (4): 783–799, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050
↑ ^2.0 ^2.1 ^2.2 Manfred Tasche and Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000).
↑ ^3.0 ^3.1 S. G. Johnson and M. Frigo, "Implementing FFTs in practice, in Fast Fourier Transforms, edited by C. Sidney Burrus (2008).
↑ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 81–82.
↑ Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs," in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).
↑ Anthony M. Castaldo, R. Clint Whaley, and Anthony T. Chronopoulos, "Reducing floating-point error in dot product using the superblock family of algorithms," SIAM J. Sci. Comput., vol. 32, pp. 1156–1174 (2008).
↑ L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM: Philadelphia, 1997).
↑ ENH: implement pairwise summation, github.com/numpy/numpy pull request #3685 (September 2013).
↑ "std.algorithm.iteration - डी प्रोग्रामिंग भाषा". dlang.org. Retrieved 2021-04-23.
↑ https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance C# algorithms

[Higham93-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing, 14 (4): 783–799, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050

[Tasche-2] 2.0 ^2.1 ^2.2 Manfred Tasche and Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000).

[JohnsonFrigo08-3] 3.0 ^3.1 S. G. Johnson and M. Frigo, "Implementing FFTs in practice, in Fast Fourier Transforms, edited by C. Sidney Burrus (2008).

[4] Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 81–82.

[5] Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs," in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[Castaldo08-6] Anthony M. Castaldo, R. Clint Whaley, and Anthony T. Chronopoulos, "Reducing floating-point error in dot product using the superblock family of algorithms," SIAM J. Sci. Comput., vol. 32, pp. 1156–1174 (2008).

[7] L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM: Philadelphia, 1997).

[8] ENH: implement pairwise summation, github.com/numpy/numpy pull request #3685 (September 2013).

[9] "std.algorithm.iteration - डी प्रोग्रामिंग भाषा". dlang.org. Retrieved 2021-04-23.

[10] ttps://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance C# algorithms

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
-[[संख्यात्मक विश्लेषण]] में, जोड़ीवार योग, जिसे कैस्केड योग भी कहा जाता है, परिमित-अंकगणितीय त्रुटिहीन [[तैरनेवाला स्थल]] संख्याओं के अनुक्रम को जोड़ने की एक विधि  है जो अनुक्रम में योग को एकत्रित करने की तुलना में संचित राउंड-ऑफ त्रुटि को अधिक  कम कर देता है।<ref name=Higham93>{{Citation | title=The accuracy of floating point summation |
+[[संख्यात्मक विश्लेषण]] में, '''युग्‍मानूसार योग''', जिसे '''कैस्केड योग''' भी कहा जाता है, परिमित-सटीक फ़्लोटिंग-पॉइंट संख्याओं के अनुक्रम को जोड़ने की एक विधि है जो अनुक्रम में योग को एकत्रित करने की तुलना में संचित राउंड-ऑफ त्रुटि को अधिक कम कर देता है।<ref name=Higham93>{{Citation | title=The accuracy of floating point summation |
 first1=Nicholas J. | last1=Higham | journal=[[SIAM Journal on Scientific Computing]] |
 volume=14 | issue=4 | pages=783–799 | doi=10.1137/0914050 | year=1993
-| citeseerx=10.1.1.43.3535 }}</ref> यद्यपि काहन योग जैसी अन्य विधि ें भी हैं जिनमें सामान्यतः और भी छोटी राउंड-ऑफ त्रुटियाँ होती हैं, जोड़ीवार योग लगभग उतना ही अच्छा होता है (केवल एक लघुगणकीय कारक द्वारा भिन्न) जबकि इसकी कम्प्यूटेशनल निवेश बहुत कम होती है - इसे इस तरह कार्यान्वित किया जा सकता है कि लगभग अनुभवहीन योग के रूप में समान निवेश (और अंकगणितीय संक्रियाओं की बिल्कुल समान संख्या)।
+| citeseerx=10.1.1.43.3535 }}</ref> इस प्रकार यद्यपि काहन योग जैसी अन्य विधिया भी हैं जिनमें सामान्यतः और भी छोटी राउंड-ऑफ त्रुटियाँ होती हैं, युग्‍मानूसार योग लगभग उतना ही अच्छा होता है (केवल एक लघुगणकीय कारक द्वारा भिन्न) जबकि इसकी कम्प्यूटेशनल निवेश बहुत कम होती है - इसे इस तरह कार्यान्वित किया जा सकता है जिससे लगभग अनुभवहीन योग के रूप में समान निवेश (और अंकगणितीय संक्रियाओं की बिल्कुल समान संख्या) होगा।
-विशेष रूप से, n संख्याओं x के अनुक्रम का जोड़ीवार योग<sub>n</sub>[[रिकर्सन (कंप्यूटर विज्ञान)]] द्वारा अनुक्रम को दो हिस्सों में तोड़ना, प्रत्येक आधे का योग करना और दो योगों को जोड़ना: एक विभाजन और जीत एल्गोरिथ्म का काम करता है। इसकी सबसे खराब स्थिति में राउंडऑफ़ त्रुटियां [[ बिग ओ अंकन ]] को अधिकतम ओ (ε लॉग एन) के रूप में बढ़ाती हैं, जहां ε [[मशीन परिशुद्धता]] है (एक निश्चित स्थिति संख्या मानते हुए, जैसा कि नीचे चर्चा की गई है)।<ref name=Higham93/>  इसकी तुलना में, योग को क्रम में जमा करने की सरल विधि  (प्रत्येक x को जोड़कर)।<sub>i</sub>i = 1, ..., n) के लिए एक समय में एक में राउंडऑफ़ त्रुटियां होती हैं जो O(εn) के रूप में सबसे खराब रूप से बढ़ती हैं।<ref name=Higham93/>  कहन सारांश में एक [[त्रुटि बाध्य]] है | सबसे खराब स्थिति में मोटे तौर पर O(ε) की त्रुटि है, जो n से स्वतंत्र है, किन्तु इसके लिए अनेक गुना अधिक अंकगणितीय परिचालन की आवश्यकता होती है।<ref name=Higham93/>  यदि राउंडऑफ़ त्रुटियाँ यादृच्छिक हैं, और विशेष रूप से यादृच्छिक संकेत हैं, तब वह एक [[यादृच्छिक चाल]] बनाते हैं और त्रुटि वृद्धि औसतन कम हो जाती है <math>O(\varepsilon \sqrt{\log n})</math> जोड़ीवार योग के लिए.<ref name=Tasche>Manfred Tasche and Hansmartin Zeuner ''Handbook of Analytic-Computational Methods in Applied Mathematics'' Boca Raton, FL: CRC Press, 2000).</ref>
-योग की एक बहुत ही समान पुनरावर्ती संरचना अनेक तेज़ [[फास्ट फूरियर ट्रांसफॉर्म]]एफएफटी) एल्गोरिदम में पाई जाती है, और उन एफएफटी के समान धीमी राउंडऑफ़ संचय के लिए ज़िम्मेदार है।<ref name="Tasche"/><ref name=JohnsonFrigo08>S. G. Johnson and M. Frigo, "[http://cnx.org/content/m16336/latest/ Implementing FFTs in practice], in ''[http://cnx.org/content/col10550/ Fast Fourier Transforms]'', edited by [[C. Sidney Burrus]] (2008).</ref>
+विशेष रूप से, n संख्याओं ''x<sub>n</sub>'' के अनुक्रम का युग्‍मानूसार योग [[रिकर्सन (कंप्यूटर विज्ञान)]] द्वारा अनुक्रम को दो हिस्सों में तोड़ना, प्रत्येक आधे का योग करना और दो योगों को जोड़ना: एक विभाजन और जीत एल्गोरिथ्म का काम करता है। इसकी सबसे गुणहीन स्थिति में राउंडऑफ़ त्रुटियां अधिकतम ''O''(ε log ''n''), के रूप में असम्बद्ध रूप से बढ़ाती हैं, जहां ε [[मशीन परिशुद्धता]] है (एक निश्चित स्थिति संख्या मानते हुए, जैसा कि नीचे चर्चा की गई है)।<ref name=Higham93/> इस प्रकार इसकी तुलना में, अनुक्रम में योग जमा करने की सरल विधि (''i'' = 1, ..., ''n के लिए एक समय में प्रत्येक xi को जोड़ने'') में राउंडऑफ़ त्रुटियां होती हैं जो O(εn) के रूप में सबसे गुणहीन रूप से बढ़ती हैं।<ref name=Higham93/> कहन सारांश में सबसे गुणहीन स्थिति वाली त्रुटि मोटे तौर पर O(ε) है, जो n से स्वतंत्र है, किन्तु इसके लिए अनेक गुना अधिक अंकगणितीय परिचालन की आवश्यकता होती है।<ref name=Higham93/> इस प्रकार यदि राउंडऑफ़ त्रुटियाँ यादृच्छिक हैं, और विशेष रूप से यादृच्छिक संकेत हैं, तब वह एक [[यादृच्छिक चाल]] बनाते हैं और त्रुटि वृद्धि औसतन कम हो जाती है <math>O(\varepsilon \sqrt{\log n})</math> युग्‍मानूसार योग के लिए है।<ref name=Tasche>Manfred Tasche and Hansmartin Zeuner ''Handbook of Analytic-Computational Methods in Applied Mathematics'' Boca Raton, FL: CRC Press, 2000).</ref>
+योग की एक बहुत ही समान पुनरावर्ती संरचना अनेक तेज़ [[फास्ट फूरियर ट्रांसफॉर्म]] (एफएफटी) एल्गोरिदम में पाई जाती है, और उन एफएफटी के समान धीमी राउंडऑफ़ संचय के लिए उत्तरदायी है।<ref name="Tasche" /><ref name="JohnsonFrigo08">S. G. Johnson and M. Frigo, "[http://cnx.org/content/m16336/latest/ Implementing FFTs in practice], in ''[http://cnx.org/content/col10550/ Fast Fourier Transforms]'', edited by [[C. Sidney Burrus]] (2008).</ref>
 ==एल्गोरिदम==
-[[ छद्मकोड ]] में, एक ऐरे डेटा प्रकार के लिए जोड़ीवार योग एल्गोरिथ्म {{var|x}} लंबाई का {{var|n}} ≥ 0 लिखा जा सकता है:
+[[ छद्मकोड | एल्गोरिदम]] में, लंबाई 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'''
+कुछ के लिए पर्याप्त रूप से छोटा {{var|N}} के लिए, यह एल्गोरिदम रिकर्सन बेस केस के रूप में एक अनुभवहीन लूप-आधारित योग पर स्विच करता है, इस प्रकार जिसकी त्रुटि सीमा O(Nε) है।<ref>{{cite book|first=Nicholas | last=Higham |title=Accuracy and Stability of Numerical Algorithms (2 ed)| publisher=SIAM|year=2002 | pages=81–82}}</ref> पूरे योग में सबसे गुणहीन स्थिति वाली त्रुटि है जो किसी दिए गए शर्त संख्या के लिए बड़े ''n'' के लिए ''O''(ε log ''n'') के रूप में स्पर्शोन्मुख रूप से बढ़ती है (नीचे देखें)।
- s = 'जोड़ी में'(x[1…n])
+इस प्रकार के एल्गोरिदम में (बांटो और जीतो एल्गोरिदम के लिए# सामान्य रूप से आधार स्थितियों को चुनना<ref>Radu Rugina and Martin Rinard, "[http://people.csail.mit.edu/rinard/paper/lcpc00.pdf Recursion unrolling for divide and conquer programs]," in ''Languages and Compilers for Parallel Computing'', chapter 3, pp. 34–48.  ''Lecture Notes in Computer Science'' vol. 2017 (Berlin: Springer, 2001).</ref>), रिकर्सन के ओवरहेड का [[परिशोधन विश्लेषण]] करने के लिए एक बड़े बेस केस का उपयोग करना वांछनीय है। इस प्रकार यदि N = 1, तब प्रत्येक इनपुट के लिए लगभग एक पुनरावर्ती सबरूटीन कॉल होती है, किन्तु अधिक सामान्यतः प्रत्येक N/2 इनपुट के लिए (लगभग) एक पुनरावर्ती कॉल होती है यदि पुनरावृत्ति बिल्कुल n = N पर रुकती है। N को पर्याप्त रूप से बड़ा बनाकर, रिकर्सन के ओवरहेड को नगण्य बनाया जा सकता है (रिकर्सिव योग के लिए बड़े बेस केस की यह विधि उच्च-प्रदर्शन एफएफटी कार्यान्वयन द्वारा नियोजित होती है<ref name=JohnsonFrigo08/>).
-       'अगर' एन ≤ एन बेस केस: पर्याप्त रूप से छोटे सरणी के लिए अनुभवहीन योग
-           एस = 0
-           'के लिए' i = 1 से n
-               s = s + x[i]
-       'अन्यथा' विभाजित करें और जीतें: सरणी के दो हिस्सों को पुनरावर्ती रूप से जोड़ें
-           एम = [[फर्श और छत के कार्य]](एन/2)
-           s = 'जोड़ीवार'(x[1...m]) + 'जोड़ीवार'(x[m+1...n])
-       'अगर अंत'
-कुछ के लिए पर्याप्त रूप से छोटा {{var|N}}, यह एल्गोरिदम रिकर्सन#बेस केस के रूप में एक अनुभवहीन लूप-आधारित योग पर स्विच करता है, जिसकी त्रुटि सीमा O(Nε) है।<ref>{{cite book|first=Nicholas | last=Higham |title=Accuracy and Stability of Numerical Algorithms (2 ed)| publisher=SIAM|year=2002 | pages=81–82}}</ref> पूरे योग में सबसे खराब स्थिति वाली त्रुटि है जो किसी दिए गए शर्त संख्या के लिए बड़े एन के लिए ओ (ε लॉग एन) के रूप में स्पर्शोन्मुख रूप से बढ़ती है (नीचे देखें)।
+एन के अतिरिक्त, बिल्कुल एन-1 जोड़ कुल मिलाकर किए जाते हैं, जो कि अनुभवहीन योग के समान है, इसलिए यदि रिकर्सन ओवरहेड को नगण्य बना दिया जाता है तब युग्‍मानूसार योग में अनिवार्य रूप से वही कम्प्यूटेशनल निवेश होती है जो अनुभवहीन योग के लिए होती है।
-इस प्रकार के एल्गोरिदम में (बांटो और जीतो एल्गोरिदम के लिए# सामान्य रूप से आधार स्थितियों को चुनना<ref>Radu Rugina and Martin Rinard, "[http://people.csail.mit.edu/rinard/paper/lcpc00.pdf Recursion unrolling for divide and conquer programs]," in ''Languages and Compilers for Parallel Computing'', chapter 3, pp. 34–48.  ''Lecture Notes in Computer Science'' vol. 2017 (Berlin: Springer, 2001).</ref>), रिकर्सन के ओवरहेड का [[परिशोधन विश्लेषण]] करने के लिए एक बड़े बेस केस का उपयोग करना वांछनीय है। यदि N = 1, तब प्रत्येक इनपुट के लिए लगभग एक पुनरावर्ती सबरूटीन कॉल होती है, किन्तु अधिक सामान्यतः प्रत्येक N/2 इनपुट के लिए (लगभग) एक पुनरावर्ती कॉल होती है यदि पुनरावृत्ति बिल्कुल n = N पर रुकती है। N को पर्याप्त रूप से बड़ा बनाकर, रिकर्सन के ओवरहेड को नगण्य बनाया जा सकता है (रिकर्सिव योग के लिए बड़े बेस केस की यह विधि  उच्च-प्रदर्शन एफएफटी कार्यान्वयन द्वारा नियोजित होती है<ref name=JohnsonFrigo08/>).
+इस विचार पर एक भिन्नता प्रत्येक पुनरावर्ती चरण में योग को बी ब्लॉक में तोड़ना है, प्रत्येक ब्लॉक को पुनरावर्ती रूप से जोड़ना है, और फिर परिणामों को जोड़ना है, जिसे इसके प्रस्तावकों द्वारा सुपरब्लॉक एल्गोरिदम करार दिया गया था।<ref name=Castaldo08>Anthony M. Castaldo, R. Clint Whaley, and Anthony T. Chronopoulos, "Reducing floating-point error in dot product using the superblock family of algorithms," ''SIAM J. Sci. Comput.'', vol. 32, pp. 1156–1174 (2008).</ref> इस प्रकार उपरोक्त युग्‍मानूसार एल्गोरिथ्म अंतिम चरण को छोड़कर प्रत्येक चरण के लिए b = 2 से मेल खाता है जो कि b = N है।
-एन के अतिरिक्त, बिल्कुल एन-1 जोड़ कुल मिलाकर किए जाते हैं, जो कि अनुभवहीन योग के समान है, इसलिए यदि रिकर्सन ओवरहेड को नगण्य बना दिया जाता है तब जोड़ीदार योग में अनिवार्य रूप से वही कम्प्यूटेशनल निवेश होती है जो अनुभवहीन योग के लिए होती है।
-इस विचार पर एक भिन्नता प्रत्येक पुनरावर्ती चरण में योग को बी ब्लॉक में तोड़ना है, प्रत्येक ब्लॉक को पुनरावर्ती रूप से जोड़ना है, और फिर परिणामों को जोड़ना है, जिसे इसके प्रस्तावकों द्वारा सुपरब्लॉक एल्गोरिदम करार दिया गया था।<ref name=Castaldo08>Anthony M. Castaldo, R. Clint Whaley, and Anthony T. Chronopoulos, "Reducing floating-point error in dot product using the superblock family of algorithms," ''SIAM J. Sci. Comput.'', vol. 32, pp. 1156–1174 (2008).</ref> उपरोक्त जोड़ीवार एल्गोरिथ्म अंतिम चरण को छोड़कर प्रत्येक चरण के लिए b = 2 से मेल खाता है जो कि b = N है।
 ==त्रुटिहीनता==
-मान लीजिए कि कोई n मान x का योग है<sub>''i''</sub>, i = 1, ...,n के लिए। त्रुटिहीन योग है:
+मान लीजिए कि i = 1, ..., n के लिए n मान ''x<sub>i</sub>'' का योग है। त्रुटिहीन योग है:
 :<math>S_n = \sum_{i=1}^n x_i</math>
 (अनंत परिशुद्धता के साथ गणना की गई)।
-आधार स्थितियों N = 1 के लिए जोड़ीवार योग के साथ, इसके अतिरिक्त एक प्राप्त होता है <math>S_n + E_n</math>, त्रुटि कहां है <math>E_n</math> ऊपर से घिरा है:<ref name=Higham93/>
+आधार स्थितियों में N = 1 के लिए युग्‍मानूसार योग के साथ, इसके अतिरिक्त एक प्राप्त होता है <math>S_n + E_n</math>, जहां त्रुटि है  <math>E_n</math> ऊपर से घिरा है:<ref name=Higham93/>
 :<math>|E_n| \leq \frac{\varepsilon \log_2 n}{1 - \varepsilon \log_2 n} \sum_{i=1}^n |x_i| </math>
-जहां ε नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (जैसे ε ≈ 10)<sup>−16</sup>मानक [[ दोहरी सुनिश्चितता ]] फ़्लोटिंग पॉइंट के लिए)। सामान्यतः, ब्याज की मात्रा सापेक्ष त्रुटि होती है <math>|E_n|/|S_n|</math>, जो इसलिए ऊपर से घिरा है:
+जहां ε नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (उदाहरण के लिए मानक दोहरी सुनिश्चितता फ़्लोटिंग पॉइंट के लिए ε ≈ 10<sup>−16</sup>)। सामान्यतः, ब्याज की मात्रा सापेक्ष त्रुटि होती है <math>|E_n|/|S_n|</math>, जो इसलिए ऊपर से घिरा है:
 :<math>\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). </math>
-सापेक्ष त्रुटि सीमा के लिए अभिव्यक्ति में, अंश (Σ|x<sub>i</sub>|||Σx<sub>i</sub>|) योग समस्या की शर्त संख्या है। अनिवार्य रूप से, शर्त संख्या त्रुटियों के लिए योग समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, यदि  इसकी गणना कैसे की जाती है।<ref>L. N. Trefethen and D. Bau, ''Numerical Linear Algebra'' (SIAM: Philadelphia, 1997).</ref> निश्चित परिशुद्धता में एक निश्चित एल्गोरिदम द्वारा प्रत्येक ([[पीछे की ओर स्थिर]]) योग विधि की सापेक्ष त्रुटि (अर्थात वह नहीं जो मनमानी-त्रुटिहीन अंकगणित का उपयोग करते हैं, न ही एल्गोरिदम जिनकी स्मृति और समय की आवश्यकताएं डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के लिए आनुपातिक है .<ref name=Higham93/>  एक खराब स्थिति वाली योग समस्या वह होती है जिसमें यह अनुपात बड़ा होता है, और इस स्थितियों में जोड़ीवार योग में भी बड़ी सापेक्ष त्रुटि हो सकती है। उदाहरण के लिए, यदि सारांश x<sub>i</sub>शून्य माध्य के साथ असंबंधित यादृच्छिक संख्याएं हैं, योग एक यादृच्छिक चलना है और स्थिति संख्या आनुपातिक रूप से बढ़ेगी <math>\sqrt{n}</math>. दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को एक परिमित स्थिरांक के रूप में दर्शाती है <math>n\to\infty</math>. यदि सभी इनपुट गैर-ऋणात्मक हैं, तब शर्त संख्या 1 है।
+सापेक्ष त्रुटि सीमा के लिए अभिव्यक्ति में, अंश (Σ|''x<sub>i</sub>''|/|Σ''x<sub>i</sub>''|) योग समस्या की शर्त संख्या है। इस प्रकार अनिवार्य रूप से, शर्त संख्या त्रुटियों के लिए योग समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, यदि इसकी गणना कैसे की जाती है।<ref>L. N. Trefethen and D. Bau, ''Numerical Linear Algebra'' (SIAM: Philadelphia, 1997).</ref> निश्चित परिशुद्धता में एक निश्चित एल्गोरिदम द्वारा प्रत्येक योग विधि की सापेक्ष त्रुटि (अर्थात वह नहीं जो मनमानी-त्रुटिहीन अंकगणित का उपयोग करते हैं, न ही एल्गोरिदम जिनकी स्मृति और समय की आवश्यकताएं डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के लिए आनुपातिक है .<ref name=Higham93/> एक गुणहीन स्थिति वाली योग समस्या वह होती है जिसमें यह अनुपात बड़ा होता है, और इस स्थितियों में युग्‍मानूसार योग में भी बड़ी सापेक्ष त्रुटि हो सकती है। इस प्रकार उदाहरण के लिए, यदि सारांश x<sub>i</sub>शून्य माध्य के साथ असंबंधित यादृच्छिक संख्याएं हैं, योग एक यादृच्छिक चलना है और स्थिति संख्या आनुपातिक रूप से बढ़ेगी <math>\sqrt{n}</math>. दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को एक परिमित स्थिरांक के रूप में दर्शाती है <math>n\to\infty</math>. यदि सभी इनपुट गैर-ऋणात्मक हैं, तब शर्त संख्या 1 है।
-ध्यान दें कि <math>1 - \varepsilon \log_2 n</math> चूँकि व्यवहार में हर प्रभावी रूप से 1 है <math>\varepsilon \log_2 n</math> जब तक n क्रम 2 का न हो जाए तब तक 1 से बहुत छोटा होता है<sup>1/ε</sup>, जो लगभग 10 है<sup>10<sup>15</sup></sup>दोगुनी परिशुद्धता में।
-इसकी तुलना में, सरल योग के लिए बाध्य सापेक्ष त्रुटि (केवल अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण पर पूर्णांक बनाना) इस प्रकार बढ़ती है <math>O(\varepsilon n)</math> शर्त संख्या से गुणा किया गया।<ref name=Higham93/>  व्यवहार में, इसकी बहुत अधिक संभावना है कि पूर्णांकन त्रुटियों में शून्य माध्य के साथ एक यादृच्छिक चिह्न होता है, जिससे वह एक यादृच्छिक चाल बनाते हैं; इस स्थितियों में, सरल योग में मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो बढ़ती है <math>O(\varepsilon \sqrt{n})</math> और जोड़ीवार योग में एक त्रुटि है जो बढ़ती है <math>O(\varepsilon \sqrt{\log n})</math> औसत पर।<ref name="Tasche"/>
+ध्यान दें कि <math>1 - \varepsilon \log_2 n</math> चूँकि व्यवहार में हर प्रभावी रूप से 1 है <math>\varepsilon \log_2 n</math> जब तक n क्रम 2<sup>1/ε</sup> का न हो जाए तब तक 1 से बहुत छोटा होता है, जो दोगुनी परिशुद्धता में लगभग 10<sup>10<sup>15</sup></sup> है।
+इसकी तुलना में, सरल योग के लिए बाध्य सापेक्ष त्रुटि (केवल अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण पर पूर्णांक बनाना) इस प्रकार बढ़ती है <math>O(\varepsilon n)</math> शर्त संख्या से गुणा किया गया।<ref name=Higham93/> इस प्रकार व्यवहार में, इसकी बहुत अधिक संभावना है कि पूर्णांकन त्रुटियों में शून्य माध्य के साथ एक यादृच्छिक चिह्न होता है, जिससे वह एक यादृच्छिक चाल बनाते हैं; इस स्थितियों में, सरल योग में मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो बढ़ती है <math>O(\varepsilon \sqrt{n})</math> और युग्‍मानूसार योग में एक त्रुटि है जो बढ़ती है <math>O(\varepsilon \sqrt{\log n})</math> औसत पर।<ref name="Tasche"/>
 ==सॉफ़्टवेयर कार्यान्वयन==
-[[NumPy]] में जोड़ीवार योग डिफ़ॉल्ट योग एल्गोरिथ्म है<ref>[https://github.com/numpy/numpy/pull/3685 ENH: implement pairwise summation], github.com/numpy/numpy pull request #3685 (September 2013).</ref> और [[जूलिया (प्रोग्रामिंग भाषा)]]|जूलिया विधि ी-कंप्यूटिंग भाषा,<ref>[https://github.com/JuliaLang/julia/pull/4039 RFC: use pairwise summation for sum, cumsum, and cumprod], github.com/JuliaLang/julia pull request #4039 (August 2013).</ref> जहां दोनों स्थितियों में यह पाया गया कि इसमें सरल योग के लिए तुलनीय गति थी (एक बड़े आधार स्थितियों के उपयोग के लिए धन्यवाद)।
+युग्‍मानूसार योग NumPy और [[जूलिया तकनीकी-कंप्यूटिंग भाषा]] में डिफ़ॉल्ट योग एल्गोरिथ्म है।<ref>[https://github.com/numpy/numpy/pull/3685 ENH: implement pairwise summation], github.com/numpy/numpy pull request #3685 (September 2013).</ref> इस प्रकार जहां दोनों स्थितियों में यह पाया गया कि इसमें सरल योग के लिए तुलनीय गति थी (एक बड़े आधार की स्थितियों में उपयोग के लिए धन्यवाद)।
-अन्य सॉफ़्टवेयर कार्यान्वयन में HPCsharp लाइब्रेरी सम्मिलित है<ref>https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance C# algorithms</ref> [[सी शार्प (प्रोग्रामिंग भाषा)]] भाषा और मानक पुस्तकालय सारांश के लिए<ref>{{Cite web|title=std.algorithm.iteration - डी प्रोग्रामिंग भाषा|url=https://dlang.org/phobos/std_algorithm_iteration.html#sum|access-date=2021-04-23|website=dlang.org}}</ref> [[डी (प्रोग्रामिंग भाषा)]] में।
+अन्य सॉफ़्टवेयर कार्यान्वयन में C# भाषा के लिए HPCsharp लाइब्रेरी<ref>{{Cite web|title=std.algorithm.iteration - डी प्रोग्रामिंग भाषा|url=https://dlang.org/phobos/std_algorithm_iteration.html#sum|access-date=2021-04-23|website=dlang.org}}</ref> और [[डी (प्रोग्रामिंग भाषा)]] में मानक लाइब्रेरी सारांश<ref>https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance C# algorithms</ref> सम्मिलित हैं।
 ==संदर्भ==
@@ Line 62: / Line 57: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 16/08/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

युग्‍मानूसार योग: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:05, 1 December 2023

Contents

एल्गोरिदम

त्रुटिहीनता

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

युग्‍मानूसार योग: Difference between revisions

Latest revision as of 10:05, 1 December 2023

एल्गोरिदम

त्रुटिहीनता

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories