Page 19 - 《软件学报》2020年第12期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(12):3685−3699 [doi: 10.13328/j.cnki.jos.005883] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
循环迭代程序的一种可信计算算法

3
1,2
赵世忠 , 陈冬火 , 刘 静 1,2
1
(华东师范大学 软件工程学院,上海 200062)
2 (上海市高可信计算重点实验室(华东师范大学),上海 200062)
3 (苏州大学 计算机科学与技术学院,江苏 苏州 215006)
通讯作者: 赵世忠, E-mail: szzhao@sei.ecnu.edu.cn

摘 要: 循环迭代程序作为软件的基本组成部分,其正确运行具有重要意义.然而,有时(比如其相关错数大于 0 时)
计算时的舍入误差(或表示误差)会导致循环迭代的计算结果不稳定.基于“中间计算精度自动动态调整”的计算技
术,给出了循环迭代程序的一种可信计算算法.利用该算法,可获得循环迭代程序任意次迭代的任意位的正确有效数
字.目前,通过 C++语言该算法已被编程实现于 ISReal 中.
关键词: 循环迭代;误差可控计算;可信计算;可靠计算;错数
中图法分类号: TP311

中文引用格式: 赵世忠,陈冬火,刘静.循环迭代程序的一种可信计算算法.软件学报,2020,31(12):3685−3699. http://www.jos.
org.cn/1000-9825/5883.htm
英文引用格式: Zhao SZ, Chen DH, Liu J. Reliable algorithm for computing cyclic iterative program. Ruan Jian Xue Bao/ Journal
of Software, 2020,31(12):3685−3699 (in Chinese). http://www.jos.org.cn/1000-9825/5883.htm
Reliable Algorithm for Computing Cyclic Iterative Program

1,2
3
ZHAO Shi-Zhong , CHEN Dong-Huo , LIU Jing 1,2
1
(Software Engineering Institute, East China Normal University, Shanghai 200062, China)
2
(Shanghai Key Laboratory for Trustworthy Computing (East China Normal University), Shanghai 200062, China)
3
(School of Computer Science and Technology, Soochow University, Suzhou 215006, China)
Abstract: As a basic component of software, the correct running of cyclic iteration program is of great significance. However,
sometimes (e.g., when its NID is greater than 0) the rounding error (or representation error) in the calculation can lead to unstable results
of the cyclic iteration. Based on the computing technology of “automatic dynamic adjustment of intermediate calculation accuracy”, a
reliable calculation algorithm for cyclic iteration is presented in this paper. By using this algorithm, the value of arbitrary precision of
cyclic iteration can be obtained. At present, the algorithm has been programmed and implemented in ISReal through C++ language.
Key words: cyclic iteration; error-controlled calculation; trusted computing; reliable computing; NID

[1]
1989 年,Muller 在其著作《计算机算术》 中给出了一个循环迭代:
⎧
⎪ u =
⎪ 1 2
⎪ u =− 4 (1)
⎨
2
⎪ 1130 3000
u ⎪ n = 111− +
⎪ ⎩ u n− 1 u u 2
n−
1 n−

∗ 基金项目: 国家重点研发项目(2017YFB1001800); 国家自然科学基金(61772203, 61972150, 61876034)
Foundation item: National Key Research and Development Program of China (2017YFB1001800); National Natural Science
Foundation of China (61772203, 61972150, 61876034)
收稿时间: 2019-04-17; 修改时间: 2019-05-30, 2019-07-21; 采用时间: 2019-08-05