首页 文章

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

提问于
浏览 次
5

这个问题是对这篇文章的后续跟进：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? .

其中一个帖子有这个解决方案来查找给定的数字是否为 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;
        }
    }

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

algorithm integer square-root perfect-square

2 回答

  • 3

    虽然这个问题不是为什么我会发布正确的解释 . 显然， x & 0xF 只相当于 x % 16 - 即从除法到16的模数（因为它将留下相应的位 . 但是，这个技巧仅适用于2的幂） .

    这个方法基于完美方块非常重要：

    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.

    为什么？实际上，我们有：K2-r2 =（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 是从完美平方的除法得出的，那么模 must 与 r^2%16 的模数相同 - 因此，它可以是 only 0 ， 1 ， 4 和 9

    更重要的是：这是完美方形的 necessary 条件而不是 enough 条件（所以点是"If modulo is NOT 0,1,4 or 9, then number is NOT perfect square"，但它仍然不等于"If modulo IS 0,1,4 or 9 then number IS perfect square"简易样本是 17 ： 17%16 = 1 但是17不是完美的正方形）这就是为什么即使满足模数条件，方法仍然使用

    return tst * tst == n;

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

    回复于
  • 2

    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 or 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 or 9 ，具体取决于k是奇数还是偶数 .

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

    回复于

相关问题