Square golf

Square roots are fairly slow to calculate (well, compared to other things our computers can do anyway). Here is an even slower way of doing it.

Say we want to find the square root of some number r, for example, let's take 13.

1. Find two integers that are next to each other, one of which squared to a larger number than r and the other to a number smaller than r. For 13, 3 squares to 9 and 4 squares to 16 so our initial boundary is 3, 4 — we know the square root is between these two numbers.
2. Find the number which is half way between our bounds. If this number squares to more than r then it becomes our new upper bound, if it squares to less than r it becomes the new lower bound.
3. Repeat step 2 until we have our answer.

This is a kind of binary search to find the required value.

• The answer should be as precise as possible and at the same time the program must produce a single answer and then terminate.
• If you end up in an infinite loop then the program is disqualified.
• The input should be read from standard input and the result displayed to standard output.