确定整数的平方根是否为整数的最快方法是什么？

一种最快地确定一个整数的平方根是否为整数的方法

问题说明

我正在寻找最快的方法来确定一个长整数是否是一个完全平方（即它的平方根是另一个整数）：

1. 我使用内置的 Math.sqrt() 函数完成了它，但我很好奇是否有一种方法可以使用整数域来完成，从而提高速度。


2. 维护一个查找表是不切实际的（因为有大约 2^31.5 个整数的平方小于 2⁶³）。

以下是我现在完成它的非常简单直接的方法：

public final static boolean isPerfectSquare(long n)<br>{<br>  if (n < 0)</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">return false;

登录后复制

long tst = (long)(Math.sqrt(n) 0.5);
return tst*tst == n;
}

_{注意：我在许多 Project Euler 问题中使用了这个函数。因此，以后将不会对这一段代码进行任何维护。并且这种微型优化实际上可以带来差异，因为挑战的一部分是用不到一分钟的时间完成每个算法，而此函数需要在某些问题中被调用数百万次。}

---

我已经尝试了解决这个问题的不同方案：

• 经过详尽的测试，我发现向 Math.sqrt() 的结果添加 0.5 is 不必要的，至少在我的机器上是这样。


• 快速反平方根比 Math.sqrt() 快，但对于 n >= 410881 给出了不正确的结果。然而，正如 BobbyShaftoe 所建议的，我们可以为 n < 410881 使用 FISR hack。


• Newton's 方法比 Math.sqrt() 慢很多。这可能是因为 Math.sqrt() 使用类似于 Newton 方法的东西，但是在硬件中实现，因此比 Java 中的速度快得多。此外，Newton 方法仍然需要使用双精度浮点数。


• 一种经过改进的 Newton 方法，它利用了一些技巧，使其只需要进行整数运算，在避免溢出时也需要一些技巧（我希望该函数可以处理所有正的 64 位有符号整数），而且它比 Math.sqrt() 慢。


• 二分查找甚至更慢。这是有道理的，因为二分查找平均需要进行 16 次传递才能找到 64 位数字的平方根。


• 根据 John 的测试，在 C 中使用或语句比使用开关速度更快，但在 Java 和 C# 中，或和开关之间似乎没有区别。


• 我还尝试制作一个查找表（作为 64 个布尔值的私有静态数组）。然后，不是使用 switch 或 or 语句，我会直接说 if(lookup[(int)(n&0x3F)]) { test } else return false;. 令我惊讶的是，这(略微)慢了一些。这是因为数组边界在 Java 中是受检的。

以上是确定整数的平方根是否为整数的最快方法是什么？的详细内容。更多信息请关注PHP中文网其他相关文章！