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.

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.

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.