完全平方数算法 - 实现解释

Question

完全平方数算法 - 实现解释

algorithmintegersquare-rootperfect-square

7

这个问题是这篇文章的后续: 确定一个整数的平方根是否为整数的最快方法, 判断输入是否为完全平方数的好算法是什么？.

其中一篇帖子提供了以下解决方法来判断给定数字是否为完全平方数:

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

这是一个很好的解决方案，完全有效。但是没有详细解释它是如何工作或更重要的是这个解决方案是如何得出的。我想知道这个解决方案是如何得出的。

- brain storm

如果一个数字是完全平方数，那么它的平方根就是一个整数。所以你只需要取平方根即可。由于浮点运算不准确，你不需要尝试检查平方根是否为整数，而是将其四舍五入到最近的整数，并检查该整数是否为你的数字的平方根。 - Niklas B.

3

似乎利用了一个完全平方数除以16后只能余下0、1、4或9的事实。数学网站可能更有资格解释为什么会这样。 - Kevin

3

@Kevin，在这种情况下，用尽所有可能性的穷举法（枚举15个情况）就足够了。请注意，平方数的个位数字只受其根号的个位数字的影响。 - cmh

2个回答

3

n & 0xF 仅选择 n 的最后4位，因为 0xF 在二进制中表示为 1111。实际上，这等价于将 n 除以16的余数。

该算法利用了完全平方数 m 的一个事实，即 m % 16 只能是 0、1、4 或 9 中的一个。可以证明如下:

任何自然数 n 都可以表示为 4k、4k+1、4k+2 或 4k+3（对于某个自然数 k）。

那么，n^2 可以是 (4k)^2、(4k+1)^2、(4k+2)^2 或 (4k+3)^2。 => n^2 可以是 16k^2、16k^2+8k+1、16k^2+16k+4 或 16k^2+24k+9。

如果 n^2 是 16k^2，则 n^2 % 16 显然为 0。

如果 n^2 是 16k^2+8k+1，则 n^2 % 16 = (8k+1) % 16 = (8k % 16) + 1 = 0 或 9，具体取决于 k 是偶数还是奇数。

如果 n^2 是 16k^2+16k+4，则 n^2 % 16 = 4。

如果 n^2 是 16k^2+24k+9，则 n^2 % 16 = (24k+9) % 16 = (16k+8k+9) % 16 = 1 或 9，具体取决于 k 是奇数还是偶数。

因此，n^2 % 16 只能是 0,1,4 或 9。

- Hari Menon

你忘记展示16k^2+16k+4 % 16 = 4了。因此，你的答案应该是n^2 % 16只能是0、1、4或9。 - Z boson

对于情况 n^2 是 16k^2+8k+1，它不应该是 1 或 9 吗？ - sequence

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alma Do · Accepted Answer

虽然这个问题不是关于编程的，但它仍与选择的解决方法有关。这就是为什么我会发布正确的解释。显然，x & 0xF只是等价于x % 16——即除以16后取余数（因为它将保留相应的位）。然而，这个技巧仅适用于2的幂次方。

这种方法基于完全平方数的一个非常重要的事实： 如果整数K被除以任何整数b并且模数为r（因此K％b=r），则K^2和r^2除以b的余数将导致相同的模数。 为什么呢？实际上，我们有：K²-r² = (K-r)(K+r)，而K-r将被整数结果除以b（因为r是K除以b的模数）。

这就是为什么对于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

因此，正如您所看到的，如果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。