浮動小数点数の小数演算には誤差が付き物
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