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

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

37: end if

38: D ⇐ (, , ,y k ε 0 enough ) ;
2.1.2 特定函数子算法
1 f
下面给出被主函数调用的第 2 个子算法.其中,f 为 f 1 ×f 2 ,f 1 /f 2 ,sin(f 1 ),arctan(f 1 ),ln(f 1 )或 e .
算法 2. Sub2_AccurateEnough( {( , ) |1y ε ≤≤ n }, ( , ,...,f x x x ),ε ).
i

i i 1 2 n
1: if f=f 1 ×f 2 then

2: D ⇐ AccurateEnough _ Mul ({( , ) |1y ε i ≤≤ n }, ,f f 2 , )ε ;

i
i
1
3: else if f=f 1 /f 2 then

4: D ⇐ AccurateEnough _ Div ({( , ) |1y ε i ≤≤ n }, ,f f 2 , )ε ;
i
i
1
5: else if f=sin(f 1 ) then

6: D ⇐ AccurateEnough _ Sin ({( , ) |1y ε i ≤≤ n }, , )f ε ;

i
1
i
7: else if f=arctan(f 1 ) then

8: D ⇐ AccurateEnough _ ArcTan ({( , ) |1y ε ≤≤ n }, , )f ε ;
i

i i 1
9: else if f=ln(f 1 ) then

10: D ⇐ AccurateEnough _ Ln ({( , ) |1y ε i ≤≤ n }, , )f ε ;

i
i
1
1 f
11: else if f = e then

12: D ⇐ AccurateEnough _ Exp ({( , ) |1y ε i ≤≤ n }, , )f ε ;

i
i
1
13: end if
算法 2 中涉及到了 6 个子算法,分别为乘法运算子算法、除法运算子算法以及正弦函数、自然对数函数、
反正切函数与指数函数子算法.
命题 2.2. 已知函数 f(X),f 1 (X)与 f 2 (X)以及自变量 Y.存在一个算法,对于任意的误差限ε>0 与 Y 的一个计算

值 Y 以及 f(X)或任意一个 f i (X)(1≤i≤2),或者能够判定,利用此计算值可以获得一个值 z,使得:
|z−u|<ε(u∈{f(Y),f 1 (Y),f 2 (Y)}) (19)
成立,或者可以获得一个更为精确的计算值,利用此新的计算值可以获得满足式(19)的一个新的 z.
(1) 乘法运算

定理 2.3. 若命题 2.2 成立,那么存在一个算法,对于 Y 的一个计算值 Y 与ε,或者能够判定,利用此计算值可
以获得一个值 y,使得:
|y−f 1 (Y)×f 2 (Y)|<ε (20)
成立,或者可以获得一个更为精确的计算值,使得利用此新的计算值,可以获得一个满足式(20)的 y.
证明:设|z 1 −f 1 (Y)|<0.1,|z 2 −f 2 (Y)|<0.1.这时:
|z 1 |+0.1>|f 1 (Y)|, |z 2 |+0.1>|f 2 (Y)| (21)
令:
ε 1 =δ(ε/(2(|z 2 |+0.1))), ε 2 =δ(ε/(2(|z 2 |+0.1+ε 1 ))) (22)
则存在 z 3 与 z 4 ,使得:
|z 3 −f 1 (Y)|<ε 1 , |z 4 −f 2 (Y)|<ε 2 (23)
其中,式(23)的第 1 个不等式又意味着:
|z 3 |<|f 1 (Y)|+ε 1 (24)
由式(23)、式(22)、式(21)的第 2 个不等式、式(24)以及式(21)的第 1 个不等式,我们有下列不等式:
( )×
( )| | z <
( ) | ε ×
+
| z × z − f Y f Y ≤ ( )| | z − f Y × ( )| | z − f Y × | ε | f Y + × | z ≤ |
( ) | | f Y
3 4 1 2 3 1 2 4 2 3 1 2 2 3
ε × ( ) | + ε × |< ε + ε × ( ) | ε + ) < ε + ε = ε
1
2
2(| z 2 | 0.1)+ | fY 2(| z + 1 | 0.1 ε + 1 ) | z 3 2 2(| z + 1 | 0.1 ε + 1 ) (| f Y 1 2 2