What does the following algorithm approximate? (Assume m>1,ϵ>0)

Question

x = m; y = 1; While (x-y > ϵ) { x = (x+y)/2; y = m/x; } print(x);

The answer is m½, its the Babylonian algorithm for square roots. I understand the algorithm but haven't been able to reverse engineer what this code does (which is the point of this question since its not part of the curriculum and almost no one would have prior knowledge of it). So again, my question is how can I deduce this code calculates square roots, just from the code itself?

Answer 1

By simply looking at the structure of the loop, we know that if the while loop terminates after going into the loop (I'll assume this for simplicity as it's the interesting case) that $y=\frac{m}{x}$ (last instruction) and that $x-y<\epsilon$ (exit condition). Combining the two gives you $x< \sqrt{m+x\dot\epsilon}$. If you manage to notice that $x\geq y$ at the end of each iteration of the loop, then you also get $x\geq y=\frac{m}{x}$ and therefore $\sqrt{m}\leq x< \sqrt{m+x\dot\epsilon}$.

---

You could write down the sequence of values taken by $x$ and $y$ mathematically (this is what you would do anyway to prove correctness and termination of the algorithm if you knew what it did/was supposed to do, but it can also help you to determine this!).

Initially, $\begin{cases}x_{0}=m\\ y_{0}=1\end{cases}$. At the end of the $n^{\text{th}}$ iteration of the while loop: $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$

Now, analysing the two sequences we find that:

1. $(x_n)$ is decreasing
2. $(y_n)$ is increasing
3. $x_0>y_0$

This is enough to say both sequences converge (as they are monotonic and bounded), to say $x$ and $y$. Using $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$ we can say that $x=y$.

So $\forall n>0,x_n\geq x=y\geq y_n$. In particular the algorithm must terminate (as $x_n-y_n$ is non-negative and converges to $0$). From there you can continue like in the first part ('By simply looking at the$\dots$').

Answer 2

One method is guessing that x ends up close to $m^{1/2}$ and prove it. The guessing is the hard part.

My method would be to try this for a few values of m, print out the results, make the same guess and prove it in the same way.

Another method is to solve a few hundred problems, look at the code, recognise it, guess x and prove it.

A not very promising method is staring at the code and waiting for enlightenment.

Now if you have the guess: You will find for m > 1 that initially x is almost divided by 2 in each step. When x is close to $m^{1/2}$, write $x = m^{1/2} * (1 + c)$ and see how the calculation changes c.