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

From Vigyanwiki
(Created page with "संख्यात्मक विश्लेषण में, कहन योग एल्गोरिथ्म, जिसे क्षतिपूर्ति य...")
 
No edit summary
 
(11 intermediate revisions by 5 users not shown)
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> मुआवजे के योग के साथ, पर्याप्त उच्च परिशुद्धता के साथ मुआवजा चर का उपयोग करने से सबसे खराब स्थिति वाली त्रुटि प्रभावी रूप से स्वतंत्र होती है <math>n</math>, इसलिए बड़ी संख्या में मानों को एक त्रुटि के साथ संक्षेपित किया जा सकता है जो केवल परिणाम की फ़्लोटिंग-पॉइंट [[परिशुद्धता (अंकगणित)]] पर निर्भर करता है।<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>




==एल्गोरिदम==
==एल्गोरिदम==
[[ छद्मकोड ]] में, एल्गोरिदम होगा:
[[ छद्मकोड | छद्मकोड]] में, एल्गोरिदम होगा:<syntaxhighlight>
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
</syntaxhighlight>


फ़ंक्शन KahanSum(इनपुट)
    var योग = 0.0 // संचायक तैयार करें।
    var c = 0.0 // खोए हुए कम-ऑर्डर बिट्स के लिए एक चालू मुआवजा।
    i = 1 से इनपुट.लेंथ के लिए // सरणी ''इनपुट'' में तत्वों को इनपुट[1] से इनपुट[इनपुट.लेंथ] तक अनुक्रमित किया गया है।
        var y = इनपुट[i] - c // ''c'' पहली बार शून्य है।
        var t = sum + y // अफ़सोस, ''sum'' बड़ा है, ''y'' छोटा, इसलिए ''y'' के निम्न-क्रम अंक खो गए हैं।
        c = (t - sum) - y // ''(t - sum)'' ''y'' के उच्च-क्रम वाले भाग को रद्द करता है; ''y'' घटाने पर ऋणात्मक (''y'' का निचला भाग) वापस आ जाता है
        योग = टी // बीजगणितीय रूप से, ''सी'' हमेशा शून्य होना चाहिए। अत्यधिक आक्रामक अनुकूलन कंपाइलरों से सावधान रहें!
    अगला i // अगली बार, खोया हुआ निचला हिस्सा एक नए प्रयास में ''y'' में जोड़ा जाएगा।
    वापसी राशि


इस एल्गोरिथम को [[2Sum]] एल्गोरिथम का उपयोग करने के लिए फिर से लिखा जा सकता है:<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>
इस एल्गोरिथम को फास्ट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>
फ़ंक्शन KahanSum2(इनपुट)
function KahanSum2(input)
    var योग = 0.0 // संचायक तैयार करें।
    var sum = 0.0                   // Prepare the accumulator.
    var c = 0.0 // खोए हुए कम-ऑर्डर बिट्स के लिए एक चालू मुआवजा।
    var c = 0.0                     // A running compensation for lost low-order bits.
 
    i = 1 से इनपुट.लेंथ के लिए // सरणी ''इनपुट'' में तत्वों को इनपुट[1] से इनपुट[इनपुट.लेंथ] तक अनुक्रमित किया गया है।
    for i = 1 to input.length do    // The array input has elements indexed input[1] to input[input.length].
        var y = इनपुट[i] + c // ''c'' पहली बार शून्य है।
        var y = input[i] + c         // c is zero the first time around.
        (sum,c) = Fast2Sum(sum,y) // ''sum'' + ''c'' सटीक योग का एक अनुमान है।
        (sum,c) = Fast2Sum(sum,y)   // sum + c is an approximation to the exact sum.
    अगला i // अगली बार, खोया हुआ निचला हिस्सा एक नए प्रयास में ''y'' में जोड़ा जाएगा।
    next i                           // Next time around, the lost low part will be added to y in a fresh attempt.
 
    वापसी राशि
    return sum
</syntaxhighlight>
 


===कार्य उदाहरण===
===कार्य उदाहरण===
यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर आमतौर पर बाइनरी अंकगणित का उपयोग करते हैं, लेकिन चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव [[फ़्लोटिंग-पॉइंट अंकगणित]] का उपयोग कर रहे हैं, <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 होगा। यह सही नहीं है।


