कहन सुम्मेशन एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
संख्यात्मक विश्लेषण में, '''कहन योग एल्गोरिथ्म''', जिसे क्षतिपूर्ति योग के रूप में भी जाना जाता है,<ref>Strictly, there exist other variants of compensated summation as well: see {{cite book |first=Nicholas |last=Higham |title=Accuracy and Stability of Numerical Algorithms (2 ed) |publisher=SIAM |year=2002 |pages=110–123 |isbn=978-0-89871-521-7}}</ref> स्पष्ट दृष्टिकोण की तुलना में, परिमित-स्पष्ट फ़्लोटिंग-पॉइंट संख्याओं के अनुक्रम को जोड़कर प्राप्त कुल में संख्यात्मक त्रुटि को अधिक कम कर देता है। यह एक अलग चल रहे क्षतिपूर्ति (छोटी त्रुटियों को जमा करने के लिए एक चर) को रखकर किया जाता है, जो वास्तव में क्षतिपूर्ति वेरिएबल की परिशुद्धता द्वारा योग की परिशुद्धता को बढ़ाता है।
संख्यात्मक विश्लेषण में, '''कहन सुम्मेशन एल्गोरिथ्म''', जिसे क्षतिपूर्ति सुम्मेशन के रूप में भी जाना जाता है,<ref>Strictly, there exist other variants of compensated summation as well: see {{cite book |first=Nicholas |last=Higham |title=Accuracy and Stability of Numerical Algorithms (2 ed) |publisher=SIAM |year=2002 |pages=110–123 |isbn=978-0-89871-521-7}}</ref> स्पष्ट दृष्टिकोण की तुलना में, परिमित-स्पष्ट फ़्लोटिंग-पॉइंट संख्याओं के अनुक्रम को जोड़कर प्राप्त कुल में संख्यात्मक त्रुटि को अधिक कम कर देता है। यह एक अलग चल रहे क्षतिपूर्ति (छोटी त्रुटियों को जमा करने के लिए एक चर) को रखकर किया जाता है, जो वास्तव में क्षतिपूर्ति वेरिएबल की परिशुद्धता द्वारा सुम्मेशन की परिशुद्धता को बढ़ाता है।


विशेष रूप से, क्रम में केवल <math>n</math> संख्याओं को जोड़ने पर सबसे व्यर्थ स्थिति वाली त्रुटि होती है जो <math>n</math> के आनुपातिक रूप से बढ़ती है, और एक मूल माध्य वर्ग त्रुटि होती है जो यादृच्छिक इनपुट के लिए <math>\sqrt{n}</math> के रूप में बढ़ती है (राउंडऑफ़ त्रुटियां एक यादृच्छिक चाल बनाती हैं)।<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 | bibcode=1993SJSC...14..783H | citeseerx=10.1.1.43.3535 | s2cid=14071038 | url=https://pdfs.semanticscholar.org/5c17/9d447a27c40a54b2bf8b1b2d6819e63c1a69.pdf}}.</ref> क्षतिपूर्ति योग के साथ, पर्याप्त उच्च परिशुद्धता के साथ क्षतिपूर्ति चर का उपयोग करते हुए सबसे व्यर्थ स्थिति वाली त्रुटि सीमा प्रभावी रूप से n से स्वतंत्र होती है, इसलिए बड़ी संख्या में मानों को एक त्रुटि के साथ सारांशित किया जा सकता है जो केवल परिणाम की फ़्लोटिंग-पॉइंट परिशुद्धता पर निर्भर करता है <ref name="Higham93" />
विशेष रूप से, क्रम में केवल <math>n</math> संख्याओं को जोड़ने पर सबसे व्यर्थ स्थिति वाली त्रुटि होती है जो <math>n</math> के आनुपातिक रूप से बढ़ती है, और एक मूल माध्य वर्ग त्रुटि होती है जो यादृच्छिक इनपुट के लिए <math>\sqrt{n}</math> के रूप में बढ़ती है (राउंडऑफ़ त्रुटियां एक यादृच्छिक चाल बनाती हैं)।<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 | bibcode=1993SJSC...14..783H | citeseerx=10.1.1.43.3535 | s2cid=14071038 | url=https://pdfs.semanticscholar.org/5c17/9d447a27c40a54b2bf8b1b2d6819e63c1a69.pdf}}.</ref> क्षतिपूर्ति सुम्मेशन के साथ, पर्याप्त उच्च परिशुद्धता के साथ क्षतिपूर्ति चर का उपसुम्मेशन करते हुए सबसे व्यर्थ स्थिति वाली त्रुटि सीमा प्रभावी रूप से n से स्वतंत्र होती है, इसलिए बड़ी संख्या में मानों को एक त्रुटि के साथ सारांशित किया जा सकता है जो केवल परिणाम की फ़्लोटिंग-पॉइंट परिशुद्धता पर निर्भर करता है <ref name="Higham93" />


