2
$\begingroup$

Is there a way to check if a number is square number?

For example, we know that $4$ is a square number because $2^2=2$ and $9$ is a square number because $3^2=9$. But for example $5$ is not a square number.

$\endgroup$
  • 2
    $\begingroup$ To check if $n$ is a perfect square, one easy way is to check if any of $1^2,2^2,\dots,(n-1)^2$ equal to $n$, albeit extremely inefficient. $\endgroup$ – Clement Yung Nov 11 '19 at 15:08
  • 1
    $\begingroup$ Factorizing in prime numbers and then check whether the exponents are even. $\endgroup$ – drhab Nov 11 '19 at 15:08
  • 3
    $\begingroup$ Calculate the square root and see if it's an integer. (This is more practical than it might sound.) $\endgroup$ – MJD Nov 11 '19 at 15:10
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/131330 $\endgroup$ – MJD Nov 11 '19 at 15:12
  • $\begingroup$ If $n$ is strictly between two consecutive squares, then $n$ is not a square. That is, if for some natural number $m,$ if $m^2<n<(m+1)^2$ then $n$ is not a square. Also, negative integers are not squares, These two rules cover all non-squares. $\endgroup$ – Thomas Andrews Nov 11 '19 at 15:15
2
$\begingroup$

As a practical matter, the method “guess the square root, then check if you're right” works surprisingly well, and much better than it sounds. The details will depend on whether you are doing a paper-and-pencil calculation or implementing a computer algorithm.

For the paper-and-pencil version, it will go something like this. Let's do an example, say $n=11486$. Let's let $s$ be the largest integer whose square root is $n$ or smaller. If $s^2=n$ exactly, then $n$ is a perfect square.

$n$ has 5 digits, so $s$ will have 3 digits. (In general, if $n$ has $d$ digits, $s$ will have $\frac{d+1}2$. Round down.) And $n$ begins with the digit 1, so that $s$ must be somewhere between 100 and 199. In fact we can do better. $\sqrt2\approx 1.41$ so $s$ can't be bigger than $141$, because $141^2$ must be close to $20000$. (Note that I got this without any actual multiplication, just from knowing the first three digits of $\sqrt 2$. But even if you know only the first two digits, you can still see that $s$ can't be much bigger than $140$.) And indeed $s$ must be pretty close to the bottom of the range $100\ldots 141$ because $11486$ is pretty close to the bottom of the range $10000\ldots20000$.

So let's guess that perhaps $s$ is around $110$. Now $11^2=121$ so $110^2 = 12100$ which is too big. So $s$ is less than $110$.

We can proceed from this and simply make another guess, well, $110$ didn't work, so let's try $105$. Or we could observe that if $n$ were a perfect square then $s$ would have to end with a $4$ or a $6$, because $n$ ends with a $6$, so it would have to be either $104$ or $106$, and since neither one works, $n$ wasn't a square. We can do even better if we are willing to use some actual mathematics. $110^2$ was too big by around $700$. If we divide this by $2$, then by our guess $110$, we get around $3$; this is roughly the amount by which our guess of $110$ was too big! Instead of $110$ we should try $107$. Squaring $107$ we get $11449$ (that's $10000+2\cdot700+49$, which is just a bit less than $n$, so we've found our $s$, and this shows that while $11449$ is a square, $11486$ can't be; it is too close to $11449$. (The next square after $107^2$ is $107^2 + 107 + 108$, but if you estimate $11486-11449$ it's clearly a lot less than that.)

Well, that was fun. Let's do another. Is $n=190969$ a square? It's six digits long so the square root $s$ will be three digits (or put another way, $1000^2 = 1000000$, which is much too big), and it must be between $400$ (whose square is 160000) and $500$ (whose square is 250000). We see that $400^2$ is too small by about $30000$. We should increase our guess by around $\frac{30000}{800} = 37$. Maybe $437$ is the number we want? Multiplying it out, we find that it is! $437^2 = 190969$ exactly.

So for paper and pencil calculation, you can put together a lot of miscellaneous number knowledge:

  1. No square ends with the digit 2, 3, 7, or 8. If $n$ does, you can stop immediately.
  2. If the original number $n$ has $d$ digits, the square root $s$ will have $\frac{d+1}2$.
  3. You can estimate the initial digit of $s$ by looking at the leading two digits of $n$. What's the square root of 79273? I don't know, but 79273 is between 40000 and 90000, so it must be bigger than 200 and smaller than 300.
  4. If you have small square roots memorized, you can leverage them to tell you things about bigger square roots. For example, if you know that $\sqrt3 \approx 1.732$ then you also know that $\sqrt{3000000}\approx 1732$.
  5. If you guess that $g^2\approx n$, and then $g^2$ comes out to be $n+e$ instead, then a better guess is $g - \frac{e}{2g}$. This is called the “Babylonian method”
  6. Squares get farther apart rather quickly as they increase. The next square after $s^2$ is bigger by $s+s+1$.
  7. If $s$ is halfway between $a$ and $b$, then its square will be only a quarter of the way from $a^2$ to $b^2$. If $s^2$ is halfway between $a^2$ and $b^2$, then $s$ will be around 70% of the way between $a$ and $b$.
  8. If $a$ is big and $b$ is small, then you can estimate $(a+b)^2$ more quickly as $a^2 + 2ab$. For example, what's $1027^2$? I can see right off that it's around $1000000 + 54000$. What's $307^2$? It's around $90000 + 4200$.
  9. If you have a guess $g$ and you want to decide if $g^2=n$, you often don't have to multiply out $g^2$ all the way. Often, just looking at the final digit is enough. Could $107^2 = 11486$? No, because $107^2$ ends in a 9, not in a 6.

Perhaps most important:

Don't forget that you're doing integer calculations. They don't have to be precise; they only have to be close enough. If you have to divide $\frac{700}{2\cdot 110}$, calculating $3.1818$ is a waste of time. It's just as good, and much easier, to say “eh, roughly $3$”.

For computer calculation, the situation is different. You can take out all the tricky parts and replace them with straight calculation, because the computer is bad at tricky stuff and great at calculation. The computer doesn't care that $(a+b)^2$ is close to $a^2 + 2ab$, because for the computer calculating $(a+b)^2$ is easier than calculating $a^2 + 2ab$. For the computer, getting an exact answer $\frac{700}{2\cdot 110} = 3.1818\ldots$ is easier than saying “eh, roughly $3$.” So for computer calculation, we can just use the Babylonian method directly: make a guess $g$, then repeatedly adjust $g$ until you get the right answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.