2Sum

2Sum ^{[ 1 ]}は、浮動小数点加算演算における正確な丸め誤差を計算する浮動小数点アルゴリズムです。

2Sum とその派生アルゴリズム Fast2Sum は、1965 年に Ole Møller によって初めて発表されました。^{[ 2 ]} Fast2Sum は、補償加算アルゴリズムなどの他のアルゴリズムで暗黙的に使用されることがよくあります。^{[ 1 ]} Kahan の加算アルゴリズムは 1965 年に初めて発表され、^{[ 3 ]} Fast2Sum は後に 1971 年にDekkerによって double-double 算術アルゴリズム用にそこから分離されました。^{[ 4 ]} 2SumとFast2Sum という名前は、1997 年にShewchukによって遡及的に適用されたようです。^{[ 5 ]}

アルゴリズム

2つの浮動小数点数が与えられた場合 $a$ そして $b$ 2Sum は浮動小数点数の合計を計算します $s:=a\oplus b$ 最も近い値に丸められ、浮動小数点誤差 $t:=a+b-(a\oplus b)$ となることによって $s+t=a+b$ 、どこ $\oplus$ そして $\ominus$ それぞれ加算と減算を最も近い値に丸めた値を表します。誤差 $t$ それ自体が浮動小数点数です。

入力される浮動小数点数

a,b

丸めた合計を出力します

s=a\oplus b

正確な誤差

t=a+b-(a\oplus b)

$s:=a\oplus b$
$a':=s\ominus b$
$b':=s\ominus a'$
$\delta _{a}:=a\ominus a'$
$\delta _{b}:=b\ominus b'$
$t:=\delta _{a}\oplus \delta _{b}$
戻る $(s,t)$

浮動小数点演算が正しく最も近い値に丸められ（同点の場合はいずれにせよ解決される）、IEEE 754のデフォルトであり、合計がオーバーフローせず、アンダーフローする場合は徐々にアンダーフローする場合、次のことが証明できる。 $s+t=a+b$ [ ¹^]^[⁶^]^[²^]

2Sum のバリアントであるFast2Sumは、指数が 2 または 3 の浮動小数点演算に対して 3 つの浮動小数点演算のみを使用します。 $a$ は少なくとも指数と同じくらい大きい。 $b$ 例えば、 $\left|a\right|\geq \left|b\right|$ : ^{[ 1 ]}^{[ 6 ]}^{[ 7 ]}^{[ 4 ]}

入力は基数2または基数3の浮動小数点数です。

a

そして

b

少なくとも１つがゼロであるか、または正規化された指数を持つ

e_{a}\geq e_{b}

丸めた合計を出力します

s=a\oplus b

正確な誤差

t=a+b-(a\oplus b)

$s:=a\oplus b$
$z=s\ominus a$
$t=b\ominus z$
戻る $(s,t)$

条件が満たされない場合でも、2Sum と Fast2Sum は誤差の妥当な近似値を提供することが多い。 $s+t\approx a+b$ これにより、入力がソートされていない場合や丸めモードが通常とは異なる場合でも、補償加算、ドット積などのアルゴリズムのエラーを低く抑えることができます。^{[ 1 ]}^{[ 2 ]}

2Sum および Fast2Sum のより複雑なバリアントは、最も近い値への丸め以外の丸めモードに使用されます。^{[ 1 ]}

参考文献

