山口屋~活動日誌~

私生活で主な出来事をピックアップ

TwoSum TwoProduct Kahan 敗者復活算法 丸め誤差

2022-11-03 20:48:35 | ソフトウェア開発
加算または乗算の丸め誤差を拾うことができるアルゴリズムとして、TwoSum や TwoProduct が知られている。
Donald E. Knuth : The Art of Computer Programming Volume 2: Seminumerical Algorithms, Addison-Wesley (1969)
T. J. Dekker : A Floating-point Technique for Extending the Available Precision, Numerische Mathematik, Vol.18, No.3, pp.224-242 (1971)

エラーフリー変換と呼ばれることもあるが、拾った丸め誤差を上手く使わなければ普通に計算するのと変わらなくなってしまう。なので、エラーフリー変換という表現はあまり好きではない。
TwoSum や TwoProduct の、オーバーフローとアンダーフローへの対策、そこから発展して疑似的な4倍精度演算(倍精度浮動小数点数演算の2倍)を行う手法もあるようだ。
柏木雅英:double-double 演算、double-double 区間演算に関するまとめ(PDF)

級数の和の計算などで、拾った丸め誤差も次の項と一緒に加算する、敗者復活算法とも呼ばれる技法を使うと、精度改善が見られる場合がある。
William Kahan : Further remarks on reducing truncation errors, Communications of the ACM, Vol.8, No.1, pp.40 (January 1965)
S:和>a:加算項という前提で、FastTwoSumで足し込んでいくのである。

コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« 浮動小数点数 比較 一致 判定... | トップ | プラレール 西武鉄道 9000系 ... »
最新の画像もっと見る

コメントを投稿

ソフトウェア開発」カテゴリの最新記事