Kahan toplama algoritması - Kahan summation algorithm

Olarak sayısal analizi , Kahan toplama algoritması olarak da bilinen, kompanse toplamı , önemli ölçüde azaltır sayısal hata bir eklenmesi ile elde edilen, toplam sekansı sonlu bir hassas kayan nokta sayısının belirgin bir yaklaşıma göre,. Bu, ayrı bir çalışma telafisi (küçük hataları biriktirmek için bir değişken) tutularak yapılır .

Özellikle, sayıları basitçe sırayla toplamak , ile orantılı olarak büyüyen bir en kötü durum hatasına ve rastgele girdilerde olduğu gibi büyüyen bir kök ortalama kare hatasına sahiptir (yuvarlama hataları rastgele bir yürüyüş oluşturur ). Telafi edilmiş toplama ile, en kötü durum hatası sınırı etkin bir şekilde 'den bağımsızdır , bu nedenle çok sayıda değer, yalnızca kayan nokta kesinliğine bağlı olan bir hatayla toplanabilir . ${\görüntüleme stili n}$${\görüntüleme stili n}$${\displaystyle {\sqrt {n}}}$${\görüntüleme stili n}$

Algoritma atfedilir William Kahan ; Ivo Babuška bağımsız olarak benzer bir algoritma bulmuş gibi görünüyor (dolayısıyla Kahan-Babuška toplamı ). Benzer, daha önceki teknikler, örneğin, Bresenham'ın çizgi algoritması , tamsayı işlemlerinde (ilk olarak aynı zamanda belgelenmiş olmasına rağmen) birikmiş hatayı ve delta-sigma modülasyonunu takip eder.

algoritma

Gelen pseudocode , algoritma olacaktır;

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

Çalışılan örnek

Bu örnek ondalık olarak verilecektir. Bilgisayarlar tipik olarak ikili aritmetik kullanır, ancak gösterilen prensip aynıdır. Altı basamaklı ondalık kayan noktalı aritmetik kullandığımızı, sum10000.0 değerine ulaştığımızı ve sonraki iki değerinin input[i]3.14159 ve 2.71828 olduğunu varsayalım. Kesin sonuç 10005.85987'dir ve bu da 10005.9'a yuvarlanır. Düz bir toplamla, gelen her değer ile hizalanır sumve birçok düşük sıralı basamak kaybolur (kesme veya yuvarlama yoluyla). Yuvarlamadan sonra ilk sonuç 10003.1 olacaktır. İkinci sonuç, yuvarlamadan önce 10005.81828 ve yuvarlamadan sonra 10005.8 olacaktır. Bu doğru değil.

Ancak, telafi edilmiş toplamla, 10005.9'luk doğru yuvarlatılmış sonucu elde ederiz.

cBaşlangıç ​​değerinin sıfır olduğunu varsayalım .

  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.

Toplam o kadar büyüktür ki, yalnızca giriş numaralarının yüksek sıralı basamakları toplanır. Ama sonraki adımda chata veriyor.

  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.

Böylece toplama iki akümülatör ile gerçekleştirilir: sumtoplamı tutar ve cözümsenmemiş parçaları biriktirir sum, bir sonraki seferin düşük dereceli kısmını dürtmek için sum. Böylece toplama, içinde "koruyucu basamaklar" ile devam eder; cbu, hiç olmamasından daha iyidir, ancak hesaplamaları girdinin iki katı hassasiyetle yapmak kadar iyi değildir. Ancak, sadece hesaplamaların kesinliğini arttırmak genel olarak pratik değildir; eğer inputçift hassasiyet zaten çok az sistem kaynağı dörtlü hassasiyet , ve eğer, inputo zaman dörtlü hassas olabilir.

Kesinlik

Doğruluk özelliklerini değerlendirmek için telafi edilmiş toplamdaki hataların dikkatli bir analizine ihtiyaç vardır. Saf toplamdan daha doğru olsa da, koşulsuz toplamlar için yine de büyük göreli hatalar verebilir.

Tek toplayarak olduğunu varsayalım değerleri için, . tam toplam ${\görüntüleme stili n}$${\displaystyle x_{i}}$${\displaystyle i=1,\,\ldots ,\,n}$

${\displaystyle S_{n}=\sum _{i=1}^{n}x_{i}}$ (sonsuz hassasiyetle hesaplanmıştır).

Telafi edilmiş toplama ile, bunun yerine hatanın sınırlandığı yerde elde edilir. ${\displaystyle S_{n}+E_{n}}$${\ Displaystyle E_{n}}$

${\displaystyle |E_{n}|\leq {\big [}2\varepsilon +O(n\varepsilon ^{2}){\big ]}\sum _{i=1}^{n}|x_{ ben}|,}$

burada bir makine hassas aritmetik (örneğin istihdam edilen IEEE standardı için çift hassasiyetli kayan nokta). Genellikle, ilgilenilen miktar nispi hatadır , bu nedenle yukarıda sınırlanmıştır. ${\görüntüleme stili\varepsilon }$${\ Displaystyle \ varepsilon \ yaklaşık 10^{-16}}$ ${\displaystyle |E_{n}|/|S_{n}|}$

${\displaystyle {\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}\sağ|} }.}$

Göreceli hata sınırı ifadesinde kesir , toplama probleminin koşul numarasıdır . Esasen koşul numarası , nasıl hesaplandığından bağımsız olarak, toplama probleminin hatalara karşı içsel duyarlılığını temsil eder . Sabit hassasiyette sabit bir algoritma (yani keyfi kesinlikli aritmetik kullananlar veya veriye bağlı olarak bellek ve zaman gereksinimleri değişen algoritmalar değil) tarafından her ( geriye doğru kararlı ) toplama yönteminin bağıl hata sınırı bu koşul sayısıyla orantılıdır. . Bir kötü koşullanmış toplamıdır sorun bu oran büyük olduğu biridir ve bu durumda bile telafi toplamıdır büyük bağıl hata olabilir. Örneğin , toplamlar sıfır ortalamalı ilişkisiz rasgele sayılarsa, toplam rasgele yürüyüştür ve koşul sayısı ile orantılı olarak büyüyecektir . Öte yandan, sıfırdan farklı ortalamaya sahip rastgele girdiler için koşul sayısı asimptotları olarak sonlu bir sabite dönüşür . Girişlerin tümü negatif değilse, koşul numarası 1'dir. ${\displaystyle \Sigma |x_{i}|/|\Sigma x_{i}|}$${\displaystyle x_{i}}$${\displaystyle {\sqrt {n}}}$${\displaystyle n\to \infty }$

Bir koşul numarası verildiğinde, telafi edilen toplamın göreli hatası etkin bir şekilde 'den bağımsızdır . Prensip olarak, bir ile doğrusal olarak büyür Nihai olarak hassas yuvarlanır çünkü: ama pratikte bu terim etkili bir şekilde sıfır olduğu , sıfıra terimi mermi sürece, kabaca veya daha büyük. Çift kesinlikte, bu , çoğu toplamdan çok daha büyük bir kabaca 'ye karşılık gelir . Bu nedenle, sabit bir koşul numarası için, telafi edilen toplamın hataları etkin bir şekilde 'den bağımsızdır . ${\görüntüleme stili n}$${\displaystyle O(n\varepsilon ^{2})}$${\görüntüleme stili n}$${\görüntüleme stili\varepsilon }$${\displaystyle n\varepsilon ^{2}}$${\görüntüleme stili n}$${\displaystyle 1/\varepsilon }$${\görüntüleme stili n}$${\görüntüleme stili 10^{16}}$${\ Displaystyle O(\varepsilon )}$${\görüntüleme stili n}$

Karşılaştırıldığında, saf toplama (sadece sırayla sayıların eklenmesi, her adımda yuvarlanması) için sınırlanan göreli hata , koşul numarasıyla çarpıldığı gibi büyür . Bu en kötü durum hatası pratikte nadiren gözlenir, çünkü yalnızca yuvarlama hatalarının tümü aynı yöndeyse oluşur. Pratikte, yuvarlama hatalarının rasgele bir yürüyüş oluşturmaları için sıfır ortalamalı rasgele bir işarete sahip olması çok daha olasıdır; bu durumda, saf toplamın, koşul sayısıyla çarpılarak büyüyen bir ortalama karekök göreli hatası vardır . Ancak bu yine de telafi edilen toplamdan çok daha kötü. Bununla birlikte, toplam iki kat hassasiyette gerçekleştirilebiliyorsa, o zaman ile değiştirilir ve saf toplam, orijinal kesinlikte telafi edilmiş toplamdaki terimle karşılaştırılabilir en kötü durum hatasına sahiptir . ${\ Displaystyle O(\varepsilon n)}$${\displaystyle O\sol(\varepsilon {\sqrt {n}}\sağ)}$${\görüntüleme stili\varepsilon }$${\displaystyle \varepsilon ^{2}}$${\displaystyle O(n\varepsilon ^{2})}$

Aynı şekilde, yukarıda görünen , yalnızca tüm yuvarlama hataları aynı işarete sahipse (ve mümkün olan maksimum büyüklükteyse) oluşan en kötü durum sınırıdır. Pratikte, hataların rasgele işaretli olması daha olasıdır, bu durumda in terimleri rasgele yürüyüşle değiştirilir, bu durumda, sıfır ortalamalı rasgele girdiler için bile, hata yalnızca ( terimi yok sayarak) şu şekilde büyür: aynı oranda toplam büyür, bağıl hata hesaplandığında faktörleri iptal eder . Bu nedenle, asimptotik olarak kötü koşullu toplamlar için bile, telafi edilmiş toplamın göreli hatası çoğu zaman en kötü durum analizinin önerebileceğinden çok daha küçük olabilir. ${\displaystyle \Sigma |x_{i}|}$${\ Displaystyle E_{n}}$${\displaystyle \Sigma |x_{i}|}$${\ Displaystyle E_{n}}$${\displaystyle O\sol(\varepsilon {\sqrt {n}}\sağ)}$${\displaystyle n\varepsilon ^{2}}$${\displaystyle S_{n}}$${\displaystyle {\sqrt {n}}}$

Diğer geliştirmeler

Neumaier, "geliştirilmiş Kahan-Babuška algoritması" olarak adlandırdığı, Kahan algoritmasının geliştirilmiş bir versiyonunu tanıttı; bu, eklenecek bir sonraki terimin mutlak değerde çalışan toplamdan daha büyük olduğu durumu da kapsar ve neyin rolünü etkin bir şekilde değiştirir. büyük ve ne küçük. Gelen pseudocode , algoritma:

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.

Birçok sayı dizisi için, her iki algoritma da aynı fikirdedir, ancak Peters'e bağlı basit bir örnek, bunların nasıl farklı olabileceğini gösterir. Çift kesinlikte toplama için, Kahan'ın algoritması 0.0, Neumaier'in algoritması ise 2.0 doğru değerini verir. ${\displaystyle [1.0,+10^{100},1.0,-10^{100}]}$

Daha iyi doğrulukta daha yüksek dereceli değişiklikler de mümkündür. Örneğin, Klein tarafından önerilen ve ikinci dereceden "yinelemeli Kahan-Babuška algoritması" olarak adlandırdığı bir varyant. Gelen pseudocode , algoritma:

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

    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
    next i

    return sum + cs + ccs

alternatifler

Kahan'ın algoritması n sayıları toplamak için hata büyümesi elde etse de, ikili toplama ile yalnızca biraz daha kötü büyüme elde edilebilir : sayı kümesini özyinelemeli olarak iki yarıya böler, her yarıyı toplar ve sonra iki toplamı toplar. Bu, saf toplamla aynı sayıda aritmetik işlem gerektirme avantajına sahiptir (dört kez aritmetik gerektiren ve dört kez basit bir toplamın gecikmesine sahip olan Kahan'ın algoritmasının aksine) ve paralel olarak hesaplanabilir. Özyinelemenin temel durumu ilke olarak yalnızca bir (veya sıfır) sayının toplamı olabilir, ancak özyinelemenin ek yükünü amorti etmek için normalde daha büyük bir temel durum kullanılır. İkili toplamın eşdeğeri birçok hızlı Fourier dönüşümü (FFT) algoritmasında kullanılır ve bu FFT'lerdeki yuvarlama hatalarının logaritmik büyümesinden sorumludur. Pratikte, rastgele işaretlerin yuvarlama hatalarıyla, ikili toplamın ortalama karekök hataları aslında olarak büyür . ${\görüntüleme stili O(1)}$${\görüntüleme stili O(\log n)}$${\displaystyle O\sol({\sqrt {\log n}}\sağ)}$