हालाँकि, क्षतिपूर्ति योग के साथ, हमें 10005.9 का सही पूर्णांकित परिणाम मिलता है।
यह उदाहरण दशमलव में दिया जायेगा. कंप्यूटर समान्यत: बाइनरी अंकगणित का उपसुम्मेशन करते हैं, किंतु चित्रित सिद्धांत वही है। मान लीजिए कि हम छह अंकों वाले दशमलव फ़्लोटिंग-पॉइंट अंकगणित का उपसुम्मेशन कर रहे हैं, सुम्मेशन मान 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 होगा। यह सही नहीं है।


ये मान लीजिए <code>c</code> प्रारंभिक मान शून्य है.
चूँकि क्षतिपूर्ति सुम्मेशन के साथ, हमें 10005.9 का सही पूर्णांकित परिणाम मिलता है।
  y = 3.14159 - 0.00000 y = इनपुट[i] - c
  टी = 10000.0 + 3.14159
    = 10003.14159 लेकिन केवल छह अंक ही बरकरार रखे गए हैं।
    =10003.1 कई अंक खो गए हैं!
  सी = (10003.1 - 10000.0) - 3.14159 इस 'आवश्यक' का मूल्यांकन लिखित रूप में किया जाना चाहिए!
    = 3.10000 - 3.14159 y का आत्मसात किया हुआ भाग पुनः प्राप्त हुआ, बनाम मूल पूर्ण y।
    = -0.0415900 अनुगामी शून्य दिखाए गए हैं क्योंकि यह छह अंकों का अंकगणित है।
योग = 10003.1 इस प्रकार, इनपुट (i) से कुछ अंक योग के बराबर थे।


योग इतना बड़ा है कि केवल इनपुट संख्याओं के उच्च-क्रम अंक ही जमा हो रहे हैं। लेकिन अगले कदम पर, <code>c</code> त्रुटि देता है.
ये मान लीजिए <code>c</code> प्रारंभिक मान शून्य है.<syntaxhighlight>
  y = 2.71828 - (-0.0415900) पिछले चरण की कमी शामिल हो जाती है।
y = 3.14159 - 0.00000            y = input[i] - c
    = 2.75987 इसका आकार y के समान है: अधिकांश अंक मिलते हैं।
  t = 10000.0 + 3.14159
  t = 10003.1 + 2.75987 लेकिन कुछ ही लोग योग के अंकों को पूरा करते हैं।
    = 10003.14159                  But only six digits are retained.
    = 10005.85987 और परिणाम पूर्णांकित है
    = 10003.1                      Many digits have been lost!
    = 10005.9 छह अंक तक.
  c = (10003.1 - 10000.0) - 3.14159 This must be evaluated as written!
  सी = (10005.9 - 10003.1) - 2.75987 यह जो कुछ भी अंदर गया उसे निकाल देता है।
    = 3.10000 - 3.14159            The assimilated part of y recovered, vs. the original full y.
    = 2.80000 - 2.75987 इस मामले में, बहुत अधिक।
    = -0.0415900                    Trailing zeros shown because this is six-digit arithmetic.
    = 0.040130 लेकिन कोई बात नहीं, अगली बार अतिरिक्त घटा दिया जाएगा।
sum = 10003.1                      Thus, few digits from input(i) met those of sum.
योग = 10005.9 सटीक परिणाम 10005.85987 है, इसे 6 अंकों में सही ढंग से पूर्णांकित किया गया है।
</syntaxhighlight>