1 2 3 4 5 6ミュラー、ジャン＝ミッシェル;ブルーニー、ニコラス。デ・ディネシン、フィレンツェ。ジャンヌロ、クロード・ピエール。ミオアラ州ジョルデス。ルフェーブル、ヴァンサン。メルキオンド、ギョーム。ナタリー・レボル;トーレス、セルジュ (2018)。浮動小数点演算ハンドブック(第 2 版)。スイス、シャム：ビルクホイザー。 pp. 104–111 . doi : 10.1007/978-3-319-76526-6。ISBN 978-3-319-76525-92023年4月28日にオリジナルからアーカイブされました。2020年9月20日に取得。
1 2 3 Møller, Ole (1965 年 3 月). 「浮動小数点加算における準倍精度」. BIT Numerical Mathematics . 5 : 37–50 . doi : 10.1007/BF01975722 . S2CID 119991676 .
↑ Kahan, W. (1965 年 1 月). 「切り捨て誤差の削減に関するさらなる考察」 . Communications of the ACM . 8 (1). Association for Computing Machinery: 40. doi : 10.1145/363707.363723 . ISSN 0001-0782 . S2CID 22584810 .
1 2 Dekker, TJ (1971 年 6 月). 「利用可能な精度を拡張するための浮動小数点技術」 . Numerische Mathematik . 18 (3): 224–242 . doi : 10.1007/BF01397083 . S2CID 63218464. 2020 年 7 月 19 日にオリジナルからアーカイブ済み。2020年 9 月 24 日に取得。
↑ Shewchuk, Jonathan Richard (1997 年 10 月) 「適応精度浮動小数点演算と高速で堅牢な幾何述語」 . Discrete & Computational Geometry . 18 (3): 305–363 . doi : 10.1007/PL00009321 .
1 2クヌース、ドナルド・E. (1998).コンピュータプログラミングの技法、第2巻：半数値アルゴリズム（第3版）。アディソン・ウェスリー。p. 236。ISBN 978-0-201-89684-82017年7月16日にオリジナルからアーカイブされました。2020年9月20日に取得。
↑ Sterbenz, Pat H. (1974). Floating-Point Computation . Englewood Cliffs, NJ, United States: Prentice-Hall. pp. 138–143 . ISBN 0-13-322495-3。

[handbook-1] 1 2 3 4 5 6ミュラー、ジャン＝ミッシェル;ブルーニー、ニコラス。デ・ディネシン、フィレンツェ。ジャンヌロ、クロード・ピエール。ミオアラ州ジョルデス。ルフェーブル、ヴァンサン。メルキオンド、ギョーム。ナタリー・レボル;トーレス、セルジュ (2018)。浮動小数点演算ハンドブック(第 2 版)。スイス、シャム：ビルクホイザー。 pp. 104–111 . doi : 10.1007/978-3-319-76526-6。ISBN 978-3-319-76525-92023年4月28日にオリジナルからアーカイブされました。2020年9月20日に取得。

[moeller-2] 1 2 3 Møller, Ole (1965 年 3 月). 「浮動小数点加算における準倍精度」. BIT Numerical Mathematics . 5 : 37–50 . doi : 10.1007/BF01975722 . S2CID 119991676 .

[kahan-3] Kahan, W. (1965 年 1 月). 「切り捨て誤差の削減に関するさらなる考察」 . Communications of the ACM . 8 (1). Association for Computing Machinery: 40. doi : 10.1145/363707.363723 . ISSN 0001-0782 . S2CID 22584810 .

[dekker-4] 1 2 Dekker, TJ (1971 年 6 月). 「利用可能な精度を拡張するための浮動小数点技術」 . Numerische Mathematik . 18 (3): 224–242 . doi : 10.1007/BF01397083 . S2CID 63218464. 2020 年 7 月 19 日にオリジナルからアーカイブ済み。2020年 9 月 24 日に取得。

[shewchuk-5] Shewchuk, Jonathan Richard (1997 年 10 月) 「適応精度浮動小数点演算と高速で堅牢な幾何述語」 . Discrete & Computational Geometry . 18 (3): 305–363 . doi : 10.1007/PL00009321 .

[knuth-taocp-vol2-6] 1 2クヌース、ドナルド・E. (1998).コンピュータプログラミングの技法、第2巻：半数値アルゴリズム（第3版）。アディソン・ウェスリー。p. 236。ISBN 978-0-201-89684-82017年7月16日にオリジナルからアーカイブされました。2020年9月20日に取得。

[sterbenz-7] Sterbenz, Pat H. (1974). Floating-Point Computation . Englewood Cliffs, NJ, United States: Prentice-Hall. pp. 138–143 . ISBN 0-13-322495-3。

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

2Sum

アルゴリズム

関連項目

参考文献

関連するトピック

丸め誤差を計算する

浮動小数点

Fast2Sum は、補償加算アルゴリズム

Fast2Sum は後に 1971 年にDekkerによって