perfect square algorithm - explanation for the implementation
algorithm, integer, perfect-square, square-root
Solution
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 K2 and r2, divided by `b` will result in same modulo.
Why? Indeed, we have: K2-r2 = (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`.
Problem
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.