カハンの加算アルゴリズム

浮動小数点数の小数演算には誤差が付き物

function sum(array) {
  let result = 0;
  for (let i = 0; i < array.length; i++) {
    result += array[i]
  }
  return result;
}

const a = Array(1000000).fill(0.1);
console.log(sum(a));

結果

100000.00000133288

この誤差を減らして足し算するのがカハンの加算アルゴリズム。誤差を補正しながら加算して誤差を最小限にするらしい。

function sumKahan(array) {
    let s = 0.0;
    let c = 0.0;
    for (const i of array) {
        const y = i - c;
        const t = s + y;
        c = (t - s) - y;
        s = t;
    }

    return s;
}

const a = Array(1000000).fill(0.1);
console.log(sumKahan(a));

結果

100000

ところでRubyの Enumerable#sum はカハンの加算アルゴリズムが採用されているらしい。

([0.1] * 100000).inject(0) { |sum, n| sum + n }
=> 10000.000000018848

([0.1] * 100000).sum
=> 10000.0