तो योग दो संचायकों के साथ किया जाता है: <code>sum</code> योग रखता है, और <code>c</code> उन भागों को एकत्रित करता है जिन्हें आत्मसात नहीं किया गया है <code>sum</code>, निम्न-क्रम वाले भाग को कुहनी मारने के लिए <code>sum</code> अगली बार. इस प्रकार योग गार्ड अंकों के साथ आगे बढ़ता है <code>c</code>, जो किसी के न होने से बेहतर है, लेकिन इनपुट की दोगुनी सटीकता के साथ गणना करने जितना अच्छा नहीं है। हालाँकि, केवल गणनाओं की सटीकता बढ़ाना सामान्य रूप से व्यावहारिक नहीं है; अगर <code>input</code> पहले से ही दोहरी परिशुद्धता में है, कुछ सिस्टम [[चौगुनी परिशुद्धता]] की आपूर्ति करते हैं, और यदि उन्होंने किया, <code>input</code> तब यह चौगुनी परिशुद्धता में हो सकता है।
सुम्मेशन इतना बड़ा है कि केवल इनपुट संख्याओं के उच्च-क्रम अंक ही जमा हो रहे हैं। किंतु अगले चरण पर, <code>c</code> त्रुटि देता है.<syntaxhighlight>
  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.
</syntaxhighlight>
 
तो सुम्मेशन दो संचायकों के साथ किया जाता है: <code>sum</code> सुम्मेशन रखता है, और <code>c</code>उन भागो को जमा करता है जो सुम्मेशन में समाहित नहीं होते हैं, जिससे अगली बार (<code>sum</code> ) के निम्न-क्रम वाले भाग को हल किया जा सकता है । इस प्रकार सारांश <code>c</code>में "गार्ड अंक" के साथ आगे बढ़ता है, जो किसी भी न होने से उत्तम है, किंतु इनपुट की दोगुनी स्पष्टता के साथ गणना करने जितना अच्छा नहीं है। चूँकि केवल गणनाओं की स्पष्टता बढ़ाना सामान्य रूप से व्यावहारिक नहीं है; यदि <code>input</code> पहले से ही दोगुनी परिशुद्धता में है, तो कुछ सिस्टम क्वाडरूपल परिशुद्धता की आपूर्ति करते हैं, और यदि वे करते हैं, तो इनपुट क्वाडरूपल परिशुद्धता में हो सकता है।


