Question 3. Recall the Babylonian iterative algorithm for approximately computin

Question

Question 3. Recall the Babylonian iterative algorithm for approximately computing the square root of a positive number, n, that we saw in lecture: 1. Begin with a positive starting value zo (Any value works, but assume zo nfor this problem.) 0 = 2. Let Zi +1 be the average of zi and 3. Repeat (2) until the desired accuracy is achieved. We are now going to prove that this algorithm jinds a good upproximation quickly using the Jollowing definition of error which measures how close estimate z, is to Vn afher iteration i: e (Our estimates are always larger than the actual square root, so e >0.) Our claim is: Claim. Each iteration of the Babylonian al orihm improves the estimation error by at least a factor of 2 (a) State the claim in quanificational logic as a claim over input n and iterations i (b) Prove that the claim holds for iteration 1 (for any n 1). (c) Now prove that ei" St. for any iteration i 2 1 (and for any n). (d) Using the claim you proved, how many iterations will be enough to get an estinate o t 00 TT 88 95 00 that is correct to within + I. Do not attempt the calculation! Use logic to convince us

Explanation / Answer

ei = (xi n0.5)/  n0.5

e0= (x0 n0.5)/  n0.5 or e0= (n n0.5)/  n0.5 = n0.5 1

x1 = (x0 + n/x0)/2 = (n+ 1)/2

e1= (x1 n0.5)/  n0.5 = (0.5n + 0.5 n0.5)/  n0.5 = 0.5n0.5 1 + 0.5n0.5

Let us choose n as 4 and x0 as 3

x1 = (x0 + n/x0)/2 = (3 + 4/3)/2 = 13/6 = 2.167

e1= (2.167 40.5)/ 40.5 = 0.167/2 = 0.0835

x2= (x1+ n/x1)/2 = (2.167 + 4/2.167)/2 = 2.006 which is close to the answer 2. Hence proved that the approximation is correct.

Also 0.0835 < 1, thus, e1 < e0

Hence proved.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.