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

Latest revision as of 17:20, 19 September 2023

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

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

स्पष्टता

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

मान लीजिए कि कोई $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}$ )। समान्यत: ब्याज की मात्रा सापेक्ष त्रुटि होती है $|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}}$ . दूसरी ओर, गैर-शून्य के साथ यादृच्छिक इनपुट के लिए स्थिति संख्या अनंतस्पर्शी को परिमित स्थिरांक $n\to \infty$ के रूप में दर्शाती है यदि सभी इनपुट गैर-ऋणात्मक हैं, तब नियमित संख्या 1 है।

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

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

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] दिखाता है कि वह कैसे भिन्न हो सकते हैं। संक्षेप के लिए $[1.0,+10^{100},1.0,-10^{100}]$ दोहरी परिशुद्धता में, काहन का एल्गोरिदम 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 संख्याओं के योग के लिए $O(1)$ त्रुटि वृद्धि को प्राप्त करता है, केवल कुछ व्यर्थ $O(\log n)$ वृद्धि को जोड़ीदार योग द्वारा प्राप्त किया जा सकता है: कोई संख्याओं के सेट को दो भागो में पुनरावर्ती रूप से विभाजित करता है, प्रत्येक आधे का योग करता है, और फिर जोड़ता है दो मान ^[2] इसका लाभ यह है कि इसमें सरल योग के समान अंकगणितीय परिचालन की आवश्यकता होती है (कहान के एल्गोरिदम के विपरीत, जिसके लिए चार गुना अंकगणित की आवश्यकता होती है और चार गुना सरल योग की विलंबता होती है) और समानांतर में गणना की जा सकती है। पुनरावृत्ति का आधार स्थिति सैद्धांतिक रूप से केवल (या शून्य) संख्याओं का योग हो सकता है, किंतु पुनरावृत्ति के ओवरहेड को परिशोधित करने के लिए, समान्यत: बड़े आधार स्थिति का उपयोग किया जाएगा। जोड़ीवार योग के समतुल्य का उपयोग अनेक तेज़ फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम में किया जाता है और यह उन एफएफटी में राउंडऑफ त्रुटियों के लॉगरिदमिक विकास के लिए उत्तरदाई है।^[13] वास्तव में, यादृच्छिक संकेतों की राउंडऑफ त्रुटियों के साथ, जोड़ीवार योग की मूल माध्य वर्ग त्रुटियां वास्तव में $O\left({\sqrt {\log n}}\right)$ के रूप में बढ़ती हैं।^[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]

यह भी देखें

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

संदर्भ

↑ 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, Bibcode:1993SJSC...14..783H, 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) से एल्गोरिदम का पायथन कार्यान्वयन। रेफरी>आर. किरचनर, उलरिच डब्ल्यू. कुलिश, वेक्टर प्रोसेसर के लिए सटीक अंकगणित, जर्नल ऑफ़ पैरेलल एंड डिस्ट्रिब्यूटेड कंप्यूटिंग 5 (1988) 250-270। एक हार्डवेयर कार्यान्वयन का वर्णन मुलर, रब और रूलिंग द्वारा किया गया था। रेफरी>एम. मुलर, सी. रब, डब्ल्यू. रूलिंग [1], फ्लोटिंग-पॉइंट संख्याओं का सटीक संचय, कंप्यूटर अंकगणित पर 10वीं IEEE संगोष्ठी की कार्यवाही (जून 1991), doi:10.1109/ARITH.1991.145535.
↑ 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, Bibcode:1993SJSC...14..783H, 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) से एल्गोरिदम का पायथन कार्यान्वयन। रेफरी>आर. किरचनर, उलरिच डब्ल्यू. कुलिश, वेक्टर प्रोसेसर के लिए सटीक अंकगणित, जर्नल ऑफ़ पैरेलल एंड डिस्ट्रिब्यूटेड कंप्यूटिंग 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).

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

@@ 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> स्पष्ट दृष्टिकोण की तुलना में, परिमित-स्पष्ट फ़्लोटिंग-पॉइंट संख्याओं के अनुक्रम को जोड़कर प्राप्त कुल में संख्यात्मक त्रुटि को अधिक कम कर देता है। यह अलग चल रहे क्षतिपूर्ति (छोटी त्रुटियों को जमा करने के लिए वेरिएबल) को रखकर किया जाता है, जो वास्तव में क्षतिपूर्ति वेरिएबल की परिशुद्धता द्वारा योग की परिशुद्धता को बढ़ाता है।
@@ Line 191: / Line 190: @@
 * [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]]
-[[Category:Created On 25/07/2023]]
+[[Category:CS1 Deutsch-language sources (de)]]
-[[Category:Vigyan Ready]]
+[[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]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Webarchive template wayback links]]
+[[Category:कंप्यूटर अंकगणित|Kahan Summation Algorithm]]
+[[Category:संख्यात्मक विश्लेषण|Kahan Summation Algorithm]]
+[[Category:स्यूडोकोड उदाहरण सहित लेख|Kahan Summation Algorithm]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 17:20, 19 September 2023

Contents

एल्गोरिदम

कार्य उदाहरण

स्पष्टता

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

विकल्प

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 17:20, 19 September 2023

एल्गोरिदम

कार्य उदाहरण

स्पष्टता

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

विकल्प

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories