Algoritmul lui Kahan

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 noiembrie 2020; verificările necesită 6 modificări .

În matematica computațională , algoritmul lui Kahan (cunoscut și ca însumare compensatorie ) este un algoritm pentru calcularea sumei unei secvențe de numere în virgulă mobilă care reduce semnificativ eroarea de calcul .comparativ cu abordarea naivă. Reducerea erorilor se realizează prin introducerea unei variabile suplimentare pentru a stoca suma în creștere a erorilor.

În special, simpla însumare a numerelor în cel mai rău caz are o eroare care crește proporțional și, la însumarea numerelor aleatoare, are o abatere standard proporțională cu (erorile de rotunjire provoacă o plimbare aleatoare ) [1] . La însumarea compensatorie, eroarea, chiar și în cel mai rău caz, nu depinde de , astfel încât un număr mare de termeni pot fi însumați cu o eroare care depinde doar de precizia numărului în virgulă mobilă [1] .

Autoritatea algoritmului este atribuită lui William Kahan [2] .

Algoritm

În pseudocod , algoritmul poate fi scris astfel:

function kahan_sum ( input ) var sum = 0.0 var c = 0.0 // Suma erorilor. for i = 1 to len ( input ) do y = input [ i ] - c // Până acum e bine: c este zero. t = sum + y // Din păcate, suma este mare, y este mică, deci biții inferiori ai lui y se pierd. c = ( t - sum ) - y // (t - sum) restabilește biții mari ai lui y; scăderea y restaurează -(cifrele inferioare ale lui y) sum = t // Algebric, c ar trebui să fie întotdeauna zero. Atenție la optimizarea excesivă a compilatoarelor! // Data viitoare când LSB-urile pierdute vor fi adăugate din nou la y. sumă returnată

Exemplu de execuție

În acest exemplu, vom folosi fracții zecimale. Calculatoarele folosesc de obicei aritmetică binară, dar algoritmul ilustrat nu se modifică. Să presupunem că folosim aritmetică cu virgulă mobilă din șase cifre, sumei i s-a atribuit valoarea 10000,0, iar următoarele două valori de intrare (i) sunt 3,14159 și 2,71828. Rezultatul exact este 10005,85987, care se rotunjește la 10005,9. Cu o simplă însumare, ordinea fiecărei valori primite ar fi aliniată cu sum și multe cifre de ordin scăzut ar fi pierdute ca urmare a rotunjirii. Primul rezultat după rotunjire ar fi 10003,1. Al doilea rezultat ar fi 10005,81828 înainte de rotunjire și 10005,8 după rotunjire, deci ultima cifră a rezultatului ar fi greșită.

Cu o însumare compensatorie, am obține rezultatul rotunjit corect de 10005,9.

Să presupunem că valoarea inițială a lui c  este 0.

y = 3,14159 - 0 y = intrare[i] - c t = 10000,0 + 3,14159 = 10003,1 Prea mulți biți pierduți! c = (10003,1 - 10000,0) - 3,14159 Acesta trebuie calculat așa cum este scris! = 3,10000 - 3,14159 Partea din y care nu a fost inclusă în t a fost restaurată , dar nu întregul y original . = -0,0415900 Zerourile finale sunt afișate deoarece aceasta este aritmetică de șase cifre. sum = 10003.1 Astfel, nu toți biții de la intrarea(i) sunt incluși în sum .

Suma este atât de mare încât se păstrează doar cifrele de început ale termenului. Din fericire, la pasul următor, c stochează o eroare.

y = 2,71828 - -0,0415900 Se ia în considerare eroarea de la pasul anterior. = 2,75987 Ordinea sa nu este prea diferită de y . Majoritatea categoriilor sunt luate în considerare. t = 10003,1 + 2,75987 Dar doar câțiva biți fac suma . = 10005,85987, rotunjit la 10005,9 c = (10005,9 - 10003,1) - 2,75987 = 2,80000 - 2,75987 Prea mult în acest caz. = 0,040130 Într-un fel sau altul, surplusul va fi dedus data viitoare. suma = 10005,9 Rezultatul exact este 10005,85987, care este rotunjit corect la 6 cifre.

Astfel, adunarea are loc în două variabile: sum stochează suma, iar c stochează partea din sumă care nu a fost în sum , pentru a fi luată în considerare în sumă la următoarea iterație. În timp ce însumarea prin stocarea cifrelor mici în c este mai bună decât a nu le stoca nicăieri, nu este totuși la fel de precisă precum efectuarea calculului folosind intrare de precizie dublă. Cu toate acestea, pur și simplu creșterea preciziei calculelor nu este în general practică; dacă intrarea este deja cu precizie dublă, puține sisteme pot oferi calcule cu precizie cvadruplă, iar dacă ar putea, intrarea ar putea fi și precizie cvadruplă.

Dezavantaje

Din păcate, algoritmul lui Kahan nu garantează protecția împotriva pierderii de precizie asociată cu prezența termenilor cu ordine semnificativ diferite în sumă . Acest lucru se poate întâmpla dacă secvența de însumare nu este bine aleasă. Pentru a vedea acest lucru, este suficient să luați −10000 în loc de numărul 2,71828 din exemplul de mai sus. La ultimul pas al algoritmului avem următoarele:

y = -10000,0 - -0,0415900 = -10000,0 Rezultatul este rotunjit la 6 cifre semnificative t = 10003,1 + -10000,0 = 3,10000 c = (3,10000 - 10003,1) - -10000,0 = -10000,0 + 10000,0 = 0 suma = 3,10000

Rezultat exact: 3,14159, adică a existat o pierdere de precizie.

Trebuie remarcat faptul că, dacă ordonăm mai întâi termenii în ordinea descrescătoare a valorii lor absolute , atunci ca urmare a aplicării algoritmului obținem rezultatul 3.14159, unde toate semnele sunt corecte.

Note

  1. ↑ 1 2 Higham, Nicholas J. (1993), The accuracy of floating point summation , SIAM Journal on Scientific Computing vol. 14 (4): 783–799 , DOI 10.1137/0914050 
  2. ↑ Kahan, William (ianuarie 1965), Observații suplimentare privind reducerea erorilor de trunchiere , Communications of the ACM vol . 8 (1): 40 , DOI 10.1145/363707.363723  

Link -uri