カハンの加算アルゴリズム
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/12/12 05:33 UTC 版)
カハンの加算アルゴリズム(英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム)とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合[1]に、計算の途中の誤差を保持することで補正する。Compensated summation(補正加算)とも呼ぶ[2]。
- ^ 任意精度演算でない、という意味。
- ^ 「補正加算」と呼ばれる技法は他にもある。詳しくは Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 110–123
- ^ a b c d e f g Higham, Nicholas J. (1993), “The accuracy of floating point summation”, SIAM Journal on Scientific Computing 14 (4): 783–799, doi:10.1137/0914050
- ^ Kahan, William (January 1965), “Further remarks on reducing truncation errors”, Communications of the ACM 8 (1): 40, doi:10.1145/363707.363723
- ^ Jack E. Bresenham, "Algorithm for computer control of a digital plotter", IBM Systems Journal, Vol. 4, No.1, January 1965, pp. 25–30
- ^ H. Inose, Y. Yasuda, J. Murakami, "A Telemetering System by Code Manipulation – ΔΣ Modulation," IRE Trans on Space Electronics and Telemetry, Sep. 1962, pp. 204–209.
- ^ L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM: Philadelphia, 1997).
- ^ a b Manfred Tasche and Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000).
- ^ S. G. Johnson and M. Frigo, "Implementing FFTs in practice, in Fast Fourier Transforms, edited by C. Sidney Burrus (2008).
- ^ Jonathan R. Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete and Computational Geometry, vol. 18, pp. 305–363 (October 1997).
- ^ Raymond Hettinger, Recipe 393090: Binary floating point summation accurate to full precision, Python implementation of algorithm from Shewchuk (1997) paper (28 March 2005).
- ^ R. Kirchner, U. W. Kulisch, Accurate arithmetic for vector processors, Journal of Parallel and Distributed Computing 5 (1988) 250-270
- ^ M. Muller, C. Rub, W. Rulling Exact accumulation of floating-point numbers, Proceedings 10th IEEE Symposium on Computer Arithmetic (Jun 1991), doi 10.1109/ARITH.1991.145535
- ^ Goldberg, David (March 1991), “What every computer scientist should know about floating-point arithmetic” (PDF), ACM Computing Surveys 23 (1): 5–48, doi:10.1145/103162.103163
- ^ GNU Compiler Collection manual, version 4.4.3: 3.10 Options That Control Optimization, -fassociative-math (Jan. 21, 2010).
- ^ Compaq Fortran User Manual for Tru64 UNIX and Linux Alpha Systems, section 5.9.7 Arithmetic Reordering Optimizations (retrieved March 2010).
- ^ Eric Fleegal, "Microsoft Visual C++ Floating-Point Optimization", Microsoft Visual Studio Technical Articles (June 2004).
- ^ Martyn J. Corden, "Consistency of floating-point results using the Intel compiler," Intel technical report (Sep. 18, 2009).
- ^ Tom Macdonald, "C for Numerical Computing", Journal of Supercomputing vol. 5, pp. 31–48 (1991).
- ^ BLAS Technical Forum, section 2.7 (August 21, 2001).
- 1 カハンの加算アルゴリズムとは
- 2 カハンの加算アルゴリズムの概要
- 3 代替手法
- 4 最適化にまつわる注意
- 5 外部リンク
カハンの加算アルゴリズムと同じ種類の言葉
- カハンの加算アルゴリズムのページへのリンク