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

发布时间：2020-12-14 01:01:24 所属栏目：Linux 来源：网络整理

导读：这个问题是对这篇文章的后续跟进： 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?. 其中一个帖子有这个解决方案来查找给定数字是否是完美的正方形： publi

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

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

解决方法

虽然这个问题不是直接编程,但它仍然与选择的解决方法有关.这就是为什么我会发布正确的解释.显然,x& 0xF只相当于x％16 – 即从除法到16的模数(因为它将留下相应的位.然而,这个技巧仅适用于2的幂).

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

如果整数K被除以具有模r的任何整数b(因此K％b = r)那么K2和r2除以b将导致相同的模.

为什么？实际上,我们得到：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是从完美平方的除法得出的,那么模数必须与r ^ 2的模数相同？ – 因此,它只能是0,1,4和9

更重要的是：这是完美正方形和不充分条件的必要条件(所以点是“如果模数不是0,4或9,那么数字不是完美的正方形”,但它仍然不等于“If modulo” IS 0,4或9然后编号IS完美正方形“简易样本是17:17？= 1但是17不是完美的正方形”这就是为什么即使满足模数条件,方法仍然使用

return tst*tst == n;

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!