3

I was recently asked to write an algorithm to find the square root of a given integer, with the solution expressed as an integer with the smallest error.

It was unclear to me whether this meant I need to return the integer closest to the actual square root, or return the integer such that, when squared, returned the closest value to the target number. When asking for clarification, I was told these are the same.

This got me thinking however, are these really equivalent?

Clearly, when deciding between two real approximations, minimizing the error of the square roots isn't the same as minimizing the error of the squares. For example, if I had to pick between 1.9 and 2.096 as an approximation of the square root of 4, then 2.096 would be the closest to the actual square root (error of 0.096 compared to 0.1), while 1.9 would provide the smallest error when squared (error of 0.39 compared to 0.393216).

For the integer approximation case, it doesn't appear obvious to me why the solutions to the two cases will always be the same. I've experimentally verified it to be so for the first 200 billion integers. Can anyone provide an intuitive or formal proof of this?

hmakholm left over Monica
  • 286,031
Siam
  • 33

2 Answers2

4

Suppose we want to approximate $\sqrt x$ with $n^2<x<(n+1)^2$.

If we minimize the error of the squares, we're going to choose $n$ or $n+1$ according to whether $x>\frac{n^2+(n+1)^2}2 = n^2 + n + \frac12$.

If we minimize the error of the square root, we should choose $n$ or $n+1$ according to whether $\sqrt{x}>n+\frac12$, which is the same as $x > (n+\frac12)^2 = n^2+n+\frac14$.

Because $x$ is an integer, being larger than $n^2+n+\frac12$ is the same as being larger than $n^2+n+\frac14$.

hmakholm left over Monica
  • 286,031
-1

If $k-{1\over2}\lt\sqrt n\lt k+{1\over2}$, then

$$(k-1)^2=k^2-2k+1\lt k^2-k+{1\over4}\lt n\lt k^2+k+{1\over4}\lt k^2+2k+1=(k+1)^2$$

To flesh this out, the fact that $k$ and $n$ are integers implies

$$k^2-k+1\le n\le k^2+k$$

If $n\gt k^2$, then $n-k^2\le k$ while $(k+1)^2-n\ge k+1$. Likewise, if $n\lt k^2$, then $k^2-n\le k-1$ while $n-(k-1)^2\ge k$. In either case, $n$ is closer to $k^2$ than it is to either $(k-1)^2$ or $(k+1)^2$.

Barry Cipra
  • 79,832