What does the following algorithm approximate? C x = m; y = 1; while (x - y >…
2004
What does the following algorithm approximate?
C
x = m;
y = 1;
while (x - y > e)
{
x = (x + y)/2;
y = m/x;
}
print(x);
(Assume m > 1, e > 0).
- A.
log m
- B.
m2
- C.
m1/2
- D.
m1/3
Attempted by 100 students.
Show answer & explanation
Correct answer: C
Answer: The algorithm approximates the square root of m (sqrt(m)).
Rewrite the update: since y is set to m/x each iteration, the assignment x = (x + y)/2 is equivalent to x = (x + m/x)/2. This is the Babylonian (Newton) iteration for finding sqrt(m).
Fixed point check: if x satisfies x = (x + m/x)/2, then multiplying both sides by 2x gives 2x^2 = x^2 + m, so x^2 = m. Thus any limit of the iteration must be sqrt(m) (the positive root, since m>1 and initial x>0).
Stopping condition: the loop stops when x - y <= e. Because y = m/x, when x and y are within e of each other the value of x is within the specified tolerance of sqrt(m), so printing x returns an approximation of sqrt(m).
Initial values: starting with x = m and y = 1 places x above and y below sqrt(m), so the iterations converge from both sides toward sqrt(m).
Therefore the algorithm approximates sqrt(m) (m^(1/2)).