Algorytm sumacyjny Kahana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

W analizie numerycznej algorytm sumacyjny Kahana (zwany także algorytmem sumowania z poprawkami) minimalizuje błędy powstałe przy dodawaniu ciągu liczb zmiennopozycyjnych o skończonej precyzji.

Algorytm w pseudokodzie:

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 względnie duże w porównaniu z y co powoduje utratę bitów mniej znaczących liczby y.
        c = (t - sum) - y         //(t - sum) odzyskuje wyższe bity y; odjęcie y odzyskuje -(niższe bity y)
        sum = t                   
    next i                  //W następnej iteracji utracone niższe bity zostaną dodane do y
    return sum