कहान योग एल्गोरिथम

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

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

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

एल्गोरिथम

स्यूडोकोड में, एल्गोरिथ्म होगा:

फंक्शन कहनसम (इनपुट)
    var sum = 0.0 // संचायक तैयार करें।
    var c = 0.0 // खोए हुए लो-ऑर्डर बिट्स के लिए एक चालू मुआवजा।

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

    वापसी राशि

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

    var sum = 0.0 // संचायक तैयार करें।
    var c = 0.0 // खोए हुए लो-ऑर्डर बिट्स के लिए एक चालू मुआवजा।

    for i = 1 to input.length do // array input में तत्व अनुक्रमित इनपुट हैं [1] से इनपुट [input.length]।
        var y = input[i] + c //c पहली बार शून्य है।
        (sum,c) = Fast2Sum(sum,y) // sum + c सटीक योग का एक अनुमान है।
    अगली बार // अगली बार, खोए हुए निचले हिस्से को एक नए प्रयास में y में जोड़ा जाएगा।

    वापसी राशि

काम किया उदाहरण

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

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

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

  वाई = 3.14159 - 0.00000 वाई = इनपुट [i] - सी
  टी = 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) से कुछ अंक योग के उन अंकों से मिले।

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

  y = 2.71828 - (-0.0415900) पिछले चरण की कमी शामिल हो जाती है।
    = 2.75987 यह y के समान आकार का है: अधिकांश अंक मिलते हैं।
  t = 10003.1 + 2.75987 लेकिन कुछ योग के अंकों को पूरा करते हैं।
    = 10005.85987 और परिणाम गोल है
    = 10005.9 छह अंकों के लिए।
  c = (10005.9 - 10003.1) - 2.75987 इसमें जो कुछ भी गया है उसे निकालता है।
    = 2.80000 - 2.75987 इस मामले में, बहुत ज्यादा।
    = 0.040130 लेकिन कोई बात नहीं, अगली बार अतिरिक्त घटा दिया जाएगा।
योग = 10005.9 सटीक परिणाम 10005.85987 है, यह 6 अंकों के लिए सही ढंग से गोल है।

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

सटीकता

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

मान लीजिए कि एक योग है $n$ मान $x_{i}$ , के लिए $i=1,\,\ldots ,\,n$ . सटीक योग है

S_{n}=\sum _{i=1}^{n}x_{i}

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

मुआवजा योग के साथ, एक इसके बजाय प्राप्त करता है $S_{n}+E_{n}$ , जहां त्रुटि $E_{n}$ से घिरा हुआ है^[2]: $|E_{n}|\leq {\big [}2\varepsilon +O(n\varepsilon ^{2}){\big ]}\sum _{i=1}^{n}|x_{i}|,$ कहाँ $\varepsilon$ नियोजित अंकगणित की मशीन परिशुद्धता है (उदा। $\varepsilon \approx 10^{-16}$ IEEE मानक डबल-सटीक फ़्लोटिंग पॉइंट के लिए)। आमतौर पर, ब्याज की मात्रा सापेक्ष त्रुटि होती है $|E_{n}|/|S_{n}|$ , जो इसलिए ऊपर से घिरा हुआ है

{\frac {|E_{n}|}{|S_{n}|}}\leq {\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|}}.

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

एक शर्त संख्या दी गई है, मुआवजा योग की सापेक्ष त्रुटि प्रभावी रूप से स्वतंत्र है $n$ . सिद्धांत रूप में, वहाँ है $O(n\varepsilon ^{2})$ जो रैखिक रूप से बढ़ता है $n$ , लेकिन व्यवहार में यह शब्द प्रभावी रूप से शून्य है: चूंकि अंतिम परिणाम एक सटीकता के लिए गोल है $\varepsilon$ , द $n\varepsilon ^{2}$ टर्म राउंड टू जीरो, जब तक $n$ मोटे तौर पर है $1/\varepsilon$ या बड़ा।^[2] दोहरी सटीकता में, यह एक से मेल खाता है $n$ मोटे तौर पर $10^{16}$ , अधिकांश राशियों से बहुत बड़ा है। तो, एक निश्चित स्थिति संख्या के लिए, मुआवजा योग की त्रुटियां प्रभावी रूप से होती हैं $O(\varepsilon )$ , स्वतंत्र $n$ .

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

