logo

SCIENTIA SINICA Informationis, Volume 46 , Issue 6 : 698-713(2016) https://doi.org/10.1360/N112015-00061

A reliable computing algorithm and its software application ISReal for arithmetic expressions

More info
  • ReceivedJul 22, 2015
  • AcceptedOct 15, 2015
  • PublishedMay 27, 2016

Abstract

Precise evaluation of arithmetic expressions is fundamental for ensuring the accuracy of various complicated calculations. However, in most mainstream software, incorrect rounding computation error and machine error lead to results instability. To address the problem of unstable computation, this paper proposes an automated adaptive technique for determining the correct degree of precision in the intermediate steps of a calculation, thereby an algorithm is presented for performing the reliable calculation of arithmetic expressions. In addition, we implement a software application, ISReal, using C++. Using this method, an arithmetic expression can be evaluated with any required degree of precision, regardless of whether the expression is well-conditioned or ill-conditioned, and the calculated value will always be consistent with the theoretical result.


Funded by

国家自然科学基金(61321064)

上海市高可信计算重点实验室开放课题(07dz22304201405)

国家自然科学基金(614025 37)

国家自然科学基金(61572195)

国家自然科学基金(11371143)


References

[1] Lorenz E N. Deterministic nonperiodic flow. J Atmos Sci, 1963, 20: 130-141 CrossRef Google Scholar

[2] Quinn K. Even had problems rounding off figures? This stock exchange has. Wall Street J, 1983, 202: 37. Google Scholar

[3] Stroud R. Rounding error costs DHSS 100 million pounds. Risks Digest, 1987, 5. Google Scholar

[4] Robert S. Roundoff error and the patriot missile. SIAM News, 1992, 25 : 11. Google Scholar

[5] Jakobsen B, Rosendahl F. The Sleipner platform accident. Struct Eng Int, 1994, 4: 190-193 CrossRef Google Scholar

[6] Selby R G, Vecchio F J, Collins M P. The failure of an offshore platform. Concrete Int, 1997, 19 : 28-35. Google Scholar

[7] McCullough B D, Vinod H D. The numerical reliability of econometric software. J Economic Literature, 1999, 37: 633-665 CrossRef Google Scholar

[8] Yang L, Zhou C C, Zhan N J, et al. Recent advances in program verification through computer algebra. Front Comput Sci China, 2010, 4: 1-16 CrossRef Google Scholar

[9] Tang E Y, Barr E, Su Z D, et al. Program instability detection based on systematically optimized numerical perturbation. Sci Sin Inform, 2014, 44 : 1445-1466 [汤恩义, BARR Earl, 苏振东, 等. 程序数值误差的扰动检测与优化. 中国科学: 信息科学, 2014, 44 : 1445-1466 ]. Google Scholar

[10] Zou D, Wang R, Xiong Y F, et al. A genetic algorithm for detecting significant floating-point inaccuracies. In: Proceedings of the 37th IEEE International Conference on Software Engineering. California: IEEE Computer Society, 2015. 529-539. Google Scholar

[11] Zhang J Z, Feng Y. Obtaining accurate values by approximate calculation. Sci China Math, 2007, 37: 809-816 [张景中, 冯勇. 采用近似计算获得准确值. 中国科学: 数学, 2007, 37 : 809-816]. Google Scholar

[12] Cuyt A, Verdonk B, Becuwe S, et al. A remarkable example of catastrophic cancellation unraveled. Computing, 2001, 66: 309-320 CrossRef Google Scholar

[13] Li Q Y, Wang N C, Yi D Y. Numerical Analysis. 5th ed. Beijing: Tsinghua University Press, 2008. 18 [李庆扬, 王能超, 易大义. 数值分析. 第5版. 北京: 清华大学出版社, 2008. 18]. Google Scholar

[14] Zimmermann P. Reliable computing with GNU MPFR. In: Mathematical Software-ICMS 2010. Berlin: Springer, 2010. 42-45. Google Scholar

[15] Rump S. Algorithms for verified inclusion: theory and practice. In: Reliability in Computing: the Role of Interval Methods in Scientific Computing. Boston: Academic Press, 1988. 109-126. Google Scholar

[16] Muller J M, Brisebarre N, Dinechin F D, et al. Handbook of Floating-Point Arithmetic. Boston: Birkhauser Boston, 2010. 12. Google Scholar

[17] Loh E, Walster G W. Rump's example revisited. Reliable Comput, 2002, 8: 245-248 CrossRef Google Scholar

[18] Higham N J. Accuracy and Stability of Numerical Algorithms. 2nd ed. Philadelphia: SIAM, 2002. 17. Google Scholar

[19] Inverse trigonometric functions. Wikipedia. http://en.wikipedia.org/wiki/Inverse\_trigonometric\_function. Google Scholar

[20] John Machin. Wikipedia. https://en.wikipedia.org/wiki/John\_Machin. Google Scholar

[21] Zhen X F. Applied Numerical Method. Beijing: Tsinghua University Press, 2006. 53-80 [甄西丰. 实用数值计算方法. 北京: 清华大学出版社, 2006. 53-80]. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号