# Determine if a number is a perfect square

Checking if a number is a perfect square is a trivial task when a square root function is available. Calculating the floored square root squared should result in the original number:

$\sqrt{n}\in\mathbb{N}\Leftrightarrow\lfloor\sqrt{n}\rfloor^2 = n$

On many systems, a calculation of a square root is costly, so the easiest way is a $$O(\sqrt{n})$$ iteration like

function isPerfectSquare(n) {

for (let i = 0; i * i <= n; i++) {

if (i * i === n) {
return true;
}
}
return false;
}

However, many numbers have certain patterns that can be exploited to make the best case performance $$O(1)$$ by excluding whole ranges of numbers. The $$O(\sqrt{n})$$ is then only required as a worst case fallback.

## Check last digit

It is well known that in base 10, a perfect square can have the least significant digit to be only 0, 1, 4, 5, 6 or 9, which forbids 2, 3, 7 and 8 under modulo 10.

The proof is pretty straightforward. Let's say the least significant digit of our number $$n\in\mathbb{Z}$$ is $$a$$ and the remaining digits are called $$b$$, we can then say $$n=10b+a$$.

Now when squared, $$n^2=(10b+a)^2=100b^2+20ab+a^2$$. It is clear that the first part $$100b^2+2ab\cdot 10$$ does not affect the least significant digit, but only $$a$$ does.

Listing all possible squares results in

$\{a^2 : a\in[0, 9]\} = \{0,1,4,9,16,25,36,49,64,81\}$

which ultimately shows that the only possible least significant digits of a perfect square are 0,1,4,5,6 and 9.

## Check digital root

The digital root of a number $$n$$ is the sum of all digits of that number. If the sum has more than one digit, the procedure is repeated until only one digit remains. Instead of implementing a recursive solution, we can use a trick. When we work in base $$b:= 10$$, it is clear that for any $$k$$ the following concurrence holds: $$b^k\equiv 1\pmod{b-1}$$. As the number $$n$$ consists of its digits $$n_i$$ times $$10^i$$, the following happens when we sum under the modular concruence 9:

$\begin{array}{rl}\text{dr}(n) &= \sum\limits_{i=0}10^i\cdot n_i \pmod{9}\\&= \sum\limits_{i=0}1\cdot n_i \pmod{9}\\&= \sum\limits_{i=0}n_i \pmod{9}\\&= \begin{cases}n\pmod{9} & n\not\equiv 0\pmod{9}\\9 & n\equiv 0\pmod{9}\end{cases}\\&= 1 + (n-1\pmod{9})\end{array}$

Using the digital root function, we can now check the behavior when getting a squared number:

$\begin{array}{rl}\text{dr}(n^2) &= 1 + (n^2-1\pmod{9})\\&= 1 + (n^2 + 8\pmod{9})\\&= \underbrace{1 + \big(\underbrace{(n^2\pmod{9}}_{\in\{0, 1, 4, 7\}}) +8\pmod{9}\big)}_{\in\{9, 1, 4, 7\}}\\\end{array}$

That is interesting. It says, that a perfect square has only four possible digital roots (1, 5, 7 and 9) and even simpler, a perfect square has four possible digits (0, 1, 4 and 7) under modulo 9.

## Improve findings over other modules

An interesting question that arises from these two findings is, can we find a better module, that covers a larger range of numbers, that is can we find a better module $$m$$ to increase the coverage and reduce the number of checks?

$n^2 \equiv k \pmod{m}$

Since the possible digits repeat quickly, a simple brute force enumeration approach can give us possible candidates:

let res = [];
for (let m = 2; m < 500; m++) {
const p = {};
for (let i = 0; i < 3000; i++) {
p[(i * i) % m] = true;
}

let k = Object.keys(pos);

if (k.length < 10)
res.push({module: m, coverage: (m - k.length) / m, candidates: k});
}

Sorting the result by coverage descending leads to the following table:

ModuleResidue ClassesCoverage
$$m=48$$0, 1, 4, 9, 16, 25, 33, 3683.3%
$$m=32$$0, 1, 4, 9, 16, 17, 2578.1%
$$m=36$$0, 1, 4, 9, 13, 16, 25, 2877.8%
$$m=40$$0, 1, 4, 9, 16, 20, 24, 25, 3677.5%
$$m=16$$0, 1, 4, 975.0%
$$m=24$$0, 1, 4, 9, 12, 1675.0%
$$m=28$$0, 1, 4, 8, 9, 16, 21, 2571.4%
$$m=20$$0, 1, 4, 5, 9, 1670.0%
$$m=12$$0, 1, 4, 966.7%
$$m=8$$0, 1, 462.5%
$$m=21$$0, 1, 4, 7, 9, 15, 16, 1861.9%
$$m=15$$0, 1, 4, 6, 9, 1060.0%
$$m=9$$0, 1, 4, 755.6%
$$m=18$$0, 1, 4, 7, 9, 10, 13, 1655.6%
$$m=4$$0, 150.0%
$$m=17$$0, 1, 2, 4, 8, 9, 13, 15, 1647.1%
$$m=13$$0, 1, 3, 4, 9, 10, 1246.2%
$$m=11$$0, 1, 3, 4, 5, 945.5%
$$m=7$$0, 1, 2, 442.9%
$$m=14$$0, 1, 2, 4, 7, 8, 9, 1142.9%
$$m=5$$0, 1, 440.0%
$$m=10$$0, 1, 4, 5, 6, 940.0%
$$m=3$$0, 133.3%
$$m=6$$0, 1, 3, 433.3%
$$m=2$$0, 10.0%

The most interesting result is module $$16$$, which has only four possible residue classes and covers $$\frac{3}{4}$$ of all numbers to give a best case performace of $$O(1)$$.

A much better improved implementation to check for perfect squares is then

function isPerfectSquare(n) {
let r = n & 15;
if (r == 0 || r == 1 || r == 4 || r == 9) {
for (let i = 0; i * i <= n; i++) {

if (i * i === n) {
return true;
}
}
}
return false;
}

Interestingly, the two previous ideas of checking the last digit and the digit root - which brought up the whole idea - does not cover that much and requires many more individual checks.

The good thing on this method is, we can add additional checks, for example for $$m=7$$ and $$m=9$$ to further increase $$O(1)$$ test coverage.

You might also be interested in the following