2Sumは、浮動小数点数の加算において、丸められた和とその丸め誤差を厳密に計算する、浮動小数点演算のみからなるアルゴリズムである。
2Sumおよびその変種であるFast2Sumは、Ole Møllerによって1965年に初めて発表された。 Fast2Sumは、補償加算アルゴリズムなどのアルゴリズムの中でしばしば暗黙裡に用いられる。実際、1965年に発表されたKahanの加算アルゴリズムは、Fast2Sumに相当する計算を含んでいる。その後、Dekker (1971) は擬似四倍精度演算の議論において、Fast2Sumを独立した定理として記述した。 「2Sum」および「Fast2Sum」という名称はShewchuk (1997) が初出とみられる。
アルゴリズム 所与の浮動小数点数 と に対して、2Sumは、最近接丸めによる和 と丸め誤差 を計算する。ただし、 および は、それぞれ最近接丸めによる加算および減算を表す。
algorithm 2Sum is s ← a ⊕ b a' ← s ⊖ b b' ← s ⊖ a' δ ← a ⊖ a' δ ← b ⊖ b' t ← δ ⊕ δ return (s, t)
浮動小数点演算が最近接丸めで計算され、アンダーフローした際は漸進的アンダーフローで処理されると仮定する。ただし、丸める前の値が隣接する2つの浮動小数点数のちょうど中間である場合はどちら側に丸めてもよく、IEEE 754の既定の丸め方式はこれらの仮定を満たす。このとき、オーバーフローが発生しなければ、丸め誤差 は浮動小数点数で厳密に表現可能であり、 が成り立つ。
2Sumの変種であるFast2Sumは、3回の浮動小数点演算のみからなる。
algorithm Fast2Sum is s ← a ⊕ b z ← s ⊖ a t ← b ⊖ z return (s, t)
丸めとアンダーフローについては2Sumと同じ仮定の下、浮動小数点演算の基数は2または3であり、 と の少なくとも一方が零であるか、 の正規化された指数が の正規化された指数以上であるとする。このとき、 がオーバーフローしなければ が成り立つ。なお、指数の条件については、その十分条件である でしばしば代替される。
仮定が満たされていない場合にも、2SumおよびFast2Sumは、しばしば丸め誤差の妥当な近似 を与える。この性質により、補償加算やドット積などのアルゴリズムにおいて、入力が絶対値の大きさ順に並べられていない場合や、丸めモードが最近接丸めではない場合でも、出力の誤差は小さくなることが多い。
最近接丸め以外の丸めモードについても、2SumおよびFast2Sumのより複雑な変種が知られている。
関連項目
カハンの加算アルゴリズム 丸め誤差
参考文献