==सटीकता==
==स्पष्टता ==
{{Confusing|1=section|reason=this section uses ε, while there exist [[Machine epsilon#Variant definitions|two conflicting definitions]]. I suggest to use '''u''' instead, whose definition is rather standard|date=December 2021}}
इसकी स्पष्टता विशेषताओं की सराहना करने के लिए क्षतिपूर्ति सुम्मेशन में त्रुटियों का सावधानीपूर्वक विश्लेषण आवश्यक है। चूँकि यह सरल सुम्मेशन से अधिक स्पष्ट है, फिर भी यह अनिर्धारित सुम्मेशनों के लिए बड़ी सापेक्ष त्रुटियाँ दे सकता है।
इसकी सटीकता विशेषताओं की सराहना करने के लिए क्षतिपूर्ति योग में त्रुटियों का सावधानीपूर्वक विश्लेषण आवश्यक है। हालाँकि यह सरल योग से अधिक सटीक है, फिर भी यह अनिर्धारित योगों के लिए बड़ी सापेक्ष त्रुटियाँ दे सकता है।


मान लीजिए कि कोई योग कर रहा है <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>|E_n| \le \big[2\varepsilon + O(n\varepsilon^2)\big] \sum_{i=1}^n |x_i|,</math>
क्षतिपूर्ति के सुम्मेशन के साथ, व्यक्ति को <math>S_n + E_n</math> प्राप्त होता है, जहां त्रुटि <math>E_n</math> से घिरा होता है<ref name=Higham93/>  
कहाँ <math>\varepsilon</math> नियोजित किए जा रहे अंकगणित की [[मशीन परिशुद्धता]] है (उदा. <math>\varepsilon \approx 10^{-16}</math> आईईईई मानक [[ दोहरी सुनिश्चितता ]] फ़्लोटिंग पॉइंट के लिए)। आमतौर पर, ब्याज की मात्रा सापेक्ष त्रुटि होती है <math>|E_n|/|S_n|</math>, जो इसलिए ऊपर से घिरा हुआ है
 
<math>|E_n| \le \big[2\varepsilon + O(n\varepsilon^2)\big] \sum_{i=1}^n |x_i|,</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> मोटे तौर पर है <math>1 / \varepsilon</math> या बड़ा.<ref name=Higham93/> दोहरी परिशुद्धता में, यह एक से मेल खाता है <math>n</math> मोटे तौर पर <math>10^{16}</math>, अधिकांश योगों से बहुत बड़ा। इसलिए, एक निश्चित स्थिति संख्या के लिए, क्षतिपूर्ति योग की त्रुटियां प्रभावी रूप से होती हैं <math>O (\varepsilon)</math>, स्वतंत्र <math>n</math>.
एक नियम संख्या को देखते हुए, क्षतिपूर्ति सुम्मेशन की सापेक्ष त्रुटि प्रभावी रूप से <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>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>\varepsilon</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> कहन एल्गोरिदम का एक उन्नत संस्करण पेश किया, जिसे वह एक बेहतर कहन-बाबुस्का एल्गोरिदम कहते हैं, जो उस मामले को भी कवर करता है जब जोड़ा जाने वाला अगला शब्द चल रहे योग की तुलना में पूर्ण मूल्य में बड़ा होता है, जो बड़े और छोटे की भूमिका को प्रभावी ढंग से बदलता है। छद्मकोड में, एल्गोरिथ्म है:
न्यूमैयर <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)
    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.
</syntaxhighlight>
   
   
फ़ंक्शन KahanBabushkaNeumaierSum(इनपुट)
    वर योग = 0.0
    var c = 0.0 // खोए हुए कम-ऑर्डर बिट्स के लिए एक चालू मुआवजा।
    i = 1 के लिए इनपुट.लेंथ करें
        var t = योग + इनपुट[i]
        यदि |योग| >= |इनपुट[i]| तब
            c += (sum - t) + इनपुट[i] // यदि ''योग'' बड़ा है, तो ''इनपुट[i]'' के निम्न-क्रम अंक खो जाते हैं।
        अन्य
            c += (इनपुट[i] - t) + योग // अन्यथा ''योग'' के निम्न-क्रम अंक खो जाते हैं।
        अगर अंत
        योग = टी
    अगला मैं
    वापसी योग + सी // सुधार अंत में केवल एक बार लागू होता है।
यह संवर्द्धन कहन के एल्गोरिदम में फास्ट2सम के साथ दोबारा लिखे गए फास्ट2सम के प्रतिस्थापन के समान है।
यह संवर्द्धन कहन के एल्गोरिदम में फास्ट2सम के साथ दोबारा लिखे गए फास्ट2सम के प्रतिस्थापन के समान है।


संख्याओं के कई अनुक्रमों के लिए, दोनों एल्गोरिदम सहमत हैं, लेकिन पीटर्स के कारण एक सरल उदाहरण<ref name="python_fsum" />दिखाता है कि वे कैसे भिन्न हो सकते हैं। संक्षेप के लिए <math>[1.0, +10^{100}, 1.0, -10^{100}]</math> दोहरी परिशुद्धता में, काहन का एल्गोरिदम 0.0 उत्पन्न करता है, जबकि न्यूमैयर का एल्गोरिदम सही मान 2.0 उत्पन्न करता है।
संख्याओं के कई अनुक्रमों के लिए, दोनों एल्गोरिदम सहमत हैं, किंतु पीटर्स के कारण एक सरल उदाहरण <ref name="python_fsum" /> दिखाता है कि वे कैसे भिन्न हो सकते हैं। संक्षेप के लिए <math>[1.0, +10^{100}, 1.0, -10^{100}]</math> दोहरी परिशुद्धता में, काहन का एल्गोरिदम 0.0 उत्पन्न करता है, जबकि न्यूमैयर का एल्गोरिदम सही मान 2.0 उत्पन्न करता है।


बेहतर सटीकता के उच्च-क्रम संशोधन भी संभव हैं। उदाहरण के लिए, क्लेन द्वारा सुझाया गया एक संस्करण,<ref>{{Cite journal |last=A. |first=Klein |date=2006 |title=A generalized Kahan–Babuška-Summation-Algorithm |journal=Computing |volume=76 |issue=3–4 |pages=279–293 |publisher=Springer-Verlag|doi=10.1007/s00607-005-0139-x |s2cid=4561254 }}</ref> जिसे उन्होंने दूसरे क्रम का पुनरावृत्त कहन-बाबुस्का एल्गोरिदम कहा। छद्मकोड में, एल्गोरिथ्म है:
उत्तम स्पष्टता के उच्च-क्रम संशोधन भी संभव हैं। उदाहरण के लिए, क्लेन द्वारा सुझाया गया एक संस्करण,<ref>{{Cite journal |last=A. |first=Klein |date=2006 |title=A generalized Kahan–Babuška-Summation-Algorithm |journal=Computing |volume=76 |issue=3–4 |pages=279–293 |publisher=Springer-Verlag|doi=10.1007/s00607-005-0139-x |s2cid=4561254 }}</ref> जिसे उन्होंने दूसरे क्रम का पुनरावृत्त कहन-बाबुस्का एल्गोरिदम कहा। छद्मकोड में, एल्गोरिथ्म है:<syntaxhighlight>
function KahanBabushkaKleinSum(input)
    var sum = 0.0
    var cs  = 0.0
    var ccs = 0.0
    var c  = 0.0
    var cc  = 0.0


फ़ंक्शन KahanBabushkaKleinSum(इनपुट)
    for i = 1 to input.length do
    वर योग = 0.0
        var t = sum + input[i]
    वर सीएस = 0.0
        if |sum| >= |input[i]| then
    वर सीसीएस = 0.0
            c = (sum - t) + input[i]
    वर सी = 0.0
        else
    वर सीसी = 0.0
            c = (input[i] - t) + sum
        endif
    i = 1 के लिए इनपुट.लेंथ करें
        sum = t
        var t = योग + इनपुट[i]
        t = cs + c
        यदि |योग| >= |इनपुट[i]| तब
        if |cs| >= |c| then
            सी = (योग - टी) + इनपुट[i]
            cc = (cs - t) + c
        अन्य
        else
            सी = (इनपुट[i] - टी) + योग
            cc = (c - t) + cs
        अगर अंत
        endif
        योग = टी
        cs = t
        टी = सीएस + सी
        ccs = ccs + cc
        यदि |सीएस| >= |सी| तब
    end loop
            सीसी = (सीएस - टी) + सी
        अन्य
            सीसी = (सी - टी) + सीएस
        अगर अंत
        सीएस = टी
        सीसीएस = सीसीएस + सीसी
    अंत पाश
    वापसी योग + सीएस + सीसीएस


    return sum + cs + ccs
</syntaxhighlight>
==विकल्प==
==विकल्प==
हालाँकि कहन का एल्गोरिदम हासिल करता है <math>O(1)</math> n संख्याओं के योग के लिए त्रुटि वृद्धि, केवल थोड़ी खराब <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>


==[[संकलक अनुकूलन]] द्वारा संभावित अमान्यकरण==
==[[संकलक अनुकूलन|कंपाइलर अनुकूलन]] द्वारा संभावित अमान्यकरण==
सिद्धांत रूप में, एक पर्याप्त रूप से आक्रामक कंपाइलर अनुकूलन कहन सारांश की प्रभावशीलता को नष्ट कर सकता है: उदाहरण के लिए, यदि कंपाइलर ने वास्तविक अंकगणित के साहचर्य नियमों के अनुसार अभिव्यक्तियों को सरल बनाया है, तो यह अनुक्रम में दूसरे चरण को सरल बना सकता है
सिद्धांत रूप में, एक पर्याप्त रूप से आक्रामक कंपाइलर अनुकूलन कहन सारांश की प्रभावशीलता को नष्ट कर सकता है: उदाहरण के लिए, यदि कंपाइलर ने वास्तविक अंकगणित के साहचर्य नियमों के अनुसार अभिव्यक्तियों को सरल बनाया है, तो यह अनुक्रम में दूसरे चरण को सरल बना सकता है
: <code>t = sum + y;</code>
: <code>t = sum + y;</code>
Line 144: 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>
फ़ंक्शन KahanSum(इनपुट)
function KahanSum(input)
    वर योग = 0.0
    var sum = 0.0
    वर सी = 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
</syntaxhighlight>
   
   
    i = 1 के लिए इनपुट.लेंथ करें
        var y = इनपुट[i] - c
        अस्थिर var t = योग + y
        अस्थिर var z = t - योग
        सी = जेड - वाई
        योग = टी
    अगला मैं
    वापसी राशि


==पुस्तकालयों द्वारा समर्थन==
==लाइब्रेरी द्वारा समर्थन==
सामान्य तौर पर, कंप्यूटर भाषाओं में अंतर्निहित योग फ़ंक्शन आम तौर पर कोई गारंटी नहीं देते हैं कि एक विशेष योग एल्गोरिथ्म को नियोजित किया जाएगा, काहन योग तो बिल्कुल भी नहीं।{{Citation needed|date=February 2010}} रैखिक बीजगणित सबरूटीन्स के लिए बीएलएएस मानक स्पष्ट रूप से प्रदर्शन कारणों से संचालन के किसी विशेष कम्प्यूटेशनल क्रम को अनिवार्य करने से बचाता है,<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> और बीएलएएस कार्यान्वयन समान्यत: कहन सारांश का उपसुम्मेशन नहीं करते हैं।
   
   
[[पायथन (प्रोग्रामिंग भाषा)]] कंप्यूटर भाषा की मानक लाइब्रेरी, [[जोनाथन शेवचुक]] एल्गोरिथ्म का उपयोग करते हुए, बिल्कुल गोल योग के लिए एक [https://docs.python.org/library/math.html#math.fsum fsum] फ़ंक्शन निर्दिष्ट करती है।<ref name="python_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>
सी शार्प (प्रोग्रामिंग भाषा)|सी# भाषा में, [https://www.nuget.org/packages/HPCsharp HPCsharp nuget पैकेज] न्यूमैयर वैरिएंट और जोड़ीवार योग को लागू करता है: दोनों स्केलर के रूप में, [[SIMD]] प्रोसेसर निर्देशों का उपयोग करके डेटा-समानांतर और समानांतर मल्टी-कोर।<ref>[https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance algorithms].</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>
==यह भी देखें==
==यह भी देखें==
* [[विचरण की गणना के लिए एल्गोरिदम]], जिसमें स्थिर योग शामिल है
* [[विचरण की गणना के लिए एल्गोरिदम]], जिसमें स्थिर सुम्मेशन सम्मिलित है


==संदर्भ==
==संदर्भ==
{{reflist|30em}}
{{reflist|30em}}
==बाहरी संबंध==
==बाहरी संबंध==
* [http://www.ddj.com/cpp/184403224 Floating-point Summation, Dr. Dobb's Journal September, 1996]
* [http://www.ddj.com/cpp/184403224 Floating-point Summation, Dr. Dobb's Journal September, 1996]


{{DEFAULTSORT:Kahan Summation Algorithm}}[[Category: कंप्यूटर अंकगणित]] [[Category: संख्यात्मक विश्लेषण]] [[Category: स्यूडोकोड उदाहरण सहित लेख]]
{{DEFAULTSORT:Kahan Summation Algorithm}}
 
 


[[Category: Machine Translated Page]]
[[Category:CS1|Kahan Summation Algorithm]]
[[Category:Created On 25/07/2023]]
[[Category:CS1 Deutsch-language sources (de)|Kahan Summation Algorithm]]
[[Category:Created On 25/07/2023|Kahan Summation Algorithm]]
[[Category:Machine Translated Page|Kahan Summation Algorithm]]
[[Category:Pages with script errors|Kahan Summation Algorithm]]
[[Category:Pages with syntax highlighting errors|Kahan Summation Algorithm]]
[[Category:Templates Vigyan Ready|Kahan Summation Algorithm]]
[[Category:Webarchive template wayback links|Kahan Summation Algorithm]]
[[Category:कंप्यूटर अंकगणित|Kahan Summation Algorithm]]
[[Category:संख्यात्मक विश्लेषण|Kahan Summation Algorithm]]
[[Category:स्यूडोकोड उदाहरण सहित लेख|Kahan Summation Algorithm]]

Latest revision as of 12:50, 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.

बाहरी संबंध