2026-11-15
KSumMerge.hs
data KSum = KSum Double Double
add :: KSum -> Double -> KSum
add (KSum s c) x = KSum t ((t - s) - y)
where
y = x - c
t = s + y
ksum :: [Double] -> KSum
ksum = foldl add (KSum 0 0)
total :: KSum -> Double
total (KSum s _) = s
merge :: KSum -> KSum -> KSum
ksum は、add で値を1つずつ KSum に足し込み、丸めで失われた分を2つ目の成分に残しながら総和を求めます。2つの KSum を1つにまとめる merge を書いてください。total (merge (ksum xs) (ksum ys)) が、xs と ys の値をすべて足した正確な値に近くなるようにします。
入力例 1
total (merge (ksum [1e20]) (ksum [-1e20, 1]))
出力例 1
1.0
入力例 2
total (merge (ksum [1, 2]) (ksum [3]))
出力例 2
6.0
入力例 3
total (merge (ksum []) (ksum [0.5]))
出力例 3
0.5
Reference
Reference
data KSum = KSum Double Double
add :: KSum -> Double -> KSum
add (KSum s c) x = KSum t ((t - s) - y)
where
y = x - c
t = s + y
ksum :: [Double] -> KSum
ksum = foldl add (KSum 0 0)
total :: KSum -> Double
total (KSum s _) = s
merge :: KSum -> KSum -> KSum
merge a (KSum s c) = add (add a s) (negate c)
add の中で、t は s + y を丸めた値で、(t - s) - y は丸めで余分に足した分です。値が丸めで切り捨てられれば、この差は負になります。KSum s c は、s から c を引いた s - c が、それまでに足した値の正確な総和に近い、という状態を保っています。次の値から c を引いてから足すのは、この - c を総和に戻すためです。
この見方をすると、KSum s c は「s と - c という2つの値」と同じものです。そこで merge は、片方の KSum に、もう片方の s と negate c を同じ add で順に足し込みます。足し込む値が2つ増えるだけなので、どちらの補正値も捨てずに済みます。掲載したのは参考実装で、唯一の正解ではありません。
入力例 1 では、ksum [-1e20, 1] の 1 は -1e20 に足したときに丸めで消え、KSum (-1e20) (-1) になります。s は -1e20 ですが、失われた 1 は c の -1 に残っています。参考実装では、1e20 に -1e20 を足して 0 になり、そこへ negate (-1) の 1 を足して 1.0 になります。成分ごとに足して KSum (s1 + s2) (c1 + c2) を作ると、total が見るのは s だけなので 0.0 になり、c を引かずに足すと -1.0 になります。入力例 3 の空のリストは KSum 0 0 なので、0.5 をそのまま足した値になります。