perfect square algorithm - explanation for the implementation

Question

This question is a follow-up on the post here: Fastest way to determine if an integer's square root is an integer, What's a good algorithm to determine if an input is a perfect square?.

One of the posts there had this solution to find if a given number is a perfect square or not:

public final static boolean isPerfectSquare(long n)
    {
        if (n < 0)
            return false;

        switch((int)(n & 0xF))
        {
        case 0: case 1: case 4: case 9:
            long tst = (long)Math.sqrt(n);
            return tst*tst == n;

        default:
            return false;
        }
    } 

This is a neat solution and works perfectly fine. but no explanation on how it works or more importantly how this solution is derived was not explained in detail. I would like to how this solution is being derived.

Lamia

If a number is a perfect square, it's square root is an integer. So you just take the square root. Since floating arithmetics is inaccurate, you don't try to check whether the square root is integer, you just round it to the nearest integer and check whether that integer is the square root of your number. – Razorbill

This appears to take advantage of the fact that a perfect square divided by 16 can only have 0, 1, 4, or 9 as a remainder. The Mathematics site may be more qualified in explaining why this is the case. – Indulgence

@Kevin, in this case a proof by exhaustion (enumerating all 15 cases) will more than suffice. Note that the least significant digit of the square is only effected by the least significant digit of its root. – Cimabue

Answer 1

While this question isn't about programming directly, it still is related to chosen solution method. That's why I'll post correct explanation. Obviously, that x & 0xF is just equivalent of x % 16 - i.e. modulo from division to 16 (since is will leave the corresponding bits. This trick, however, works only with powers of 2).

This method is based on very important thing about perfect square:

If integer number K is divided to any integer number b with modulo r (so K%b = r) then K² and r², divided by b will result in same modulo.

Why? Indeed, we have: K²-r² = (K-r)(K+r) and K-r will be divided to b with integer result (since r is modulo for K divided to b)

That's why for b=16:

r       r^2  (r^2)%16
0 ---->  0 ---> 0
1 ---->  1 ---> 1
2 ---->  4 ---> 4
3 ---->  9 ---> 9
4 --->  16 ---> 0
5 --->  25 ---> 9
6 --->  36 ---> 4
7 --->  49 ---> 1
8 --->  64 ---> 0
9 --->  81 ---> 1
10 --> 100 ---> 4
11 --> 121 ---> 9
12 --> 144 ---> 0
13 --> 169 ---> 9
14 --> 196 ---> 4
15 --> 225 ---> 1

So, as you can see, if r is derived from division of perfect square, then modulo must be same as modulo of r^2%16 - thus, it can be only 0, 1, 4 and 9

One more important thing: this is necessary condition for perfect square and not enough condition (so point is "If modulo is NOT 0,1,4 or 9, then number is NOT perfect square", but still it's not equal to "If modulo IS 0,1,4 or 9 then number IS perfect square" Easy sample is 17: 17%16 = 1 but 17 is NOT perfect square) That's why even with fulfilled modulo condition, method still uses

return tst*tst == n;

-i.e. testing that n is perfect square by calculating it's square root. So this method will be faster approximately in 4 times - since from 16 possible modulos r for 12 we can always return false.

Avoidance

This reminds me vaguely of Wheel factorization with prime numbers. It's a quick way to eliminate prime candidates which are not prime. en.wikipedia.org/wiki/Wheel_factorization. – Landbert

It may be used for that, yes (in fact it is). Actually, Case with factorization also relies on necessary condition (it still isn't enough, obviously) – Avoidance

Answer 2

n & 0xF just picks the last 4 bits of n, since 0xF is 1111 in binary. Effectively, it is equivalent to getting the remainder when n is divided by 16.

This algorithm makes use of the fact that for a perfect square m, m % 16 can only be one of 0, 1, 4 or 9. It can be proved as follows:

Any natural number n can be represented as 4k, 4k+1, 4k+2 or 4k+3 (for some natural number k).

Then, n^2 can be (4k)^2, (4k+1)^2, (4k+2)^2 or (4k+3)^2. => n^2 can be 16k^2, 16k^2+8k+1, 16k^2+16k+4 or 16k^2+24k+9.

If n^2 is 16k^2, n^2 % 16 is clearly 0.

If n^2 is 16k^2+8k+1, n^2 % 16 = (8k+1) % 16 = (8k % 16) + 1 = 0 or 9, depending on whether k is even or odd.

If n^2 is 16k^2+16k+4, n^2 % 16 = 4.

If n^2 is 16k^2+24k+9, n^2 % 16 = (24k+9) % 16 = (16k+8k+9) % 16 = 1 or 9 depending on whether k is odd or even.

Therefore, n^2 % 16 can only be 0,1, 4 or 9.

Annamariaannamarie

You forgot to show 16k^2+16k+4 % 16 = 4. So your answer should be Therefore, n^2 % 16 can only be 0,1 4, or 9. – Landbert

For the case n^2 is 16k^2+8k+1, shouldn't it be either 1 or 9? – Waylen