[[कलन विधि|एल्गोरिथ्म]] का श्रेय [[विलियम कहाँ]] को दिया जाता है;<ref name="kahan65">{{Citation |last=Kahan |first=William |title=Further remarks on reducing truncation errors |date=January 1965 |url=http://mgnet.org/~douglas/Classes/na-sc/notes/kahan.pdf |journal=[[Communications of the ACM]] |volume=8 |issue=1 |page=40 |archive-url=https://web.archive.org/web/20180209003010/http://mgnet.org/~douglas/Classes/na-sc/notes/kahan.pdf |doi=10.1145/363707.363723 |s2cid=22584810 |archive-date=9 February 2018}}.</ref> ऐसा लगता है कि इवो बाबुस्का स्वतंत्र रूप से एक समान एल्गोरिथ्म के साथ आए हैं (इसलिए कहन-बाबुस्का सारांश)।<ref>Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)</ref> समान, पहले की तकनीकें, उदाहरण के लिए, ब्रेसेनहैम की लाइन एल्गोरिदम हैं, जो पूर्णांक संचालन में संचित त्रुटि का ट्रैक रखती हैं (चूँकि पहली बार उसी समय के आसपास प्रलेखित किया गया था)<ref>{{cite journal |first=Jack E. |last=Bresenham |url=http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf |title=डिजिटल प्लॉटर के कंप्यूटर नियंत्रण के लिए एल्गोरिदम|journal=IBM Systems Journal |volume=4 |issue=1 |date=January 1965 |pages=25–30 |doi=10.1147/sj.41.0025 |s2cid=41898371 }}</ref>) और [[डेल्टा-सिग्मा मॉड्यूलेशन]] है।<ref>{{cite journal |first1=H. |last1=Inose |first2=Y. |last2=Yasuda |first3=J. |last3=Murakami |title=A Telemetering System by Code Manipulation – ΔΣ Modulation |journal=IRE Transactions on Space Electronics and Telemetry |date=September 1962 |pages=204–209|volume=SET-8|  doi=10.1109/IRET-SET.1962.5008839 |s2cid=51647729 }}</ref>
एल्गोरिथ्म का श्रेय विलियम काहन को दिया जाता है;<ref name="kahan65">{{Citation |last=Kahan |first=William |title=Further remarks on reducing truncation errors |date=January 1965 |url=http://mgnet.org/~douglas/Classes/na-sc/notes/kahan.pdf |journal=[[Communications of the ACM]] |volume=8 |issue=1 |page=40 |archive-url=https://web.archive.org/web/20180209003010/http://mgnet.org/~douglas/Classes/na-sc/notes/kahan.pdf |doi=10.1145/363707.363723 |s2cid=22584810 |archive-date=9 February 2018}}.</ref> ऐसा लगता है कि इवो बाबुस्का स्वतंत्र रूप से एक समान एल्गोरिथ्म के साथ आए हैं (इसलिए कहन-बाबुस्का सारांश)।<ref>Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)</ref> समान, पहले की तकनीकें, उदाहरण के लिए, ब्रेसेनहैम की लाइन एल्गोरिदम हैं, जो पूर्णांक संचालन में संचित त्रुटि का ट्रैक रखती हैं (चूँकि पहली बार उसी समय के आसपास प्रलेखित किया गया था)<ref>{{cite journal |first=Jack E. |last=Bresenham |url=http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf |title=डिजिटल प्लॉटर के कंप्यूटर नियंत्रण के लिए एल्गोरिदम|journal=IBM Systems Journal |volume=4 |issue=1 |date=January 1965 |pages=25–30 |doi=10.1147/sj.41.0025 |s2cid=41898371 }}</ref>) और [[डेल्टा-सिग्मा मॉड्यूलेशन]] है।<ref>{{cite journal |first1=H. |last1=Inose |first2=Y. |last2=Yasuda |first3=J. |last3=Murakami |title=A Telemetering System by Code Manipulation – ΔΣ Modulation |journal=IRE Transactions on Space Electronics and Telemetry |date=September 1962 |pages=204–209|volume=SET-8|  doi=10.1109/IRET-SET.1962.5008839 |s2cid=51647729 }}</ref>




Line 24: Line 24:




इस एल्गोरिथम को फास्ट2सम एल्गोरिथम का उपयोग करने के लिए फिर से लिखा जा सकता है:<ref>{{cite book |author-last1=Muller |author-first1=Jean-Michel |author-last2=Brunie |author-first2=Nicolas |author-last3=de Dinechin |author-first3=Florent |author-last4=Jeannerod |author-first4=Claude-Pierre |author-first5=Mioara |author-last5=Joldes |author-last6=Lefèvre |author-first6=Vincent |author-last7=Melquiond |author-first7=Guillaume |author-last8=Revol |author-first8=Nathalie|author8-link=Nathalie Revol |author-last9=Torres |author-first9=Serge |title=फ़्लोटिंग-पॉइंट अंकगणित की पुस्तिका|date=2018 |orig-year=2010 |publisher=[[Birkhäuser]] |edition=2 |isbn=978-3-319-76525-9 |lccn=2018935254 |doi=10.1007/978-3-319-76526-6 |url=https://books.google.com/books?id=h3ZZDwAAQBAJ |page=179}}</ref><syntaxhighlight>
इस एल्गोरिथम को फास्ट2सम एल्गोरिथम का उपसुम्मेशन करने के लिए फिर से लिखा जा सकता है:<ref>{{cite book |author-last1=Muller |author-first1=Jean-Michel |author-last2=Brunie |author-first2=Nicolas |author-last3=de Dinechin |author-first3=Florent |author-last4=Jeannerod |author-first4=Claude-Pierre |author-first5=Mioara |author-last5=Joldes |author-last6=Lefèvre |author-first6=Vincent |author-last7=Melquiond |author-first7=Guillaume |author-last8=Revol |author-first8=Nathalie|author8-link=Nathalie Revol |author-last9=Torres |author-first9=Serge |title=फ़्लोटिंग-पॉइंट अंकगणित की पुस्तिका|date=2018 |orig-year=2010 |publisher=[[Birkhäuser]] |edition=2 |isbn=978-3-319-76525-9 |lccn=2018935254 |doi=10.1007/978-3-319-76526-6 |url=https://books.google.com/books?id=h3ZZDwAAQBAJ |page=179}}</ref><syntaxhighlight>
function KahanSum2(input)
function KahanSum2(input)
     var sum = 0.0                    // Prepare the accumulator.
     var sum = 0.0                    // Prepare the accumulator.
Line 39: Line 39:


===कार्य उदाहरण===
===कार्य उदाहरण===
यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपयोग करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव [[फ़्लोटिंग-पॉइंट अंकगणित]] का उपयोग कर रहे हैं, <code>sum</code> मान 10000.0 प्राप्त कर लिया है, और अगले दो मान <code>input[i]</code> 3.14159 और 2.71828 हैं। स्पष्ट परिणाम 10005.85987 है, जो 10005.9 के समान है। एक सादे योग के साथ, प्रत्येक आने वाले मूल्य को संरेखित किया जाएगा <code>sum</code>, और कई निम्न-क्रम अंक खो जाएंगे (काट-छांट या पूर्णांकन द्वारा) पूर्णांकन के बाद पहला परिणाम 10003.1 होगा। दूसरा परिणाम राउंडिंग से पहले 10005.81828 और राउंडिंग के बाद 10005.8 होगा। यह सही नहीं है।
यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपसुम्मेशन करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव [[फ़्लोटिंग-पॉइंट अंकगणित]] का उपसुम्मेशन कर रहे हैं, <code>sum</code> मान 10000.0 प्राप्त कर लिया है, और अगले दो मान <code>input[i]</code> 3.14159 और 2.71828 हैं। स्पष्ट परिणाम 10005.85987 है, जो 10005.9 के समान है। एक सादे सुम्मेशन के साथ, प्रत्येक आने वाले मूल्य को संरेखित किया जाएगा <code>sum</code>, और कई निम्न-क्रम अंक खो जाएंगे (काट-छांट या पूर्णांकन द्वारा) पूर्णांकन के बाद पहला परिणाम 10003.1 होगा। दूसरा परिणाम राउंडिंग से पहले 10005.81828 और राउंडिंग के बाद 10005.8 होगा। यह सही नहीं है।


यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपयोग करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव फ़्लोटिंग-पॉइंट अंकगणित का उपयोग कर रहे हैं, योग मान 10000.0 तक पहुंच गया है, और <code>input[i]</code>के अगले दो मान 3.14159 और 2.71828 हैं। स्पष्ट परिणाम 10005.85987 है, जो 10005.9 के समान है। एक सादे <code>sum</code> के साथ, प्रत्येक आने वाले मूल्य को <code>sum</code>के साथ संरेखित किया जाएगा, और कई निम्न-क्रम अंक खो जाएंगे (खंडन या पूर्णांकन द्वारा) पूर्णांकन के बाद पहला परिणाम 10003.1 होगा। दूसरा परिणाम राउंडिंग से पहले 10005.81828 और राउंडिंग के बाद 10005.8 होगा। यह सही नहीं है।
यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपसुम्मेशन करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव फ़्लोटिंग-पॉइंट अंकगणित का उपसुम्मेशन कर रहे हैं, सुम्मेशन मान 10000.0 तक पहुंच गया है, और <code>input[i]</code>के अगले दो मान 3.14159 और 2.71828 हैं। स्पष्ट परिणाम 10005.85987 है, जो 10005.9 के समान है। एक सादे <code>sum</code> के साथ, प्रत्येक आने वाले मूल्य को <code>sum</code>के साथ संरेखित किया जाएगा, और कई निम्न-क्रम अंक खो जाएंगे (खंडन या पूर्णांकन द्वारा) पूर्णांकन के बाद पहला परिणाम 10003.1 होगा। दूसरा परिणाम राउंडिंग से पहले 10005.81828 और राउंडिंग के बाद 10005.8 होगा। यह सही नहीं है।


चूँकि क्षतिपूर्ति योग के साथ, हमें 10005.9 का सही पूर्णांकित परिणाम मिलता है।
चूँकि क्षतिपूर्ति सुम्मेशन के साथ, हमें 10005.9 का सही पूर्णांकित परिणाम मिलता है।


ये मान लीजिए <code>c</code> प्रारंभिक मान शून्य है.<syntaxhighlight>
ये मान लीजिए <code>c</code> प्रारंभिक मान शून्य है.<syntaxhighlight>
Line 57: Line 57:
   
   


योग इतना बड़ा है कि केवल इनपुट संख्याओं के उच्च-क्रम अंक ही जमा हो रहे हैं। किंतु अगले चरण पर, <code>c</code> त्रुटि देता है.<syntaxhighlight>
सुम्मेशन इतना बड़ा है कि केवल इनपुट संख्याओं के उच्च-क्रम अंक ही जमा हो रहे हैं। किंतु अगले चरण पर, <code>c</code> त्रुटि देता है.<syntaxhighlight>
   y = 2.71828 - (-0.0415900)        The shortfall from the previous stage gets included.
   y = 2.71828 - (-0.0415900)        The shortfall from the previous stage gets included.
     = 2.75987                      It is of a size similar to y: most digits meet.
     = 2.75987                      It is of a size similar to y: most digits meet.
Line 69: Line 69:
</syntaxhighlight>
</syntaxhighlight>
    
    
तो योग दो संचायकों के साथ किया जाता है: <code>sum</code> योग रखता है, और <code>c</code>उन भागो को जमा करता है जो योग में समाहित नहीं होते हैं, जिससे अगली बार (<code>sum</code> ) के निम्न-क्रम वाले भाग को हल किया जा सकता है । इस प्रकार सारांश <code>c</code>में "गार्ड अंक" के साथ आगे बढ़ता है, जो किसी भी न होने से उत्तम है, किंतु इनपुट की दोगुनी स्पष्टता के साथ गणना करने जितना अच्छा नहीं है। चूँकि केवल गणनाओं की स्पष्टता बढ़ाना सामान्य रूप से व्यावहारिक नहीं है; यदि <code>input</code> पहले से ही दोगुनी परिशुद्धता में है, तो कुछ सिस्टम क्वाडरूपल परिशुद्धता की आपूर्ति करते हैं, और यदि वे करते हैं, तो इनपुट क्वाडरूपल परिशुद्धता में हो सकता है।
तो सुम्मेशन दो संचायकों के साथ किया जाता है: <code>sum</code> सुम्मेशन रखता है, और <code>c</code>उन भागो को जमा करता है जो सुम्मेशन में समाहित नहीं होते हैं, जिससे अगली बार (<code>sum</code> ) के निम्न-क्रम वाले भाग को हल किया जा सकता है । इस प्रकार सारांश <code>c</code>में "गार्ड अंक" के साथ आगे बढ़ता है, जो किसी भी न होने से उत्तम है, किंतु इनपुट की दोगुनी स्पष्टता के साथ गणना करने जितना अच्छा नहीं है। चूँकि केवल गणनाओं की स्पष्टता बढ़ाना सामान्य रूप से व्यावहारिक नहीं है; यदि <code>input</code> पहले से ही दोगुनी परिशुद्धता में है, तो कुछ सिस्टम क्वाडरूपल परिशुद्धता की आपूर्ति करते हैं, और यदि वे करते हैं, तो इनपुट क्वाडरूपल परिशुद्धता में हो सकता है।


==स्पष्टता ==
==स्पष्टता ==
इसकी स्पष्टता विशेषताओं की सराहना करने के लिए क्षतिपूर्ति योग में त्रुटियों का सावधानीपूर्वक विश्लेषण आवश्यक है। चूँकि यह सरल योग से अधिक स्पष्ट है, फिर भी यह अनिर्धारित योगों के लिए बड़ी सापेक्ष त्रुटियाँ दे सकता है।
इसकी स्पष्टता विशेषताओं की सराहना करने के लिए क्षतिपूर्ति सुम्मेशन में त्रुटियों का सावधानीपूर्वक विश्लेषण आवश्यक है। चूँकि यह सरल सुम्मेशन से अधिक स्पष्ट है, फिर भी यह अनिर्धारित सुम्मेशनों के लिए बड़ी सापेक्ष त्रुटियाँ दे सकता है।


मान लीजिए कि कोई <math>n                                                                                                                                                                                                    </math> मानों <math>x_i</math> का योग है, <math>i = 1, \, \ldots, \, n</math> के लिए स्पष्ट योग है
मान लीजिए कि कोई <math>n                                                                                                                                                                                                    </math> मानों <math>x_i</math> का सुम्मेशन है, <math>i = 1, \, \ldots, \, n</math> के लिए स्पष्ट सुम्मेशन है
: <math>S_n = \sum_{i=1}^n x_i</math> (अनंत परिशुद्धता के साथ गणना की गई)।
: <math>S_n = \sum_{i=1}^n x_i</math> (अनंत परिशुद्धता के साथ गणना की गई)।
क्षतिपूर्ति के योग के साथ, व्यक्ति को <math>S_n + E_n</math> प्राप्त होता है, जहां त्रुटि <math>E_n</math> से घिरा होता है<ref name=Higham93/>  
क्षतिपूर्ति के सुम्मेशन के साथ, व्यक्ति को <math>S_n + E_n</math> प्राप्त होता है, जहां त्रुटि <math>E_n</math> से घिरा होता है<ref name=Higham93/>  


<math>|E_n| \le \big[2\varepsilon + O(n\varepsilon^2)\big] \sum_{i=1}^n |x_i|,</math>
<math>|E_n| \le \big[2\varepsilon + O(n\varepsilon^2)\big] \sum_{i=1}^n |x_i|,</math>
Line 82: Line 82:
जहाँ <math>\varepsilon</math> नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (उदाहरण के लिए आईईईई मानक डबल-प्रिसिजन फ़्लोटिंग पॉइंट के लिए <math>\varepsilon \approx 10^{-16}</math>)। समान्यत: ब्याज की मात्रा सापेक्ष त्रुटि होती है <math>|E_n|/|S_n|</math>, जो इसलिए ऊपर से घिरा है
जहाँ <math>\varepsilon</math> नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (उदाहरण के लिए आईईईई मानक डबल-प्रिसिजन फ़्लोटिंग पॉइंट के लिए <math>\varepsilon \approx 10^{-16}</math>)। समान्यत: ब्याज की मात्रा सापेक्ष त्रुटि होती है <math>|E_n|/|S_n|</math>, जो इसलिए ऊपर से घिरा है
: <math>\frac{|E_n|}{|S_n|} \le \big[2\varepsilon + O(n\varepsilon^2)\big] \frac{\sum\limits_{i=1}^n |x_i|}{\left|\sum\limits_{i=1}^n x_i\right|}.</math>
: <math>\frac{|E_n|}{|S_n|} \le \big[2\varepsilon + O(n\varepsilon^2)\big] \frac{\sum\limits_{i=1}^n |x_i|}{\left|\sum\limits_{i=1}^n x_i\right|}.</math>
सापेक्ष त्रुटि सीमा के लिए अभिव्यक्ति में, अंश <math>\Sigma |x_i| / |\Sigma x_i|</math> योग समस्या की [[शर्त संख्या|नियमित संख्या]] है. अनिवार्य रूप से, नियमित संख्या त्रुटियों के लिए योग समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, तथापि इसकी गणना कैसे की जाती है।<ref>{{cite book |first1=Lloyd N. |authorlink1=Lloyd N. Trefethen |last1=Trefethen |first2=David |last2=Bau |title=संख्यात्मक रैखिक बीजगणित|publisher=SIAM |location=Philadelphia |year=1997 |isbn=978-0-89871-361-9}}</ref> निश्चित परिशुद्धता में एक निश्चित एल्गोरिदम द्वारा प्रत्येक (पिछली स्थिर) योग विधि से जुड़ी सापेक्ष त्रुटि (अथार्त वे नहीं जो इच्छित -स्पष्ट अंकगणित का उपयोग करते हैं, न ही एल्गोरिदम जिनकी मेमोरी और समय की आवश्यकताएं डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के लिए आनुपातिक है।<ref name="Higham93" /> एक व्यर्थ स्थिति वाली योग समस्या वह होती है जिसमें यह अनुपात बड़ा होता है, और इस स्थिति में क्षतिपूर्ति योग में भी बड़ी सापेक्ष त्रुटि हो सकती है। उदाहरण के लिए, यदि सारांश <math>x_i</math> शून्य माध्य के साथ असंबंधित यादृच्छिक संख्याएं हैं, योग एक यादृच्छिक चलना है, और स्थिति संख्या आनुपातिक रूप से बढ़ेगी <math>\sqrt{n}</math>. दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को एक परिमित स्थिरांक <math>n \to \infty</math> के रूप में दर्शाती है यदि सभी इनपुट गैर-ऋणात्मक हैं, तो नियमित संख्या 1 है।
सापेक्ष त्रुटि सीमा के लिए अभिव्यक्ति में, अंश <math>\Sigma |x_i| / |\Sigma x_i|</math> सुम्मेशन समस्या की [[शर्त संख्या|नियमित संख्या]] है. अनिवार्य रूप से, नियमित संख्या त्रुटियों के लिए सुम्मेशन समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, तथापि इसकी गणना कैसे की जाती है।<ref>{{cite book |first1=Lloyd N. |authorlink1=Lloyd N. Trefethen |last1=Trefethen |first2=David |last2=Bau |title=संख्यात्मक रैखिक बीजगणित|publisher=SIAM |location=Philadelphia |year=1997 |isbn=978-0-89871-361-9}}</ref> निश्चित परिशुद्धता में एक निश्चित एल्गोरिदम द्वारा प्रत्येक (पिछली स्थिर) सुम्मेशन विधि से जुड़ी सापेक्ष त्रुटि (अथार्त वे नहीं जो इच्छित -स्पष्ट अंकगणित का उपसुम्मेशन करते हैं, न ही एल्गोरिदम जिनकी मेमोरी और समय की आवश्यकताएं डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के लिए आनुपातिक है।<ref name="Higham93" /> एक व्यर्थ स्थिति वाली सुम्मेशन समस्या वह होती है जिसमें यह अनुपात बड़ा होता है, और इस स्थिति में क्षतिपूर्ति सुम्मेशन में भी बड़ी सापेक्ष त्रुटि हो सकती है। उदाहरण के लिए, यदि सारांश <math>x_i</math> शून्य माध्य के साथ असंबंधित यादृच्छिक संख्याएं हैं, सुम्मेशन एक यादृच्छिक चलना है, और स्थिति संख्या आनुपातिक रूप से बढ़ेगी <math>\sqrt{n}</math>. दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को एक परिमित स्थिरांक <math>n \to \infty</math> के रूप में दर्शाती है यदि सभी इनपुट गैर-ऋणात्मक हैं, तो नियमित संख्या 1 है।


एक नियम संख्या को देखते हुए, क्षतिपूर्ति योग की सापेक्ष त्रुटि प्रभावी रूप से <math>n</math> से स्वतंत्र है। सिद्धांत रूप में, <math>O (n \varepsilon^2)</math> है जो <math>n</math> के साथ रैखिक रूप से बढ़ता है, किंतु वास्तव में यह शब्द प्रभावी रूप से शून्य है: चूंकि अंतिम परिणाम एक परिशुद्धता के लिए गोल होता है जो,की <math>\varepsilon</math> , <math>n \varepsilon^2</math> पद शून्य तक पूर्णांकित होता है, जब तक कि <math>n                                                                                                                                                                                                                     
एक नियम संख्या को देखते हुए, क्षतिपूर्ति सुम्मेशन की सापेक्ष त्रुटि प्रभावी रूप से <math>n</math> से स्वतंत्र है। सिद्धांत रूप में, <math>O (n \varepsilon^2)</math> है जो <math>n</math> के साथ रैखिक रूप से बढ़ता है, किंतु वास्तव में यह शब्द प्रभावी रूप से शून्य है: चूंकि अंतिम परिणाम एक परिशुद्धता के लिए गोल होता है जो,की <math>\varepsilon</math> , <math>n \varepsilon^2</math> पद शून्य तक पूर्णांकित होता है, जब तक कि <math>n                                                                                                                                                                                                                     
                                                                                                                                                                                                                                   </math> समान्य रूप से <math>1 / \varepsilon</math> या बड़ा न हो।<ref name="Higham93" /> दोहरी परिशुद्धता में, यह लगभग <math>10^{16}</math> के <math>n</math> से मेल खाता है, जो अधिकांश योगों से बहुत बड़ा है। तो, एक निश्चित नियम संख्या के लिए, क्षतिपूर्ति योग की त्रुटियां प्रभावी रूप से <math>O (\varepsilon)</math> होती हैं, जो <math>n</math> से स्वतंत्र होती हैं।
                                                                                                                                                                                                                                   </math> समान्य रूप से <math>1 / \varepsilon</math> या बड़ा न हो।<ref name="Higham93" /> दोहरी परिशुद्धता में, यह लगभग <math>10^{16}</math> के <math>n</math> से मेल खाता है, जो अधिकांश सुम्मेशनों से बहुत बड़ा है। तो, एक निश्चित नियम संख्या के लिए, क्षतिपूर्ति सुम्मेशन की त्रुटियां प्रभावी रूप से <math>O (\varepsilon)</math> होती हैं, जो <math>n</math> से स्वतंत्र होती हैं।


इसकी तुलना में, सरल योग के लिए बाध्य सापेक्ष त्रुटि (केवल अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण पर पूर्णांक बनाना) <math>O(\varepsilon n)</math> को नियम संख्या से गुणा करने पर बढ़ती है।<ref name="Higham93" /> चूँकि , यह सबसे व्यर्थ स्थिति वाली त्रुटि वास्तव में संभवतः ही कभी देखी जाती है, क्योंकि यह केवल तभी होती है जब पूर्णांकन त्रुटियाँ सभी एक ही दिशा में होती हैं। वास्तव में, इसकी बहुत अधिक संभावना है कि पूर्णांकन त्रुटियों में शून्य माध्य के साथ एक यादृच्छिक चिह्न होता है, जिससे वे एक यादृच्छिक चाल बनाते हैं; इस स्थिति में, सरल योग में एक मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो कि स्थिति संख्या से गुणा करने पर <math>O\left(\varepsilon \sqrt{n}\right)</math> बढ़ती है।<ref name="Tasche">Manfred Tasche and Hansmartin Zeuner, ''Handbook of Analytic-Computational Methods in Applied Mathematics'', Boca Raton, FL: CRC Press, 2000.</ref> चूँकि , यह अभी भी क्षतिपूर्ति के योग से बहुत व्यर्थ है। चूँकि यदि योग को दोगुनी परिशुद्धता में निष्पादित किया जा सकता है, तो <math>O(n \varepsilon^2)</math> को <math>\varepsilon^2</math> द्वारा प्रतिस्थापित किया जाता है, और मूल परिशुद्धता पर क्षतिपूर्ति योग में <math>O(n \varepsilon^2)</math> शब्द की तुलना में मूल योग में सबसे व्यर्थ स्थिति वाली त्रुटि होती है।
इसकी तुलना में, सरल सुम्मेशन के लिए बाध्य सापेक्ष त्रुटि (केवल अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण पर पूर्णांक बनाना) <math>O(\varepsilon n)</math> को नियम संख्या से गुणा करने पर बढ़ती है।<ref name="Higham93" /> चूँकि , यह सबसे व्यर्थ स्थिति वाली त्रुटि वास्तव में संभवतः ही कभी देखी जाती है, क्योंकि यह केवल तभी होती है जब पूर्णांकन त्रुटियाँ सभी एक ही दिशा में होती हैं। वास्तव में, इसकी बहुत अधिक संभावना है कि पूर्णांकन त्रुटियों में शून्य माध्य के साथ एक यादृच्छिक चिह्न होता है, जिससे वे एक यादृच्छिक चाल बनाते हैं; इस स्थिति में, सरल सुम्मेशन में एक मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो कि स्थिति संख्या से गुणा करने पर <math>O\left(\varepsilon \sqrt{n}\right)</math> बढ़ती है।<ref name="Tasche">Manfred Tasche and Hansmartin Zeuner, ''Handbook of Analytic-Computational Methods in Applied Mathematics'', Boca Raton, FL: CRC Press, 2000.</ref> चूँकि , यह अभी भी क्षतिपूर्ति के सुम्मेशन से बहुत व्यर्थ है। चूँकि यदि सुम्मेशन को दोगुनी परिशुद्धता में निष्पादित किया जा सकता है, तो <math>O(n \varepsilon^2)</math> को <math>\varepsilon^2</math> द्वारा प्रतिस्थापित किया जाता है, और मूल परिशुद्धता पर क्षतिपूर्ति सुम्मेशन में <math>O(n \varepsilon^2)</math> शब्द की तुलना में मूल सुम्मेशन में सबसे व्यर्थ स्थिति वाली त्रुटि होती है।


उसी प्रतीक के द्वारा, ऊपर <math>\Sigma |x_i|</math> में दिखाई देने वाला <math>E_n</math> सबसे व्यर्थ स्थिति वाला बंधन है जो केवल तब होता है जब सभी गोलाई त्रुटियों का चिह्न समान होता है (और अधिकतम संभव परिमाण के होते हैं)।<ref name="Higham93" /> वास्तव में, यह अधिक संभावना है कि त्रुटियों में यादृच्छिक संकेत होते हैं, जिस स्थिति में <math>\Sigma |x_i|</math> में शब्दों को यादृच्छिक चाल से बदल दिया जाता है, उस स्थिति में, शून्य माध्य वाले यादृच्छिक इनपुट के लिए भी, त्रुटि <math>E_n</math> केवल बढ़ती है <math>O\left(\varepsilon \sqrt{n}\right)</math> (<math>n \varepsilon^2</math> पद को अनदेखा `करते हुए), उसी दर से योग <math>S_n</math> बढ़ता है, जब सापेक्ष त्रुटि की गणना की जाती है तो <math>\sqrt{n}</math> कारकों को समाप्त कर दिया जाता है। इसलिए, असम्बद्ध रूप से गैर-वातानुकूलित योगों के लिए भी, क्षतिपूर्ति के योग के लिए सापेक्ष त्रुटि अधिकांशतः सबसे व्यर्थ स्थिति के विश्लेषण से बहुत छोटी हो सकती है।
उसी प्रतीक के द्वारा, ऊपर <math>\Sigma |x_i|</math> में दिखाई देने वाला <math>E_n</math> सबसे व्यर्थ स्थिति वाला बंधन है जो केवल तब होता है जब सभी गोलाई त्रुटियों का चिह्न समान होता है (और अधिकतम संभव परिमाण के होते हैं)।<ref name="Higham93" /> वास्तव में, यह अधिक संभावना है कि त्रुटियों में यादृच्छिक संकेत होते हैं, जिस स्थिति में <math>\Sigma |x_i|</math> में शब्दों को यादृच्छिक चाल से बदल दिया जाता है, उस स्थिति में, शून्य माध्य वाले यादृच्छिक इनपुट के लिए भी, त्रुटि <math>E_n</math> केवल बढ़ती है <math>O\left(\varepsilon \sqrt{n}\right)</math> (<math>n \varepsilon^2</math> पद को अनदेखा `करते हुए), उसी दर से सुम्मेशन <math>S_n</math> बढ़ता है, जब सापेक्ष त्रुटि की गणना की जाती है तो <math>\sqrt{n}</math> कारकों को समाप्त कर दिया जाता है। इसलिए, असम्बद्ध रूप से गैर-वातानुकूलित सुम्मेशनों के लिए भी, क्षतिपूर्ति के सुम्मेशन के लिए सापेक्ष त्रुटि अधिकांशतः सबसे व्यर्थ स्थिति के विश्लेषण से बहुत छोटी हो सकती है।


==आगे संवर्द्धन==
==आगे संवर्द्धन==
न्यूमैयर <ref name=Neumaier74>{{cite journal |first=A. |last=Neumaier |doi=10.1002/zamm.19740540106 |bibcode=1974ZaMM...54...39N |title=परिमित योगों के योग के लिए कुछ विधियों का पूर्णांकन त्रुटि विश्लेषण|trans-title=Rounding Error Analysis of Some Methods for Summing Finite Sums |language=de |journal=Zeitschrift für Angewandte Mathematik und Mechanik |volume=54 |issue=1 |date=1974 |pages=39–51 |url=https://www.mat.univie.ac.at/~neum/scan/01.pdf}}</ref> कहन एल्गोरिदम का एक उन्नत संस्करण प्रस्तुत किया जाता है, जिसे वह एक उत्तम कहन-बाबुस्का एल्गोरिदम कहते हैं, जो उस स्थिति को भी आवरण करता है जब जोड़ा जाने वाला अगला शब्द चल रहे योग की तुलना में पूर्ण मूल्य में बड़ा होता है, जो बड़े और छोटे की भूमिका को प्रभावी रूप से बदलता है। छद्मकोड में, एल्गोरिथ्म है:<syntaxhighlight>
न्यूमैयर <ref name=Neumaier74>{{cite journal |first=A. |last=Neumaier |doi=10.1002/zamm.19740540106 |bibcode=1974ZaMM...54...39N |title=परिमित योगों के योग के लिए कुछ विधियों का पूर्णांकन त्रुटि विश्लेषण|trans-title=Rounding Error Analysis of Some Methods for Summing Finite Sums |language=de |journal=Zeitschrift für Angewandte Mathematik und Mechanik |volume=54 |issue=1 |date=1974 |pages=39–51 |url=https://www.mat.univie.ac.at/~neum/scan/01.pdf}}</ref> कहन एल्गोरिदम का एक उन्नत संस्करण प्रस्तुत किया जाता है, जिसे वह एक उत्तम कहन-बाबुस्का एल्गोरिदम कहते हैं, जो उस स्थिति को भी आवरण करता है जब जोड़ा जाने वाला अगला शब्द चल रहे सुम्मेशन की तुलना में पूर्ण मूल्य में बड़ा होता है, जो बड़े और छोटे की भूमिका को प्रभावी रूप से बदलता है। छद्मकोड में, एल्गोरिथ्म है:<syntaxhighlight>
function KahanBabushkaNeumaierSum(input)
function KahanBabushkaNeumaierSum(input)
     var sum = 0.0
     var sum = 0.0
Line 143: Line 143:
</syntaxhighlight>
</syntaxhighlight>
==विकल्प==
==विकल्प==
चूँकि काहन का एल्गोरिदम n संख्याओं के योग के लिए <math>O(1)</math> त्रुटि वृद्धि को प्राप्त करता है, केवल कुछ व्यर्थ <math>O(\log n)</math> वृद्धि को जोड़ीदार योग द्वारा प्राप्त किया जा सकता है: कोई संख्याओं के सेट को दो भागो में पुनरावर्ती रूप से विभाजित करता है, प्रत्येक आधे का योग करता है, और फिर जोड़ता है दो मान <ref name=Higham93/> इसका लाभ यह है कि इसमें सरल योग के समान अंकगणितीय परिचालन की आवश्यकता होती है (कहान के एल्गोरिदम के विपरीत, जिसके लिए चार गुना अंकगणित की आवश्यकता होती है और चार गुना सरल योग की विलंबता होती है) और समानांतर में गणना की जा सकती है। पुनरावृत्ति का आधार स्थिति सैद्धांतिक रूप से केवल एक (या शून्य) संख्याओं का योग हो सकता है, किंतु पुनरावृत्ति के ओवरहेड को परिशोधित करने के लिए, समान्यत: एक बड़े आधार स्थिति का उपयोग किया जाएगा। जोड़ीवार योग के समतुल्य का उपयोग कई तेज़ फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम में किया जाता है और यह उन एफएफटी में राउंडऑफ त्रुटियों के लॉगरिदमिक विकास के लिए उत्तरदाई है।<ref>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> वास्तव में, यादृच्छिक संकेतों की राउंडऑफ त्रुटियों के साथ, जोड़ीवार योग की मूल माध्य वर्ग त्रुटियां वास्तव में <math>O\left(\sqrt{\log n}\right)</math> के रूप में बढ़ती हैं।<ref name=Tasche/>
चूँकि काहन का एल्गोरिदम n संख्याओं के सुम्मेशन के लिए <math>O(1)</math> त्रुटि वृद्धि को प्राप्त करता है, केवल कुछ व्यर्थ <math>O(\log n)</math> वृद्धि को जोड़ीदार सुम्मेशन द्वारा प्राप्त किया जा सकता है: कोई संख्याओं के सेट को दो भागो में पुनरावर्ती रूप से विभाजित करता है, प्रत्येक आधे का सुम्मेशन करता है, और फिर जोड़ता है दो मान <ref name=Higham93/> इसका लाभ यह है कि इसमें सरल सुम्मेशन के समान अंकगणितीय परिचालन की आवश्यकता होती है (कहान के एल्गोरिदम के विपरीत, जिसके लिए चार गुना अंकगणित की आवश्यकता होती है और चार गुना सरल सुम्मेशन की विलंबता होती है) और समानांतर में गणना की जा सकती है। पुनरावृत्ति का आधार स्थिति सैद्धांतिक रूप से केवल एक (या शून्य) संख्याओं का सुम्मेशन हो सकता है, किंतु पुनरावृत्ति के ओवरहेड को परिशोधित करने के लिए, समान्यत: एक बड़े आधार स्थिति का उपसुम्मेशन किया जाएगा। जोड़ीवार सुम्मेशन के समतुल्य का उपसुम्मेशन कई तेज़ फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम में किया जाता है और यह उन एफएफटी में राउंडऑफ त्रुटियों के लॉगरिदमिक विकास के लिए उत्तरदाई है।<ref>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> वास्तव में, यादृच्छिक संकेतों की राउंडऑफ त्रुटियों के साथ, जोड़ीवार सुम्मेशन की मूल माध्य वर्ग त्रुटियां वास्तव में <math>O\left(\sqrt{\log n}\right)</math> के रूप में बढ़ती हैं।<ref name=Tasche/>


एक अन्य विकल्प [[मनमाना-सटीक अंकगणित|इच्छित -स्पष्ट अंकगणित]] का उपयोग करना है, जिसे सैद्धांतिक रूप से बहुत अधिक कम्प्यूटेशनल प्रयास की निवेश के साथ पूर्णांकित करने की आवश्यकता नहीं है। इच्छित परिशुद्धता का उपयोग करके बिल्कुल गोल मान निष्पादित करने का एक विधि कई फ़्लोटिंग-पॉइंट घटकों का उपयोग करके अनुकूली रूप से विस्तार करना है। यह उन सामान्य स्थिति में कम्प्यूटेशनल निवेश को कम कर देगा जहां उच्च परिशुद्धता की आवश्यकता नहीं है।<ref>Jonathan R. Shewchuk, [http://www.cs.berkeley.edu/~jrs/papers/robustr.pdf Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates], ''Discrete and Computational Geometry'', vol. 18, pp. 305–363 (October 1997).</ref><ref name="python_fsum">रेमंड हेटिंगर, [http://code.activestate.com/recipes/393090/ रेसिपी 393090: बाइनरी फ़्लोटिंग पॉइंट योग पूर्ण परिशुद्धता के लिए सटीक], शेवचुक (1997) लेख (28 मार्च 2005) से एल्गोरिदम का पायथन कार्यान्वयन। रेफरी>आर. किरचनर, उलरिच डब्ल्यू. कुलिश, वेक्टर प्रोसेसर के लिए सटीक अंकगणित, जर्नल ऑफ़ पैरेलल एंड डिस्ट्रिब्यूटेड कंप्यूटिंग 5 (1988) 250-270। एक हार्डवेयर कार्यान्वयन का वर्णन मुलर, रब और रूलिंग द्वारा किया गया था। रेफरी>एम. मुलर, सी. रब, डब्ल्यू. रूलिंग [http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=145535&isnumber=3902], फ्लोटिंग-पॉइंट संख्याओं का सटीक संचय, कंप्यूटर अंकगणित पर 10वीं IEEE संगोष्ठी की कार्यवाही (जून 1991), {{doi|10.1109/ARITH.1991.145535}}.</ref>
एक अन्य विकल्प [[मनमाना-सटीक अंकगणित|इच्छित -स्पष्ट अंकगणित]] का उपसुम्मेशन करना है, जिसे सैद्धांतिक रूप से बहुत अधिक कम्प्यूटेशनल प्रयास की निवेश के साथ पूर्णांकित करने की आवश्यकता नहीं है। इच्छित परिशुद्धता का उपसुम्मेशन करके बिल्कुल गोल मान निष्पादित करने का एक विधि कई फ़्लोटिंग-पॉइंट घटकों का उपसुम्मेशन करके अनुकूली रूप से विस्तार करना है। यह उन सामान्य स्थिति में कम्प्यूटेशनल निवेश को कम कर देगा जहां उच्च परिशुद्धता की आवश्यकता नहीं है।<ref>Jonathan R. Shewchuk, [http://www.cs.berkeley.edu/~jrs/papers/robustr.pdf Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates], ''Discrete and Computational Geometry'', vol. 18, pp. 305–363 (October 1997).</ref><ref name="python_fsum">रेमंड हेटिंगर, [http://code.activestate.com/recipes/393090/ रेसिपी 393090: बाइनरी फ़्लोटिंग पॉइंट योग पूर्ण परिशुद्धता के लिए सटीक], शेवचुक (1997) लेख (28 मार्च 2005) से एल्गोरिदम का पायथन कार्यान्वयन। रेफरी>आर. किरचनर, उलरिच डब्ल्यू. कुलिश, वेक्टर प्रोसेसर के लिए सटीक अंकगणित, जर्नल ऑफ़ पैरेलल एंड डिस्ट्रिब्यूटेड कंप्यूटिंग 5 (1988) 250-270। एक हार्डवेयर कार्यान्वयन का वर्णन मुलर, रब और रूलिंग द्वारा किया गया था। रेफरी>एम. मुलर, सी. रब, डब्ल्यू. रूलिंग [http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=145535&isnumber=3902], फ्लोटिंग-पॉइंट संख्याओं का सटीक संचय, कंप्यूटर अंकगणित पर 10वीं IEEE संगोष्ठी की कार्यवाही (जून 1991), {{doi|10.1109/ARITH.1991.145535}}.</ref>


==[[संकलक अनुकूलन|कंपाइलर अनुकूलन]] द्वारा संभावित अमान्यकरण==
==[[संकलक अनुकूलन|कंपाइलर अनुकूलन]] द्वारा संभावित अमान्यकरण==
Line 155: Line 155:
और फिर को
और फिर को
: <code>c = 0;</code>
: <code>c = 0;</code>
इस प्रकार त्रुटि क्षतिपूर्ति समाप्त हो जाती है।<ref name=Goldberg91>{{Citation | title=What every computer scientist should know about floating-point arithmetic |first1=David | last1=Goldberg |journal=[[ACM Computing Surveys]] | volume=23 | issue=1 | pages=5–48 | date=March 1991 |doi=10.1145/103162.103163 |s2cid=222008826 |url=http://www.validlab.com/goldberg/paper.pdf }}.</ref> वास्तव में, कई कंपाइलर सरलीकरण में एसोसिएटिविटी नियमों (जो केवल फ़्लोटिंग-पॉइंट अंकगणित में अनुमानित होते हैं) का उपयोग नहीं करते हैं, जब तक कि असुरक्षित अनुकूलन को सक्षम करने वाले कंपाइलर विकल्पों द्वारा स्पष्ट रूप से ऐसा करने का निर्देश नहीं दिया जाता है,<ref>[[GNU Compiler Collection]] manual, version 4.4.3: [https://gcc.gnu.org/onlinedocs/gcc-4.4.3/gcc/Optimize-Options.html 3.10 Options That Control Optimization], ''-fassociative-math'' (Jan. 21, 2010).</ref><ref>''[http://h21007.www2.hp.com/portal/download/files/unprot/Fortran/docs/unix-um/dfumperf.htm Compaq Fortran User Manual for Tru64 UNIX and Linux Alpha Systems] {{Webarchive|url=https://web.archive.org/web/20110607140000/http://h21007.www2.hp.com/portal/download/files/unprot/Fortran/docs/unix-um/dfumperf.htm |date=2011-06-07 }}'', section 5.9.7 Arithmetic Reordering Optimizations (retrieved March 2010).</ref><ref>Börje Lindh, [http://www.sun.com/blueprints/0302/optimize.pdf Application Performance Optimization], ''Sun BluePrints OnLine'' (March 2002).</ref><ref>Eric Fleegal, "[http://msdn.microsoft.com/en-us/library/aa289157%28VS.71%29.aspx Microsoft Visual C++ Floating-Point Optimization]", ''Microsoft Visual Studio Technical Articles''  (June 2004).</ref> चूँकि Intel C++ कंपाइलर एक उदाहरण है जो डिफ़ॉल्ट रूप से साहचर्य-आधारित परिवर्तनों की अनुमति देता है।<ref>Martyn J. Corden, "[http://software.intel.com/en-us/articles/consistency-of-floating-point-results-using-the-intel-compiler/ Consistency of floating-point results using the Intel compiler]", ''Intel technical report'' (Sep. 18, 2009).</ref> C प्रोग्रामिंग लैंग्वेज के मूल K&R C संस्करण ने कंपाइलर को वास्तविक-अंकगणितीय साहचर्यता नियमों के अनुसार फ़्लोटिंग-पॉइंट अभिव्यक्तियों को फिर से व्यवस्थित करने की अनुमति दी, किंतु बाद के [[ANSI C]] मानक ने C को संख्यात्मक अनुप्रयोगों के लिए उत्तम अनुकूल बनाने के लिए पुन: ऑर्डर करने पर रोक लगा दी गई थी (और [[फोरट्रान]] के समान, जो पुन: ऑर्डर करने पर भी रोक लगाता है),<ref>{{cite journal |first=Tom |last=MacDonald |title=संख्यात्मक कंप्यूटिंग के लिए सी|journal=Journal of Supercomputing |volume=5 |issue=1 |pages=31–48 |year=1991 |doi=10.1007/BF00155856|s2cid=27876900 }}</ref> चूँकि वास्तव में कंपाइलर विकल्प पुनः-ऑर्डरिंग को पुनः सक्षम कर सकते हैं, जैसा कि ऊपर बताया गया है।
इस प्रकार त्रुटि क्षतिपूर्ति समाप्त हो जाती है।<ref name=Goldberg91>{{Citation | title=What every computer scientist should know about floating-point arithmetic |first1=David | last1=Goldberg |journal=[[ACM Computing Surveys]] | volume=23 | issue=1 | pages=5–48 | date=March 1991 |doi=10.1145/103162.103163 |s2cid=222008826 |url=http://www.validlab.com/goldberg/paper.pdf }}.</ref> वास्तव में, कई कंपाइलर सरलीकरण में एसोसिएटिविटी नियमों (जो केवल फ़्लोटिंग-पॉइंट अंकगणित में अनुमानित होते हैं) का उपसुम्मेशन नहीं करते हैं, जब तक कि असुरक्षित अनुकूलन को सक्षम करने वाले कंपाइलर विकल्पों द्वारा स्पष्ट रूप से ऐसा करने का निर्देश नहीं दिया जाता है,<ref>[[GNU Compiler Collection]] manual, version 4.4.3: [https://gcc.gnu.org/onlinedocs/gcc-4.4.3/gcc/Optimize-Options.html 3.10 Options That Control Optimization], ''-fassociative-math'' (Jan. 21, 2010).</ref><ref>''[http://h21007.www2.hp.com/portal/download/files/unprot/Fortran/docs/unix-um/dfumperf.htm Compaq Fortran User Manual for Tru64 UNIX and Linux Alpha Systems] {{Webarchive|url=https://web.archive.org/web/20110607140000/http://h21007.www2.hp.com/portal/download/files/unprot/Fortran/docs/unix-um/dfumperf.htm |date=2011-06-07 }}'', section 5.9.7 Arithmetic Reordering Optimizations (retrieved March 2010).</ref><ref>Börje Lindh, [http://www.sun.com/blueprints/0302/optimize.pdf Application Performance Optimization], ''Sun BluePrints OnLine'' (March 2002).</ref><ref>Eric Fleegal, "[http://msdn.microsoft.com/en-us/library/aa289157%28VS.71%29.aspx Microsoft Visual C++ Floating-Point Optimization]", ''Microsoft Visual Studio Technical Articles''  (June 2004).</ref> चूँकि Intel C++ कंपाइलर एक उदाहरण है जो डिफ़ॉल्ट रूप से साहचर्य-आधारित परिवर्तनों की अनुमति देता है।<ref>Martyn J. Corden, "[http://software.intel.com/en-us/articles/consistency-of-floating-point-results-using-the-intel-compiler/ Consistency of floating-point results using the Intel compiler]", ''Intel technical report'' (Sep. 18, 2009).</ref> C प्रोग्रामिंग लैंग्वेज के मूल K&R C संस्करण ने कंपाइलर को वास्तविक-अंकगणितीय साहचर्यता नियमों के अनुसार फ़्लोटिंग-पॉइंट अभिव्यक्तियों को फिर से व्यवस्थित करने की अनुमति दी, किंतु बाद के [[ANSI C]] मानक ने C को संख्यात्मक अनुप्रसुम्मेशनों के लिए उत्तम अनुकूल बनाने के लिए पुन: ऑर्डर करने पर रोक लगा दी गई थी (और [[फोरट्रान]] के समान, जो पुन: ऑर्डर करने पर भी रोक लगाता है),<ref>{{cite journal |first=Tom |last=MacDonald |title=संख्यात्मक कंप्यूटिंग के लिए सी|journal=Journal of Supercomputing |volume=5 |issue=1 |pages=31–48 |year=1991 |doi=10.1007/BF00155856|s2cid=27876900 }}</ref> चूँकि वास्तव में कंपाइलर विकल्प पुनः-ऑर्डरिंग को पुनः सक्षम कर सकते हैं, जैसा कि ऊपर बताया गया है।


ऐसे अनुकूलन को स्थानीय रूप से बाधित करने का एक पोर्टेबल विधि मूल सूत्रीकरण में से एक पंक्ति को दो कथनों में तोड़ना है, और दो मध्यवर्ती उत्पादों को [[अस्थिर चर|अस्थिर]] वेरिएबल बनाना है:<syntaxhighlight>
ऐसे अनुकूलन को स्थानीय रूप से बाधित करने का एक पोर्टेबल विधि मूल सूत्रीकरण में से एक पंक्ति को दो कथनों में तोड़ना है, और दो मध्यवर्ती उत्पादों को [[अस्थिर चर|अस्थिर]] वेरिएबल बनाना है:<syntaxhighlight>
Line 175: Line 175:


==लाइब्रेरी द्वारा समर्थन==
==लाइब्रेरी द्वारा समर्थन==
सामान्य रूप से कंप्यूटर लैंग्वेज में अंतर्निहित योग फ़ंक्शन समान्यत: कोई आश्वासन नहीं देते हैं कि एक विशेष योग एल्गोरिथ्म को नियोजित किया जाएगा, काहन योग तो बिल्कुल भी नहीं रैखिक बीजगणित सबरूटीन्स के लिए बीएलएएस मानक स्पष्ट रूप से प्रदर्शन कारणों से संचालन के किसी विशेष कम्प्यूटेशनल क्रम को अनिवार्य करने से बचाता है,<ref>[http://www.netlib.org/blas/blast-forum/ BLAS Technical Forum], section 2.7 (August 21, 2001), [https://web.archive.org/web/20040410160918/http://www.netlib.org/blas/blast-forum/chapter2.pdf#page=17 Archived on Wayback Machine].</ref> और बीएलएएस कार्यान्वयन समान्यत: कहन सारांश का उपयोग नहीं करते हैं।
सामान्य रूप से कंप्यूटर लैंग्वेज में अंतर्निहित सुम्मेशन फ़ंक्शन समान्यत: कोई आश्वासन नहीं देते हैं कि एक विशेष सुम्मेशन एल्गोरिथ्म को नियोजित किया जाएगा, काहन सुम्मेशन तो बिल्कुल भी नहीं रैखिक बीजगणित सबरूटीन्स के लिए बीएलएएस मानक स्पष्ट रूप से प्रदर्शन कारणों से संचालन के किसी विशेष कम्प्यूटेशनल क्रम को अनिवार्य करने से बचाता है,<ref>[http://www.netlib.org/blas/blast-forum/ BLAS Technical Forum], section 2.7 (August 21, 2001), [https://web.archive.org/web/20040410160918/http://www.netlib.org/blas/blast-forum/chapter2.pdf#page=17 Archived on Wayback Machine].</ref> और बीएलएएस कार्यान्वयन समान्यत: कहन सारांश का उपसुम्मेशन नहीं करते हैं।
   
   
पायथन कंप्यूटर लैंग्वेज की मानक लाइब्रेरी कई आंशिक योगों को ट्रैक करने के लिए शेवचुक एल्गोरिथ्म <ref name="python_fsum"/> का उपयोग करते हुए, बिल्कुल गोल योग के लिए एक [https://docs.python.org/library/math.html#math.fsum fsum] फ़ंक्शन निर्दिष्ट करती है।
पायथन कंप्यूटर लैंग्वेज की मानक लाइब्रेरी कई आंशिक सुम्मेशनों को ट्रैक करने के लिए शेवचुक एल्गोरिथ्म <ref name="python_fsum"/> का उपसुम्मेशन करते हुए, बिल्कुल गोल सुम्मेशन के लिए एक [https://docs.python.org/library/math.html#math.fsum fsum] फ़ंक्शन निर्दिष्ट करती है।


[[जूलिया (प्रोग्रामिंग भाषा)|जूलिया (प्रोग्रामिंग लैंग्वेज)]] लैंग्वेज में, का डिफ़ॉल्ट कार्यान्वयन <code>sum</code> फ़ंक्शन अच्छे प्रदर्शन के साथ उच्च स्पष्टता के लिए जोड़ीवार योग करता है,<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> किंतु एक बाहरी लाइब्रेरी न्यूमैयर के <code>sum_kbn</code> नामित संस्करण का कार्यान्वयन प्रदान करती है ऐसे स्थिति के लिए जब उच्च स्पष्टता की आवश्यकता होती है।<ref>[https://github.com/JuliaMath/KahanSummation.jl KahanSummation library] in Julia.</ref>
[[जूलिया (प्रोग्रामिंग भाषा)|जूलिया (प्रोग्रामिंग लैंग्वेज)]] लैंग्वेज में, का डिफ़ॉल्ट कार्यान्वयन <code>sum</code> फ़ंक्शन अच्छे प्रदर्शन के साथ उच्च स्पष्टता के लिए जोड़ीवार सुम्मेशन करता है,<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> किंतु एक बाहरी लाइब्रेरी न्यूमैयर के <code>sum_kbn</code> नामित संस्करण का कार्यान्वयन प्रदान करती है ऐसे स्थिति के लिए जब उच्च स्पष्टता की आवश्यकता होती है।<ref>[https://github.com/JuliaMath/KahanSummation.jl KahanSummation library] in Julia.</ref>


C शार्प (प्रोग्रामिंग लैंग्वेज) या C# लैंग्वेज में, [https://www.nuget.org/packages/HPCsharp एचपीसीशार्प नुगेट पैकेज] न्यूमैयर वैरिएंट और जोड़ीवार योग को प्रयुक्त करता है: दोनों स्केलर के रूप में, [[SIMD|एसआईएमडी]] प्रोसेसर निर्देशों का उपयोग करके डेटा-समानांतर और समानांतर मल्टी-कोर होते है।<ref>[https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance algorithms].</ref>
C शार्प (प्रोग्रामिंग लैंग्वेज) या C# लैंग्वेज में, [https://www.nuget.org/packages/HPCsharp एचपीसीशार्प नुगेट पैकेज] न्यूमैयर वैरिएंट और जोड़ीवार सुम्मेशन को प्रयुक्त करता है: दोनों स्केलर के रूप में, [[SIMD|एसआईएमडी]] प्रोसेसर निर्देशों का उपसुम्मेशन करके डेटा-समानांतर और समानांतर मल्टी-कोर होते है।<ref>[https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance algorithms].</ref>
==यह भी देखें==
==यह भी देखें==
* [[विचरण की गणना के लिए एल्गोरिदम]], जिसमें स्थिर योग सम्मिलित है
* [[विचरण की गणना के लिए एल्गोरिदम]], जिसमें स्थिर सुम्मेशन सम्मिलित है


==संदर्भ==
==संदर्भ==

Revision as of 12:48, 6 September 2023

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

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

एल्गोरिथ्म का श्रेय विलियम काहन को दिया जाता है;[3] ऐसा लगता है कि इवो बाबुस्का स्वतंत्र रूप से एक समान एल्गोरिथ्म के साथ आए हैं (इसलिए कहन-बाबुस्का सारांश)।[4] समान, पहले की तकनीकें, उदाहरण के लिए, ब्रेसेनहैम की लाइन एल्गोरिदम हैं, जो पूर्णांक संचालन में संचित त्रुटि का ट्रैक रखती हैं (चूँकि पहली बार उसी समय के आसपास प्रलेखित किया गया था)[5]) और डेल्टा-सिग्मा मॉड्यूलेशन है।[6]


एल्गोरिदम

छद्मकोड में, एल्गोरिदम होगा:

function KahanSum(input)
    var sum = 0.0                    // Prepare the accumulator.
    var c = 0.0                      // A running compensation for lost low-order bits.

    for i = 1 to input.length do     // The array input has elements indexed input[1] to input[input.length].
        var y = input[i] - c         // c is zero the first time around.
        var t = sum + y              // Alas, sum is big, y small, so low-order digits of y are lost.
        c = (t - sum) - y            // (t - sum) cancels the high-order part of y; subtracting y recovers negative (low part of y)
        sum = t                      // Algebraically, c should always be zero. Beware overly-aggressive optimizing compilers!
    next i                           // Next time around, the lost low part will be added to y in a fresh attempt.

    return sum


इस एल्गोरिथम को फास्ट2सम एल्गोरिथम का उपसुम्मेशन करने के लिए फिर से लिखा जा सकता है:[7]

function KahanSum2(input)
    var sum = 0.0                    // Prepare the accumulator.
    var c = 0.0                      // A running compensation for lost low-order bits.

    for i = 1 to input.length do     // The array input has elements indexed input[1] to input[input.length].
        var y = input[i] + c         // c is zero the first time around.
        (sum,c) = Fast2Sum(sum,y)    // sum + c is an approximation to the exact sum.
    next i                           // Next time around, the lost low part will be added to y in a fresh attempt.

    return sum


कार्य उदाहरण

यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपसुम्मेशन करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव फ़्लोटिंग-पॉइंट अंकगणित का उपसुम्मेशन कर रहे हैं, sum मान 10000.0 प्राप्त कर लिया है, और अगले दो मान input[i] 3.14159 और 2.71828 हैं। स्पष्ट परिणाम 10005.85987 है, जो 10005.9 के समान है। एक सादे सुम्मेशन के साथ, प्रत्येक आने वाले मूल्य को संरेखित किया जाएगा sum, और कई निम्न-क्रम अंक खो जाएंगे (काट-छांट या पूर्णांकन द्वारा) पूर्णांकन के बाद पहला परिणाम 10003.1 होगा। दूसरा परिणाम राउंडिंग से पहले 10005.81828 और राउंडिंग के बाद 10005.8 होगा। यह सही नहीं है।

यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपसुम्मेशन करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव फ़्लोटिंग-पॉइंट अंकगणित का उपसुम्मेशन कर रहे हैं, सुम्मेशन मान 10000.0 तक पहुंच गया है, और input[i]के अगले दो मान 3.14159 और 2.71828 हैं। स्पष्ट परिणाम 10005.85987 है, जो 10005.9 के समान है। एक सादे sum के साथ, प्रत्येक आने वाले मूल्य को sumके साथ संरेखित किया जाएगा, और कई निम्न-क्रम अंक खो जाएंगे (खंडन या पूर्णांकन द्वारा) पूर्णांकन के बाद पहला परिणाम 10003.1 होगा। दूसरा परिणाम राउंडिंग से पहले 10005.81828 और राउंडिंग के बाद 10005.8 होगा। यह सही नहीं है।

चूँकि क्षतिपूर्ति सुम्मेशन के साथ, हमें 10005.9 का सही पूर्णांकित परिणाम मिलता है।

ये मान लीजिए c प्रारंभिक मान शून्य है.

 y = 3.14159 - 0.00000             y = input[i] - c
  t = 10000.0 + 3.14159
    = 10003.14159                   But only six digits are retained.
    = 10003.1                       Many digits have been lost!
  c = (10003.1 - 10000.0) - 3.14159 This must be evaluated as written! 
    = 3.10000 - 3.14159             The assimilated part of y recovered, vs. the original full y.
    = -0.0415900                    Trailing zeros shown because this is six-digit arithmetic.
sum = 10003.1                       Thus, few digits from input(i) met those of sum.


सुम्मेशन इतना बड़ा है कि केवल इनपुट संख्याओं के उच्च-क्रम अंक ही जमा हो रहे हैं। किंतु अगले चरण पर, c त्रुटि देता है.

  y = 2.71828 - (-0.0415900)        The shortfall from the previous stage gets included.
    = 2.75987                       It is of a size similar to y: most digits meet.
  t = 10003.1 + 2.75987             But few meet the digits of sum.
    = 10005.85987                   And the result is rounded
    = 10005.9                       To six digits.
  c = (10005.9 - 10003.1) - 2.75987 This extracts whatever went in.
    = 2.80000 - 2.75987             In this case, too much.
    = 0.040130                      But no matter, the excess would be subtracted off next time.
sum = 10005.9                       Exact result is 10005.85987, this is correctly rounded to 6 digits.

तो सुम्मेशन दो संचायकों के साथ किया जाता है: sum सुम्मेशन रखता है, और cउन भागो को जमा करता है जो सुम्मेशन में समाहित नहीं होते हैं, जिससे अगली बार (sum ) के निम्न-क्रम वाले भाग को हल किया जा सकता है । इस प्रकार सारांश cमें "गार्ड अंक" के साथ आगे बढ़ता है, जो किसी भी न होने से उत्तम है, किंतु इनपुट की दोगुनी स्पष्टता के साथ गणना करने जितना अच्छा नहीं है। चूँकि केवल गणनाओं की स्पष्टता बढ़ाना सामान्य रूप से व्यावहारिक नहीं है; यदि input पहले से ही दोगुनी परिशुद्धता में है, तो कुछ सिस्टम क्वाडरूपल परिशुद्धता की आपूर्ति करते हैं, और यदि वे करते हैं, तो इनपुट क्वाडरूपल परिशुद्धता में हो सकता है।

स्पष्टता

इसकी स्पष्टता विशेषताओं की सराहना करने के लिए क्षतिपूर्ति सुम्मेशन में त्रुटियों का सावधानीपूर्वक विश्लेषण आवश्यक है। चूँकि यह सरल सुम्मेशन से अधिक स्पष्ट है, फिर भी यह अनिर्धारित सुम्मेशनों के लिए बड़ी सापेक्ष त्रुटियाँ दे सकता है।

मान लीजिए कि कोई मानों का सुम्मेशन है, के लिए स्पष्ट सुम्मेशन है

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

क्षतिपूर्ति के सुम्मेशन के साथ, व्यक्ति को प्राप्त होता है, जहां त्रुटि से घिरा होता है[2]

जहाँ नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (उदाहरण के लिए आईईईई मानक डबल-प्रिसिजन फ़्लोटिंग पॉइंट के लिए )। समान्यत: ब्याज की मात्रा सापेक्ष त्रुटि होती है , जो इसलिए ऊपर से घिरा है

सापेक्ष त्रुटि सीमा के लिए अभिव्यक्ति में, अंश सुम्मेशन समस्या की नियमित संख्या है. अनिवार्य रूप से, नियमित संख्या त्रुटियों के लिए सुम्मेशन समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, तथापि इसकी गणना कैसे की जाती है।[8] निश्चित परिशुद्धता में एक निश्चित एल्गोरिदम द्वारा प्रत्येक (पिछली स्थिर) सुम्मेशन विधि से जुड़ी सापेक्ष त्रुटि (अथार्त वे नहीं जो इच्छित -स्पष्ट अंकगणित का उपसुम्मेशन करते हैं, न ही एल्गोरिदम जिनकी मेमोरी और समय की आवश्यकताएं डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के लिए आनुपातिक है।[2] एक व्यर्थ स्थिति वाली सुम्मेशन समस्या वह होती है जिसमें यह अनुपात बड़ा होता है, और इस स्थिति में क्षतिपूर्ति सुम्मेशन में भी बड़ी सापेक्ष त्रुटि हो सकती है। उदाहरण के लिए, यदि सारांश शून्य माध्य के साथ असंबंधित यादृच्छिक संख्याएं हैं, सुम्मेशन एक यादृच्छिक चलना है, और स्थिति संख्या आनुपातिक रूप से बढ़ेगी . दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को एक परिमित स्थिरांक के रूप में दर्शाती है यदि सभी इनपुट गैर-ऋणात्मक हैं, तो नियमित संख्या 1 है।

एक नियम संख्या को देखते हुए, क्षतिपूर्ति सुम्मेशन की सापेक्ष त्रुटि प्रभावी रूप से से स्वतंत्र है। सिद्धांत रूप में, है जो के साथ रैखिक रूप से बढ़ता है, किंतु वास्तव में यह शब्द प्रभावी रूप से शून्य है: चूंकि अंतिम परिणाम एक परिशुद्धता के लिए गोल होता है जो,की , पद शून्य तक पूर्णांकित होता है, जब तक कि समान्य रूप से या बड़ा न हो।[2] दोहरी परिशुद्धता में, यह लगभग के से मेल खाता है, जो अधिकांश सुम्मेशनों से बहुत बड़ा है। तो, एक निश्चित नियम संख्या के लिए, क्षतिपूर्ति सुम्मेशन की त्रुटियां प्रभावी रूप से होती हैं, जो से स्वतंत्र होती हैं।

इसकी तुलना में, सरल सुम्मेशन के लिए बाध्य सापेक्ष त्रुटि (केवल अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण पर पूर्णांक बनाना) को नियम संख्या से गुणा करने पर बढ़ती है।[2] चूँकि , यह सबसे व्यर्थ स्थिति वाली त्रुटि वास्तव में संभवतः ही कभी देखी जाती है, क्योंकि यह केवल तभी होती है जब पूर्णांकन त्रुटियाँ सभी एक ही दिशा में होती हैं। वास्तव में, इसकी बहुत अधिक संभावना है कि पूर्णांकन त्रुटियों में शून्य माध्य के साथ एक यादृच्छिक चिह्न होता है, जिससे वे एक यादृच्छिक चाल बनाते हैं; इस स्थिति में, सरल सुम्मेशन में एक मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो कि स्थिति संख्या से गुणा करने पर बढ़ती है।[9] चूँकि , यह अभी भी क्षतिपूर्ति के सुम्मेशन से बहुत व्यर्थ है। चूँकि यदि सुम्मेशन को दोगुनी परिशुद्धता में निष्पादित किया जा सकता है, तो को द्वारा प्रतिस्थापित किया जाता है, और मूल परिशुद्धता पर क्षतिपूर्ति सुम्मेशन में शब्द की तुलना में मूल सुम्मेशन में सबसे व्यर्थ स्थिति वाली त्रुटि होती है।

उसी प्रतीक के द्वारा, ऊपर में दिखाई देने वाला सबसे व्यर्थ स्थिति वाला बंधन है जो केवल तब होता है जब सभी गोलाई त्रुटियों का चिह्न समान होता है (और अधिकतम संभव परिमाण के होते हैं)।[2] वास्तव में, यह अधिक संभावना है कि त्रुटियों में यादृच्छिक संकेत होते हैं, जिस स्थिति में में शब्दों को यादृच्छिक चाल से बदल दिया जाता है, उस स्थिति में, शून्य माध्य वाले यादृच्छिक इनपुट के लिए भी, त्रुटि केवल बढ़ती है ( पद को अनदेखा `करते हुए), उसी दर से सुम्मेशन बढ़ता है, जब सापेक्ष त्रुटि की गणना की जाती है तो कारकों को समाप्त कर दिया जाता है। इसलिए, असम्बद्ध रूप से गैर-वातानुकूलित सुम्मेशनों के लिए भी, क्षतिपूर्ति के सुम्मेशन के लिए सापेक्ष त्रुटि अधिकांशतः सबसे व्यर्थ स्थिति के विश्लेषण से बहुत छोटी हो सकती है।

आगे संवर्द्धन

न्यूमैयर [10] कहन एल्गोरिदम का एक उन्नत संस्करण प्रस्तुत किया जाता है, जिसे वह एक उत्तम कहन-बाबुस्का एल्गोरिदम कहते हैं, जो उस स्थिति को भी आवरण करता है जब जोड़ा जाने वाला अगला शब्द चल रहे सुम्मेशन की तुलना में पूर्ण मूल्य में बड़ा होता है, जो बड़े और छोटे की भूमिका को प्रभावी रूप से बदलता है। छद्मकोड में, एल्गोरिथ्म है:

function KahanBabushkaNeumaierSum(input)
    var sum = 0.0
    var c = 0.0                       // A running compensation for lost low-order bits.

    for i = 1 to input.length do
        var t = sum + input[i]
        if |sum| >= |input[i]| then
            c += (sum - t) + input[i] // If sum is bigger, low-order digits of input[i] are lost.
        else
            c += (input[i] - t) + sum // Else low-order digits of sum are lost.
        endif
        sum = t
    next i

    return sum + c                    // Correction only applied once in the very end.

यह संवर्द्धन कहन के एल्गोरिदम में फास्ट2सम के साथ दोबारा लिखे गए फास्ट2सम के प्रतिस्थापन के समान है।

संख्याओं के कई अनुक्रमों के लिए, दोनों एल्गोरिदम सहमत हैं, किंतु पीटर्स के कारण एक सरल उदाहरण [11] दिखाता है कि वे कैसे भिन्न हो सकते हैं। संक्षेप के लिए दोहरी परिशुद्धता में, काहन का एल्गोरिदम 0.0 उत्पन्न करता है, जबकि न्यूमैयर का एल्गोरिदम सही मान 2.0 उत्पन्न करता है।

उत्तम स्पष्टता के उच्च-क्रम संशोधन भी संभव हैं। उदाहरण के लिए, क्लेन द्वारा सुझाया गया एक संस्करण,[12] जिसे उन्होंने दूसरे क्रम का पुनरावृत्त कहन-बाबुस्का एल्गोरिदम कहा। छद्मकोड में, एल्गोरिथ्म है:

function KahanBabushkaKleinSum(input)
    var sum = 0.0
    var cs  = 0.0
    var ccs = 0.0
    var c   = 0.0
    var cc  = 0.0

    for i = 1 to input.length do
        var t = sum + input[i]
        if |sum| >= |input[i]| then
            c = (sum - t) + input[i]
        else
            c = (input[i] - t) + sum
        endif
        sum = t
        t = cs + c
        if |cs| >= |c| then
            cc = (cs - t) + c
        else
            cc = (c - t) + cs
        endif
        cs = t
        ccs = ccs + cc
    end loop 

    return sum + cs + ccs

विकल्प

चूँकि काहन का एल्गोरिदम n संख्याओं के सुम्मेशन के लिए त्रुटि वृद्धि को प्राप्त करता है, केवल कुछ व्यर्थ वृद्धि को जोड़ीदार सुम्मेशन द्वारा प्राप्त किया जा सकता है: कोई संख्याओं के सेट को दो भागो में पुनरावर्ती रूप से विभाजित करता है, प्रत्येक आधे का सुम्मेशन करता है, और फिर जोड़ता है दो मान [2] इसका लाभ यह है कि इसमें सरल सुम्मेशन के समान अंकगणितीय परिचालन की आवश्यकता होती है (कहान के एल्गोरिदम के विपरीत, जिसके लिए चार गुना अंकगणित की आवश्यकता होती है और चार गुना सरल सुम्मेशन की विलंबता होती है) और समानांतर में गणना की जा सकती है। पुनरावृत्ति का आधार स्थिति सैद्धांतिक रूप से केवल एक (या शून्य) संख्याओं का सुम्मेशन हो सकता है, किंतु पुनरावृत्ति के ओवरहेड को परिशोधित करने के लिए, समान्यत: एक बड़े आधार स्थिति का उपसुम्मेशन किया जाएगा। जोड़ीवार सुम्मेशन के समतुल्य का उपसुम्मेशन कई तेज़ फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम में किया जाता है और यह उन एफएफटी में राउंडऑफ त्रुटियों के लॉगरिदमिक विकास के लिए उत्तरदाई है।[13] वास्तव में, यादृच्छिक संकेतों की राउंडऑफ त्रुटियों के साथ, जोड़ीवार सुम्मेशन की मूल माध्य वर्ग त्रुटियां वास्तव में के रूप में बढ़ती हैं।[9]

एक अन्य विकल्प इच्छित -स्पष्ट अंकगणित का उपसुम्मेशन करना है, जिसे सैद्धांतिक रूप से बहुत अधिक कम्प्यूटेशनल प्रयास की निवेश के साथ पूर्णांकित करने की आवश्यकता नहीं है। इच्छित परिशुद्धता का उपसुम्मेशन करके बिल्कुल गोल मान निष्पादित करने का एक विधि कई फ़्लोटिंग-पॉइंट घटकों का उपसुम्मेशन करके अनुकूली रूप से विस्तार करना है। यह उन सामान्य स्थिति में कम्प्यूटेशनल निवेश को कम कर देगा जहां उच्च परिशुद्धता की आवश्यकता नहीं है।[14][11]

कंपाइलर अनुकूलन द्वारा संभावित अमान्यकरण

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

t = sum + y;
c = (t - sum) - y;

को

c = ((sum + y) - sum) - y;

और फिर को

c = 0;

इस प्रकार त्रुटि क्षतिपूर्ति समाप्त हो जाती है।[15] वास्तव में, कई कंपाइलर सरलीकरण में एसोसिएटिविटी नियमों (जो केवल फ़्लोटिंग-पॉइंट अंकगणित में अनुमानित होते हैं) का उपसुम्मेशन नहीं करते हैं, जब तक कि असुरक्षित अनुकूलन को सक्षम करने वाले कंपाइलर विकल्पों द्वारा स्पष्ट रूप से ऐसा करने का निर्देश नहीं दिया जाता है,[16][17][18][19] चूँकि Intel C++ कंपाइलर एक उदाहरण है जो डिफ़ॉल्ट रूप से साहचर्य-आधारित परिवर्तनों की अनुमति देता है।[20] C प्रोग्रामिंग लैंग्वेज के मूल K&R C संस्करण ने कंपाइलर को वास्तविक-अंकगणितीय साहचर्यता नियमों के अनुसार फ़्लोटिंग-पॉइंट अभिव्यक्तियों को फिर से व्यवस्थित करने की अनुमति दी, किंतु बाद के ANSI C मानक ने C को संख्यात्मक अनुप्रसुम्मेशनों के लिए उत्तम अनुकूल बनाने के लिए पुन: ऑर्डर करने पर रोक लगा दी गई थी (और फोरट्रान के समान, जो पुन: ऑर्डर करने पर भी रोक लगाता है),[21] चूँकि वास्तव में कंपाइलर विकल्प पुनः-ऑर्डरिंग को पुनः सक्षम कर सकते हैं, जैसा कि ऊपर बताया गया है।

ऐसे अनुकूलन को स्थानीय रूप से बाधित करने का एक पोर्टेबल विधि मूल सूत्रीकरण में से एक पंक्ति को दो कथनों में तोड़ना है, और दो मध्यवर्ती उत्पादों को अस्थिर वेरिएबल बनाना है:

function KahanSum(input)
    var sum = 0.0
    var c = 0.0

    for i = 1 to input.length do
        var y = input[i] - c
        volatile var t = sum + y
        volatile var z = t - sum
        c = z - y
        sum = t
    next i

    return sum


लाइब्रेरी द्वारा समर्थन

सामान्य रूप से कंप्यूटर लैंग्वेज में अंतर्निहित सुम्मेशन फ़ंक्शन समान्यत: कोई आश्वासन नहीं देते हैं कि एक विशेष सुम्मेशन एल्गोरिथ्म को नियोजित किया जाएगा, काहन सुम्मेशन तो बिल्कुल भी नहीं रैखिक बीजगणित सबरूटीन्स के लिए बीएलएएस मानक स्पष्ट रूप से प्रदर्शन कारणों से संचालन के किसी विशेष कम्प्यूटेशनल क्रम को अनिवार्य करने से बचाता है,[22] और बीएलएएस कार्यान्वयन समान्यत: कहन सारांश का उपसुम्मेशन नहीं करते हैं।

पायथन कंप्यूटर लैंग्वेज की मानक लाइब्रेरी कई आंशिक सुम्मेशनों को ट्रैक करने के लिए शेवचुक एल्गोरिथ्म [11] का उपसुम्मेशन करते हुए, बिल्कुल गोल सुम्मेशन के लिए एक fsum फ़ंक्शन निर्दिष्ट करती है।

जूलिया (प्रोग्रामिंग लैंग्वेज) लैंग्वेज में, का डिफ़ॉल्ट कार्यान्वयन sum फ़ंक्शन अच्छे प्रदर्शन के साथ उच्च स्पष्टता के लिए जोड़ीवार सुम्मेशन करता है,[23] किंतु एक बाहरी लाइब्रेरी न्यूमैयर के sum_kbn नामित संस्करण का कार्यान्वयन प्रदान करती है ऐसे स्थिति के लिए जब उच्च स्पष्टता की आवश्यकता होती है।[24]

C शार्प (प्रोग्रामिंग लैंग्वेज) या C# लैंग्वेज में, एचपीसीशार्प नुगेट पैकेज न्यूमैयर वैरिएंट और जोड़ीवार सुम्मेशन को प्रयुक्त करता है: दोनों स्केलर के रूप में, एसआईएमडी प्रोसेसर निर्देशों का उपसुम्मेशन करके डेटा-समानांतर और समानांतर मल्टी-कोर होते है।[25]

यह भी देखें

संदर्भ

  1. Strictly, there exist other variants of compensated summation as well: see Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 110–123. ISBN 978-0-89871-521-7.
  2. 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Higham, Nicholas J. (1993), "The accuracy of floating point summation" (PDF), SIAM Journal on Scientific Computing, 14 (4): 783–799, Bibcode:1993SJSC...14..783H, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050, S2CID 14071038.
  3. Kahan, William (January 1965), "Further remarks on reducing truncation errors" (PDF), Communications of the ACM, 8 (1): 40, doi:10.1145/363707.363723, S2CID 22584810, archived from the original (PDF) on 9 February 2018.
  4. Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)
  5. Bresenham, Jack E. (January 1965). "डिजिटल प्लॉटर के कंप्यूटर नियंत्रण के लिए एल्गोरिदम" (PDF). IBM Systems Journal. 4 (1): 25–30. doi:10.1147/sj.41.0025. S2CID 41898371.
  6. Inose, H.; Yasuda, Y.; Murakami, J. (September 1962). "A Telemetering System by Code Manipulation – ΔΣ Modulation". IRE Transactions on Space Electronics and Telemetry. SET-8: 204–209. doi:10.1109/IRET-SET.1962.5008839. S2CID 51647729.
  7. Muller, Jean-Michel; Brunie, Nicolas; de Dinechin, Florent; Jeannerod, Claude-Pierre; Joldes, Mioara; Lefèvre, Vincent; Melquiond, Guillaume; Revol, Nathalie; Torres, Serge (2018) [2010]. फ़्लोटिंग-पॉइंट अंकगणित की पुस्तिका (2 ed.). Birkhäuser. p. 179. doi:10.1007/978-3-319-76526-6. ISBN 978-3-319-76525-9. LCCN 2018935254.
  8. Trefethen, Lloyd N.; Bau, David (1997). संख्यात्मक रैखिक बीजगणित. Philadelphia: SIAM. ISBN 978-0-89871-361-9.
  9. 9.0 9.1 Manfred Tasche and Hansmartin Zeuner, Handbook of Analytic-Computational Methods in Applied Mathematics, Boca Raton, FL: CRC Press, 2000.
  10. Neumaier, A. (1974). "परिमित योगों के योग के लिए कुछ विधियों का पूर्णांकन त्रुटि विश्लेषण" [Rounding Error Analysis of Some Methods for Summing Finite Sums] (PDF). Zeitschrift für Angewandte Mathematik und Mechanik (in Deutsch). 54 (1): 39–51. Bibcode:1974ZaMM...54...39N. doi:10.1002/zamm.19740540106.
  11. 11.0 11.1 11.2 रेमंड हेटिंगर, रेसिपी 393090: बाइनरी फ़्लोटिंग पॉइंट योग पूर्ण परिशुद्धता के लिए सटीक, शेवचुक (1997) लेख (28 मार्च 2005) से एल्गोरिदम का पायथन कार्यान्वयन। रेफरी>आर. किरचनर, उलरिच डब्ल्यू. कुलिश, वेक्टर प्रोसेसर के लिए सटीक अंकगणित, जर्नल ऑफ़ पैरेलल एंड डिस्ट्रिब्यूटेड कंप्यूटिंग 5 (1988) 250-270। एक हार्डवेयर कार्यान्वयन का वर्णन मुलर, रब और रूलिंग द्वारा किया गया था। रेफरी>एम. मुलर, सी. रब, डब्ल्यू. रूलिंग [1], फ्लोटिंग-पॉइंट संख्याओं का सटीक संचय, कंप्यूटर अंकगणित पर 10वीं IEEE संगोष्ठी की कार्यवाही (जून 1991), doi:10.1109/ARITH.1991.145535.
  12. A., Klein (2006). "A generalized Kahan–Babuška-Summation-Algorithm". Computing. Springer-Verlag. 76 (3–4): 279–293. doi:10.1007/s00607-005-0139-x. S2CID 4561254.
  13. S. G. Johnson and M. Frigo, "Implementing FFTs in practice, in Fast Fourier Transforms, edited by C. Sidney Burrus(2008).
  14. Jonathan R. Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete and Computational Geometry, vol. 18, pp. 305–363 (October 1997).
  15. Goldberg, David (March 1991), "What every computer scientist should know about floating-point arithmetic" (PDF), ACM Computing Surveys, 23 (1): 5–48, doi:10.1145/103162.103163, S2CID 222008826.
  16. GNU Compiler Collection manual, version 4.4.3: 3.10 Options That Control Optimization, -fassociative-math (Jan. 21, 2010).
  17. Compaq Fortran User Manual for Tru64 UNIX and Linux Alpha Systems Archived 2011-06-07 at the Wayback Machine, section 5.9.7 Arithmetic Reordering Optimizations (retrieved March 2010).
  18. Börje Lindh, Application Performance Optimization, Sun BluePrints OnLine (March 2002).
  19. Eric Fleegal, "Microsoft Visual C++ Floating-Point Optimization", Microsoft Visual Studio Technical Articles (June 2004).
  20. Martyn J. Corden, "Consistency of floating-point results using the Intel compiler", Intel technical report (Sep. 18, 2009).
  21. MacDonald, Tom (1991). "संख्यात्मक कंप्यूटिंग के लिए सी". Journal of Supercomputing. 5 (1): 31–48. doi:10.1007/BF00155856. S2CID 27876900.
  22. BLAS Technical Forum, section 2.7 (August 21, 2001), Archived on Wayback Machine.
  23. RFC: use pairwise summation for sum, cumsum, and cumprod, github.com/JuliaLang/julia pull request #4039 (August 2013).
  24. KahanSummation library in Julia.
  25. HPCsharp nuget package of high performance algorithms.

बाहरी संबंध