极客观点
项目管理
HarmonyOS
我正在寻找最快的方法来确定 long 值是否是一个完美的平方（即它的平方根是另一个整数）：
- 我已经通过使用内置的
Math.sqrt()函数以简单的方式完成了它，但我想知道是否有一种方法可以通过将自己限制在仅整数域来更快地完成它。 - 维护查找表是不切实际的（因为大约有 2 31.5个整数的平方小于 2 63 ）。
这是我现在做的非常简单直接的方法：
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
注意：我在许多 Project Euler 问题中都使用了这个函数。因此没有其他人需要维护此代码。这种微优化实际上可能会有所作为，因为部分挑战是在不到一分钟的时间内完成每个算法，并且在某些问题中需要调用此函数数百万次。
我已经尝试了不同的解决方案来解决这个问题：
- 经过详尽的测试，我发现将
0.5添加到 Math.sqrt() 的结果是没有必要的，至少在我的机器上不是这样。 - 快速平方根反比 更快，但它给出了 n >= 410881 的不正确结果。但是，正如 BobbyShaftoe 所建议的，我们可以对 n < 410881 使用 FISR hack。
- 牛顿法比
Math.sqrt()慢一点。这可能是因为Math.sqrt()使用了类似于牛顿法的方法，但在硬件中实现，因此它比 Java 快得多。此外，牛顿法仍然需要使用双打。 - 修改后的牛顿法，它使用了一些技巧，因此只涉及整数数学，需要一些技巧来避免溢出（我希望这个函数适用于所有正 64 位带符号整数），而且它仍然比
Math.sqrt()。 - 二进制印章甚至更慢。这是有道理的，因为二进制印章平均需要 16 遍才能找到 64 位数字的平方根。
- 根据 John 的测试，在 C++ 中使用
or语句比使用switch更快，但在 Java 和 C# 中orswitchb-ff-7 和---。 - 我还尝试制作一个查找表（作为 64 个布尔值的私有静态数组）。然后而不是 switch 或
or声明，我只想说if(lookup[(int)(n&0x3F)]) { test } else return false;。令我惊讶的是，这（只是稍微）慢了。这是因为 在 Java 中检查了数组边界。
原文由 Kip 发布，翻译遵循 CC BY-SA 4.0 许可协议
java
我找到了一种比你的 6bits+Carmack+sqrt 代码快 35% 的方法，至少对于我的 CPU (x86) 和编程语言 (C/C++) 是这样。您的结果可能会有所不同，尤其是因为我不知道 Java 因素将如何发挥作用。
我的方法有三个：
int64 x。）为了实际检查留数是否为正方形，我在预先计算的表格中查找答案。
此时，要使我们的数字成为正方形，它必须是 1 mod 8。
这个想法是，在每次迭代中，您将一位添加到 r，即 x 的“当前”平方根；每个平方根都是精确的模数越来越大的 2 次方，即 t/2。最后，r 和 t/2-r 将是 x 模 t/2 的平方根。 （请注意，如果 r 是 x 的平方根，那么 -r 也是。这甚至是模数，但要注意，对某些数字进行模数，事物的平方根甚至可能超过 2；值得注意的是，这包括 2 的幂。 ) 因为我们的实际平方根小于 2^32，此时我们实际上可以检查 r 或 t/2-r 是否为实平方根。在我的实际代码中，我使用了以下修改后的循环：
这里的加速是通过三种方式获得的：预先计算的起始值（相当于循环的 ~10 次迭代）、提前退出循环以及跳过一些 t 值。对于最后一部分，我查看了
z = r - x * x，并使用一个小技巧将 t 设置为 2 除以 z 的最大幂。这使我可以跳过无论如何都不会影响 r 值的 t 值。在我的例子中，预先计算的起始值挑选出“最小正数”平方根模 8192。即使这段代码对您来说运行得不是更快，我也希望您喜欢它包含的一些想法。完整的、经过测试的代码如下，包括预先计算的表格。