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

赵世忠 等:循环迭代程序的一种可信计算算法 3697

4: while j≤n do
n−j
5: β[j]⇐extra_precision ;
6: if j=1 then
7: y ⇐ 1 f 1 (, ,...,x x 1 2 x m ) εβ× [1] ; //计算 f 1 精度为ε×extra_precision n−1 的值.
8: j⇐j+1;
9: else if j>1 then
10: (, ,,y k ε 0 enough ) ⇐ AccurateEnough ({( , [ ]) |1y β i i i j − ≤≤ 1}, f j ,ε × β [ ])j ;

j
11: if enough=true then
12: j⇐j+1;
13: else
14: l⇐l+1; //修改 l 的值.
l
15: extra_precision⇐0.1 ; //修改精度步长
16: j⇐1; //重新开始
17: end if
18: end if
19: end while
20: return y ;
n
在上述算法中,为了提高计算效率,我们令 y i 的精度超过 y i+1 (1≤i<n)的精度.并且,所有精度构成等比数列.
需要注意的是:若某一次的精度不满足要求,那么一定要像第 16 行那样(提高精度后)从头开始计算.

4 案例分析与验证

对于前述算法,我们已用 C++语言编程实现于 ISReal [7,8] .程序及有关文档的下载网址是:http://www.
isrealsoft.cn/download.htm.ISReal 的现有版本采用 GMP 的整数运算作为底层运算,并且输入与输出均是字符串,
所以采用前述算法的 ISReal 得出的结果是正确结果.除此之外,ISReal 用“y”与“:=”分别代表迭代的函数名与赋
值符号.比如,式(1)中第 1 个赋值语句可以写成这种形式:y1:=2.另外,为了方便操作,ISReal 利用小数位数取代误
n
差限(或精度).比如:若结果的误差限为 0.1 ,则 ISReal 会令结果保留 n 位小数,对应设置函数(或命令)为
DecimalPlaces.
例 4.1:计算式(1)中的 u 30 ,结果保留 16 位有效数字.
由于迭代的极限值为 6,因此不妨令结果保留 15 位小数.这时,由程序的运行过程可知:只有 u 3 重复计算了 5
5
次 , 即 l=5,extra_precision=0.1 . 这样 , 计算时 ,u i (1≤i≤30) 的误差限为 0.1 15+(30−i)×5 . 最终的 输出结果为 :
u 30 =6.006786093031206.
下面的图 2 展示了 ISReal 在计算 u 30 时的环境界面,其中包括 5 行输入与 1 行输出.
例 4.2:计算式(2)中的 u 32 ,结果保留 100 位有效数字.

类似于例 4.1,由于迭代的极限值为 5,因此不妨令结果保留 99 位小数.这时,由程序的运行过程可知:只有 y 3
5
重复计算了 5 次,即 l=5,extra_precision=0.1 .这样,计算时,y i (1≤i≤32)的误差限为 0.1 99+(32−i)×5 .最终输出结果为:
y 32 =4.99999973471133152416344898867038732090718155847042406411602067150199474070118455323008329
5123968309.
例 4.3:计算式(6)中的 y 9 ,结果保留 16 位有效数字.
由于迭代的每个值均为 0.5,因此令结果保留 16 位小数.这时,由程序的运行过程可知:只有 y 2 重复计算了 2
2
次,即 l=2,extra_precision=0.1 .这样,计算时,y i (1≤i≤9)的误差限为 0.1 16+(9−i)×2 .最终输出结果为 y 9 =0.5.