Namaran

Code daily. Without assist.

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 をそのまま足した値になります。