Discrete Mathematics for Computer Science

Program Correctness 61

RESULT: Approximation of hi

Root = 4

for i = 1 to 4 do

Root = (Root + 17/Root)/2

print Root

The computation starts by assigning 4 to Root. The value in Root at any time will

represent the current approximation to N/1. For each iteration of the for loop, the current

approximation is improved by evaluating the expression

(Root + 17/Root)/2

and storing the "better" approximation in Root. This process continues until the for loop

has been executed four times. The value of Root after each of the first four iterations is

shown in Table 1.2.

Table 1.2 Output from Square Root II

Values of Root for I= 1, 2, 3, 4

1 Root

1 4.125

2 4.12310606060606

3 4.12310562561768

4 4.12310562561766

With any iterative algorithm, it is important to know with each iteration that the error

gets smaller. Let Rn denote the value of Root after the for loop has been executed n times.

Then, as before En = /P7 - Rn is the error in the calculation after n executions of the for

loop. The error can be either positive or negative.

Theorem 5. Prove that for Square Root II, the error bound cn for Rn satisfies the inequal-

ity IEI < (1/2)6.2n-3 for each n E N.

Proof. Letno =0. LetT= {n e N: 16nI < (1/2)6"2n-3}.

(Base step) Since (4.1)2 - 16.81 and (4.125)2 = 17.015625, it follows that

4.1 <V i7 < 4.125

Now, Ro = 4, so

4.1 -R 0 < V_7-Ro <4.125-Ro

co < 0.125 (Ro = 4)

CO < (1/2)6"2°-3