Algorytm sumacyjny Kahana
Algorytm sumacyjny Kahana, znany również jako algorytm sumowania z poprawkami, to technika mająca na celu zminimalizowanie błędów, które mogą wystąpić podczas dodawania ciągu liczb zmiennoprzecinkowych o ograniczonej precyzji.
Pseudokod algorytmu
Oto przedstawienie algorytmu w formie pseudokodu:
function kahanSum(input, n)
var sum = input[1]
var c = 0.0 // Poprawka zawierająca utracone niskie bity.
for i = 2 to n
y = input[i] – c
t = sum + y // sum jest stosunkowo duże w porównaniu do y, co skutkuje utratą mniej znaczących bitów liczby y.
c = (t – sum) – y // (t – sum) przywraca wyższe bity y; odjęcie y pozwala odzyskać -(niższe bity y)
sum = t
next i // W kolejnej iteracji utracone niższe bity zostaną dodane do y
return sum
