完美的平方算法 - 实现的解释

Question

这个问题是在后一个后续这里:确定一个整数的平方根是一个整数的最快方法,什么是好的算法,以确定是否输入是一个完美的正方形？.

其中一个帖子有这个解决方案来查找给定的数字是否是perfect square:

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;
        }
    } 

这是一个简洁的解决方案,完美无缺.但是没有详细解释它是如何工作的,或者更重要的是如何得出这个解决方案.我想如何推导出这个解决方案.

Answer 1

虽然这个问题与编程无关，但它仍然与选择的解决方法有关。这就是为什么我会发布正确的解释。显然，这x & 0xF相当于x % 16- 即从除法到 16 取模（因为它会留下相应的位。但是，这个技巧仅适用于 2 的幂）。

该方法基于完美平方的非常重要的一点：

如果整数K除以任何b具有模数的整数r(so K%b = r)，则 K ²和 r ²除以b将得到相同的模数。

为什么？事实上，我们有： K ² -r ² = (Kr)(K+r) 并将K-r被除以b整数结果（因为除以r为模）Kb

这就是为什么b=16：

rr^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

因此，正如您所看到的，如果r是从完全平方除法得出的，则模必须与 的模相同r^2%16- 因此，它只能是 0、1、4和9

更重要的一件事：这是完全平方的必要条件，而不是充分条件（所以要点是“如果模不是 0,1,4 或 9，则数字不是完全平方”，但它仍然不等于“如果模不是完全平方” IS 0,1,4 或 9 那么数字是完全平方”简单的示例是17：17%16 = 1但 17 不是完全平方）这就是为什么即使满足模数条件，方法仍然使用

返回 tst*tst == n;

n-即通过计算平方根来测试完美平方。所以这个方法大约会快 4 倍 - 因为从r12 的 16 个可能的模我们总是可以返回false。