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

概述这个问题是对这篇文章的后续跟进： 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 这个问题是对这篇文章的后续跟进： 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)%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的模数相同？ – 因此,它只能是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.

总结

以上是内存溢出为你收集整理的完美的平方算法 – 实现的解释全部内容，希望文章能够帮你解决完美的平方算法 – 实现的解释所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。