उसी टोकन से, द $\Sigma |x_{i}|$ जो इसमें दिखाई देता है $E_{n}$ ऊपर एक सबसे खराब स्थिति है जो केवल तभी होती है जब सभी राउंडिंग त्रुटियों का एक ही संकेत होता है (और अधिकतम संभव परिमाण के होते हैं)।^[2] व्यवहार में, यह अधिक संभावना है कि त्रुटियों में यादृच्छिक चिह्न होते हैं, जिस मामले में शब्द होते हैं $\Sigma |x_{i}|$ एक यादृच्छिक चलना द्वारा प्रतिस्थापित किया जाता है, इस मामले में, यहां तक कि शून्य माध्य वाले यादृच्छिक इनपुट के लिए भी त्रुटि $E_{n}$ के रूप में ही बढ़ता है $O\left(\varepsilon {\sqrt {n}}\right)$ (अनदेखा करते हुए $n\varepsilon ^{2}$ अवधि), समान दर योग $S_{n}$ बढ़ता है, रद्द करता है ${\sqrt {n}}$ कारक जब सापेक्ष त्रुटि की गणना की जाती है। इसलिए, असम्बद्ध रूप से बीमार राशियों के लिए भी, क्षतिपूर्ति योग के लिए सापेक्ष त्रुटि अक्सर सबसे खराब स्थिति वाले विश्लेषण की तुलना में बहुत कम हो सकती है।

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

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

समारोह कहन बाबुष्का न्यूमेयर योग (इनपुट)
    वार योग = 0.0
    var c = 0.0 // खोए हुए लो-ऑर्डर बिट्स के लिए एक चालू मुआवजा।

    for i = 1 to input.length do
        वर टी = योग + इनपुट [मैं]
        अगर | योग | >= |इनपुट[i]| तब
            c + = (योग - t) + इनपुट [i] // यदि  योग  बड़ा है, तो  इनपुट [i]  के निम्न-क्रम अंक खो जाते हैं।
        अन्य
            c + = (इनपुट [i] - t) + योग // अन्यथा  योग  के निम्न-क्रम अंक खो गए हैं।
        अगर अंत
        योग = टी
    अगला मैं

    वापसी योग + सी // सुधार केवल एक बार अंत में लागू होता है।

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

संख्याओं के कई अनुक्रमों के लिए, दोनों एल्गोरिदम सहमत हैं, लेकिन पीटर्स के कारण एक साधारण उदाहरण है^[11]दिखाता है कि वे कैसे भिन्न हो सकते हैं। संक्षेप के लिए $[1.0,+10^{100},1.0,-10^{100}]$ दोहरी सटीकता में, कहन का एल्गोरिथ्म 0.0 देता है, जबकि न्यूमेयर का एल्गोरिथ्म सही मान 2.0 देता है।

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

समारोह कहन बाबुष्का क्लेन सम (इनपुट)
    वार योग = 0.0
    वार सीएस = 0.0
    वार सीसीएस = 0.0
    वार सी = 0.0
    वार सीसी = 0.0

    for i = 1 to input.length do
        वर टी = योग + इनपुट [मैं]
        अगर | योग | >= |इनपुट[i]| तब
            सी = (योग - टी) + इनपुट [i]
        अन्य
            सी = (इनपुट [i] - टी) + योग
        अगर अंत
        योग = टी
        टी = सीएस + सी
        अगर |सीएस| >= |सी| तब
            सीसी = (सीएस - टी) + सी
        अन्य
            सीसी = (सी - टी) + सीएस
        अगर अंत
        सीएस = टी
        सीसीएस = सीसीएस + सीसी
    अंत पाश

    वापसी राशि + सीएस + सीसीएस

विकल्प

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

एक अन्य विकल्प मनमाना-सटीक अंकगणित का उपयोग करना है, जिसे सिद्धांत रूप में बहुत अधिक कम्प्यूटेशनल प्रयास की लागत के साथ बिल्कुल गोल करने की आवश्यकता नहीं है। मनमाने ढंग से परिशुद्धता का उपयोग करके पूरी तरह से गोल रकम का प्रदर्शन करने का एक तरीका कई फ़्लोटिंग-पॉइंट घटकों का उपयोग करके अनुकूली रूप से विस्तार करना है। यह सामान्य मामलों में कम्प्यूटेशनल लागत को कम करेगा जहां उच्च परिशुद्धता की आवश्यकता नहीं है।^[14]^[11] एक अन्य विधि जो केवल पूर्णांक अंकगणित का उपयोग करती है, लेकिन एक बड़ा संचायक, किरचनर और उलरिच डब्ल्यू कुलिश द्वारा वर्णित किया गया था; रेफरी> आर। Kirchner, Ulrich W. Kulisch, वेक्टर प्रोसेसर के लिए सटीक अंकगणित, जर्नल ऑफ़ पैरेलल एंड डिस्ट्रिब्यूटेड कंप्यूटिंग 5 (1988) 250–270। </ref> मुलर, रुब और रूलिंग द्वारा एक हार्डवेयर कार्यान्वयन का वर्णन किया गया था। रेफरी> एम। मुलर, सी. रब, डब्ल्यू. रूलिंग [1], फ्लोटिंग-पॉइंट नंबरों का सटीक संचय, कंप्यूटर अंकगणित पर 10वीं IEEE संगोष्ठी की कार्यवाही (जून 1991), doi:10.1109/ARITH.1991.145535.</रेफरी>

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

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

t = sum + y;

c = (t - sum) - y;

को

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

और फिर करने के लिए

c = 0;

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

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

