कहन योग एल्गोरिथ्म: Difference between revisions

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


मान लीजिए कि कोई योग कर रहा है <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
        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
</syntaxhighlight>
   
   
  i = 1 के लिए इनपुट.लेंथ करें
  var t = योग + इनपुट[i]
  यदि |योग| >= |इनपुट[i]| तब
  सी = (योग - टी) + इनपुट[i]
  अन्य
  सी = (इनपुट[i] - टी) + योग
  अगर अंत
  योग = टी
  टी = सीएस + सी
  यदि |सीएस| >= |सी| तब
  सीसी = (सीएस - टी) + सी
  अन्य
  सीसी = (सी - टी) + सीएस
  अगर अंत
  सीएस = टी
  सीसीएस = सीसीएस + सीसी
  अंत पाश
  वापसी योग + सीएस + सीसीएस


==विकल्प==
==विकल्प==
चूँकि कहन का एल्गोरिदम हासिल करता है <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>


==[[संकलक अनुकूलन]] द्वारा संभावित अमान्यकरण==
==[[संकलक अनुकूलन]] द्वारा संभावित अमान्यकरण==
Line 155: Line 160:
और फिर को
और फिर को
: <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>
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
फ़ंक्शन KahanSum(इनपुट)
</syntaxhighlight>
  वर योग = 0.0
  वर सी = 0.0
  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> और बीएलएएस कार्यान्वयन आम तौर पर कहन सारांश का उपयोग नहीं करते हैं।
सामान्य रूप से  कंप्यूटर भाषाओं में अंतर्निहित योग फ़ंक्शन समान्यत: कोई आश्वासन नहीं देते हैं कि एक विशेष योग एल्गोरिथ्म को नियोजित किया जाएगा, काहन योग तो बिल्कुल भी नहीं{{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> और बीएलएएस कार्यान्वयन समान्यत: कहन सारांश का उपयोग नहीं करते हैं।
   
   
[[पायथन (प्रोग्रामिंग भाषा)]] कंप्यूटर भाषा की मानक लाइब्रेरी, [[जोनाथन शेवचुक]] एल्गोरिथ्म का उपयोग करते हुए, बिल्कुल गोल योग के लिए एक [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>
 
C शार्प (प्रोग्रामिंग भाषा) या  C# भाषा में, [https://www.nuget.org/packages/HPCsharp एचपीसीशार्प नुगेट पैकेज] न्यूमैयर वैरिएंट और जोड़ीवार योग को प्रयुक्त करता है: दोनों स्केलर के रूप में, [[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>
सी शार्प (प्रोग्रामिंग भाषा)|सी# भाषा में, [https://www.nuget.org/packages/HPCsharp HPCsharp nuget पैकेज] न्यूमैयर वैरिएंट और जोड़ीवार योग को लागू करता है: दोनों स्केलर के रूप में, [[SIMD]] प्रोसेसर निर्देशों का उपयोग करके डेटा-समानांतर और समानांतर मल्टी-कोर।<ref>[https://github.com/DragonSpit/HPCsharp HPCsharp nuget package of high performance algorithms].</ref>




==यह भी देखें==
==यह भी देखें==
* [[विचरण की गणना के लिए एल्गोरिदम]], जिसमें स्थिर योग शामिल है
* [[विचरण की गणना के लिए एल्गोरिदम]], जिसमें स्थिर योग सम्मिलित है


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

Revision as of 17:29, 29 July 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


पुस्तकालयों द्वारा समर्थन

सामान्य रूप से कंप्यूटर भाषाओं में अंतर्निहित योग फ़ंक्शन समान्यत: कोई आश्वासन नहीं देते हैं कि एक विशेष योग एल्गोरिथ्म को नियोजित किया जाएगा, काहन योग तो बिल्कुल भी नहीं[citation needed] रैखिक बीजगणित सबरूटीन्स के लिए बीएलएएस मानक स्पष्ट रूप से प्रदर्शन कारणों से संचालन के किसी विशेष कम्प्यूटेशनल क्रम को अनिवार्य करने से बचाता है,[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.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कहन_योग_एल्गोरिथ्म&oldid=255790’