algorithm - 完美平方算法 - 实现说明

Question

此问题是此处帖子的后续问题: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? .

那里的一个帖子有这个解决方案来查找给定数字是否是完美正方形:

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 以 r 为模除以任何整数 b (所以 K %b = r) 然后 K² 和 r² 除以 b 将得到相同的模数。

为什么？事实上，我们有:K²-r² = (K-r)(K+r) 并且 K-r 将被划分为 b 具有整数结果(因为 r 是 K 除以 b 的模数)

这就是 b=16 的原因:

r       r^2  (r^2)%160 ---->  0 ---> 01 ---->  1 ---> 12 ---->  4 ---> 43 ---->  9 ---> 94 --->  16 ---> 05 --->  25 ---> 96 --->  36 ---> 47 --->  49 ---> 18 --->  64 ---> 09 --->  81 ---> 110 --> 100 ---> 411 --> 121 ---> 912 --> 144 ---> 013 --> 169 ---> 914 --> 196 ---> 415 --> 225 ---> 1

因此，如您所见，如果 r 从完全平方的除法中导出，则模 必须 与 r^2%16 的模相同 - 因此，它可以仅 0、1、4 和9

还有一件更重要的事情:这是完美平方的必要条件，而不是足够条件(所以点是“如果模不是 0,1,4或 9，则数字不是完全平方数”，但它仍然不等于 “如果模数是 0、1、4 或 9，则数字是完全平方数” 简单示例是 17:17%16 = 1 但 17 不是完美的正方形)这就是为什么即使满足模条件，方法仍然使用

return tst*tst == n;

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