फंक्शन कहनसम (इनपुट)
    वार योग = 0.0
    वार सी = 0.0

    for i = 1 to input.length do
        var y = इनपुट [i] - सी
        वाष्पशील संस्करण टी = योग + वाई
        वाष्पशील var z = t - योग
        सी = जेड - वाई
        योग = टी
    अगला मैं

    वापसी राशि

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

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

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

जूलिया (प्रोग्रामिंग भाषा) भाषा में, का डिफ़ॉल्ट कार्यान्वयन sum फ़ंक्शन अच्छे प्रदर्शन के साथ उच्च सटीकता के लिए जोड़ो में योग करता है,^[23] लेकिन एक बाहरी पुस्तकालय न्यूमेयर के नाम के संस्करण का कार्यान्वयन प्रदान करता है sum_kbn उन मामलों के लिए जब उच्च सटीकता की आवश्यकता होती है।^[24] C Sharp (प्रोग्रामिंग लैंग्वेज)|C# लैंग्वेज में, HPCsharp nuget package न्यूमैयर वैरिएंट और पेयरवाइज समन को लागू करता है: SIMD प्रोसेसर निर्देशों का उपयोग करके स्केलर, डेटा-समानांतर दोनों के रूप में, और समानांतर मल्टी-कोर।^[25]

यह भी देखें

विचरण की गणना के लिए एल्गोरिदम, जिसमें स्थिर योग शामिल है

संदर्भ

↑ 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.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, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050, S2CID 14071038.
↑ 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.
↑ Babuska, I.: Numerical stability in mathematical analysis. Inf. Proc. ˇ 68, 11–23 (1969)
↑ Bresenham, Jack E. (January 1965). "डिजिटल प्लॉटर के कंप्यूटर नियंत्रण के लिए एल्गोरिथम" (PDF). IBM Systems Journal. 4 (1): 25–30. doi:10.1147/sj.41.0025. S2CID 41898371.
↑ 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.
↑ 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.
↑ Trefethen, Lloyd N.; Bau, David (1997). संख्यात्मक रैखिक बीजगणित. Philadelphia: SIAM. ISBN 978-0-89871-361-9.
↑ ^9.0 ^9.1 Manfred Tasche and Hansmartin Zeuner, Handbook of Analytic-Computational Methods in Applied Mathematics, Boca Raton, FL: CRC Press, 2000.
↑ 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.0 ^11.1 ^11.2 रेमंड हेटिंगर, रेसिपी 393090: बाइनरी फ्लोटिंग पॉइंट समनेशन एक्यूरेट टू फुल प्रिसिजन, शेवचुक (1997) लेख (28 मार्च 2005) से एल्गोरिथम का पायथन इम्प्लीमेंटेशन।
↑ 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.
↑ S. G. Johnson and M. Frigo, "Implementing FFTs in practice, in Fast Fourier Transforms, edited by C. Sidney Burrus(2008).
↑ Jonathan R. Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete and Computational Geometry, vol. 18, pp. 305–363 (October 1997).
↑ 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.
↑ GNU Compiler Collection manual, version 4.4.3: 3.10 Options That Control Optimization, -fassociative-math (Jan. 21, 2010).
↑ 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).
↑ Börje Lindh, Application Performance Optimization, Sun BluePrints OnLine (March 2002).
↑ Eric Fleegal, "Microsoft Visual C++ Floating-Point Optimization", Microsoft Visual Studio Technical Articles (June 2004).
↑ Martyn J. Corden, "Consistency of floating-point results using the Intel compiler", Intel technical report (Sep. 18, 2009).
↑ MacDonald, Tom (1991). "न्यूमेरिकल कंप्यूटिंग के लिए सी". Journal of Supercomputing. 5 (1): 31–48. doi:10.1007/BF00155856. S2CID 27876900.
↑ BLAS Technical Forum, section 2.7 (August 21, 2001), Archived on Wayback Machine.
↑ RFC: use pairwise summation for sum, cumsum, and cumprod, github.com/JuliaLang/julia pull request #4039 (August 2013).
↑ KahanSummation library in Julia.
↑ HPCsharp nuget package of high performance algorithms.

बाहरी संबंध

Floating-point Summation, Dr. Dobb's Journal September, 1996

[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.

[Higham93-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, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050, S2CID 14071038.

[kahan65-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.

[Tasche-9] 9.0 ^9.1 Manfred Tasche and Hansmartin Zeuner, Handbook of Analytic-Computational Methods in Applied Mathematics, Boca Raton, FL: CRC Press, 2000.

[Neumaier74-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.

[python_fsum-11] 11.0 ^11.1 ^11.2 रेमंड हेटिंगर, रेसिपी 393090: बाइनरी फ्लोटिंग पॉइंट समनेशन एक्यूरेट टू फुल प्रिसिजन, शेवचुक (1997) लेख (28 मार्च 2005) से एल्गोरिथम का पायथन इम्प्लीमेंटेशन।

[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).

[Goldberg91-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]