Determine if a number is a perfect square

Verifying whether a number is a perfect square becomes a trivial task with the availability of a square root function; squaring the floored square root should yield the original number:

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

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

function isPerfectSquare(n) {

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

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

Babylonian Method

The intuitive algorithm is already quite fast in practice, but we can utilize the Babylonian Method for square root finding to check if a number is a perfect square. The idea is that we can express our number \(n\) as \(m\cdot\frac{n}{m}\) and on the other hand also as \(\sqrt{n}\cdot\sqrt{n}\), from which follows that if \(m<\sqrt{n}\), then \(\frac{n}{m}>\sqrt{n}\) and if \(m>\sqrt{n}\), then \(\frac{n}{m}<\sqrt{n}\). This way we have one upper estimate that is too big and one lower estimate that is too small for our real \(\sqrt{n}\), so we simply take the average of those and form an iterative process:

\[m_{k+1} = \frac{m_k + n / m_k}{2}\]

It is obvious that by halfing on each iteration, the error towards the real square root gets also halfed as well, forming an \(O(\log(n))\) algorithm:

function isPerfectSquare(n) {

  let m = n;
  while (m * m > n) {
    m = (m + n / m) >> 1;
  }
  return m * m === n;
}

Please note, the division is actually an integer division, but we utilize JavaScripts implicit cast with the right shift to avoid an additional call. However, we can go even further as 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(\log{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:

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 performance of \(O(1)\).

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

function isPerfectSquare(n) {
  let m = n & 15;

  if (m !== 0 && m !== 1 && m !== 4 && m !== 9) {
    return false;
  }

  for (m = n; m * m > n; ) {
    m = (m + n / m) >> 1;
  }
  return m * m === n;
}

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.