Kahanの総和法 - tkenichi の日記

数値をたくさん足し上げるとき、数値誤差の問題は忘れがち。統計ソフトを使っているときは中でうまくやっているのだと思うけど、自分でプログラムを作っているときは気をつけないと誤差がたまるようなコードを書いてしまう。

有名なのが標本分散の計算で、
$s^2 = \frac{1}{n} \sum_{i=1}^{n}(\bar{x}-x_{i})$
を
$s^2 = \frac{1}{n} \sum_{i=1}^{n}x_{i}^{2} - \bar{x}^{2}$
で計算すると桁落ちしてしまう。

単純に総和を求めるときも、桁落ちは発生してしまう。それを防ぐ方法のひとつが Kahan の総和法と呼ばれるもの。自分メモをかねて、サンプル。

def sum(a)
	s = 0.0
	a.each{ |v|
		s += v
	}
	return s
end

def sum_kahan(a)
	sum = 0.0
	diff = 0.0
	a.each{ |v|
		y = v - diff
		t = sum + y
		diff = (t-sum)-y
		sum = t
	}
	return sum
end

a = Array.new
100000.times{
	a << 0.1
}

p sum(a)
p sum_kahan(a)

実行してみると、

10000.0000000188
10000.0

となる。http://codepad.org/rYrO2S2R

10万個のデータの標本分散を計算するときの和をとるのにこの方法を使った場合と使わなかった場合の差は、2乗の平均から平均の2乗で計算したときの差の 1/3 ぐらい出た。結構馬鹿にできない。http://codepad.org/yid2H2CZ