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

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?

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

• $(y_n)$ is increasing

• $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$').

StackExchange Computer Science Q#115231, answer score: 4