Başka bir alternatif, prensipte çok daha fazla hesaplama çabası maliyeti ile hiçbir yuvarlama gerektirmeyen keyfi kesinlikli aritmetik kullanmaktır . Rastgele kesinlik kullanarak tam olarak yuvarlanmış toplamlar gerçekleştirmenin bir yolu, birden çok kayan nokta bileşeni kullanarak uyarlanabilir şekilde genişletmektir. Bu, yüksek hassasiyetin gerekli olmadığı yaygın durumlarda hesaplama maliyetini en aza indirecektir. Yalnızca tamsayı aritmetiği kullanan, ancak büyük bir akümülatör kullanan başka bir yöntem Kirchner ve Kulisch tarafından tanımlanmıştır ; bir donanım uygulaması Müller, Rüb ve Rülling tarafından tanımlanmıştır.

Derleyici optimizasyonu ile olası geçersiz kılma

İlke olarak, yeterince agresif bir optimize edici derleyici , Kahan toplamının etkinliğini yok edebilir: örneğin, derleyici ifadeleri gerçek aritmetiğin ilişkilendirme kurallarına göre basitleştirirse, dizideki ikinci adımı "basitleştirebilir".

t = sum + y;

c = (t - sum) - y;

ile

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

ve sonra

c = 0;

böylece hata telafisini ortadan kaldırır. Pratikte, birçok derleyici, "güvenli olmayan" optimizasyonları etkinleştiren derleyici seçenekleri tarafından açıkça yönlendirilmedikçe, basitleştirmelerde ilişkilendirme kurallarını (yalnızca kayan nokta aritmetiğinde yaklaşık değerlerdir) kullanmaz, ancak Intel C++ Derleyicisi ilişkilendirmeye izin veren bir örnektir. varsayılan olarak -tabanlı dönüşümler. C programlama dilinin orijinal K&R C versiyonu , derleyicinin gerçek aritmetik ilişkilendirme kurallarına göre kayan noktalı ifadeleri yeniden sıralamasına izin verdi, ancak müteakip ANSI C standardı, C'yi sayısal uygulamalar için daha uygun hale getirmek için yeniden sıralamayı yasakladı ( ve yeniden sıralamayı da yasaklayan Fortran'a daha çok benzer ), ancak pratikte derleyici seçenekleri yukarıda belirtildiği gibi yeniden sıralamayı yeniden etkinleştirebilir.

Bu tür optimizasyonları yerel olarak engellemenin taşınabilir bir yolu, orijinal formülasyondaki satırlardan birini iki ifadeye bölmek ve ara ürünlerden ikisini uçucu hale getirmektir :

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

Kütüphaneler tarafından destek

Genel olarak, bilgisayar dillerindeki yerleşik "toplam" işlevleri, Kahan toplamı şöyle dursun, belirli bir toplama algoritmasının kullanılacağına dair hiçbir garanti sağlamaz. BLAS için standart lineer cebir alt yordamlar açıkça performans nedenleriyle işlemlerin herhangi bir hesaplama düzeni zorunlu önler ve BLAS uygulamalar tipik olarak Kahan toplamı kullanmayın.

Python bilgisayar dilinin standart kitaplığı, birden çok kısmi toplamı izlemek için Shewchuk algoritmasını kullanarak tam olarak yuvarlanmış toplam için bir fsum işlevi belirtir .

In Julia dil, varsayılan uygulaması sumfonksiyonu yapar İkili toplamı iyi bir performans ile yüksek doğruluk için değil, harici kütüphane adında Neumaier en varyantın bir uygulamasını sağlar sum_kbnyüksek doğruluk gerektiğinde durumlar için.

Olarak , C # dil, HPCsharp Nuget paket uygular Neumaier varyantı ve ikili toplam : kullanarak skalar, veri-paralel olarak, her iki SIMD işlemci talimatlarının ve çok çekirdekli paraleldir.

Ayrıca bakınız

• Kararlı toplamı içeren varyansı hesaplamak için algoritmalar

Referanslar

Dış bağlantılar

• Kayan Nokta Toplamı, Dr. Dobb's Journal Eylül, 1996