Code
2023-03-20 10:00:03

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

我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法：

我使用内置的Math.sqrt（）以简单的方式完成了这项工作函数，但我想知道是否有一种方法可以通过将自己限制为仅限整数的域。维护查找表是不切实际的（因为平方小于263的231.5个整数）。

下面是我现在做的非常简单明了的方法：

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问题中都使用了这个函数。因此，其他人将永远不必维护此代码。而这种微优化实际上可能会有所不同，因为挑战的一部分是在不到一分钟的时间内完成每一个算法，而在某些问题中，这个函数需要调用数百万次。

我尝试了不同的解决方案：

经过详尽的测试，我发现不需要在Math.sqrt（）的结果上加0.5，至少在我的机器上是这样。快速平方根逆运算速度更快，但对于n>=410881，它给出了错误的结果。然而，正如BobbyShaftoe所建议的，我们可以在n<410881时使用FISR黑客。牛顿的方法比Math.sqrt（）慢得多。这可能是因为Math.sqr（）使用了类似于牛顿方法的东西，但在硬件中实现，所以比Java快得多。此外，牛顿法仍然需要使用双精度。一个经过修改的牛顿方法使用了一些技巧，因此只涉及整数数学，需要一些技巧来避免溢出（我希望这个函数可以处理所有64位有符号的正整数），而且它仍然比math.sqrt（）慢。二元斩更慢。这是有意义的，因为二进制斩波平均需要16次才能找到64位数字的平方根。根据John的测试，在C++中使用or语句比使用switch更快，但在Java和C#中，or和switch之间似乎没有区别。我还尝试创建一个查找表（作为64个布尔值的私有静态数组）。然后，我只说if（lookup[（int）（n&0x3F）]）｛test｝else return false；，而不是switch或or语句；。令我惊讶的是，这（只是稍微）慢了一些。这是因为在Java中检查数组边界。

当前回答

maartinus解决方案的以下简化似乎使运行时减少了几个百分点，但我在基准测试方面做得不够好，无法产生我可以信任的基准：

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

值得检查的是，如何省略第一次测试，

if (goodMask << x >= 0) return false;

会影响性能。

2014-07-13 10:17:15

其他回答

整数问题需要整数解。因此

对（非负）整数进行二进制搜索，以找到最大的整数t，使t**2<=n。然后测试r**2=n是否精确。这需要时间O（log n）。

如果你不知道如何对正整数进行二进制搜索，因为集合是无界的，这很容易。首先计算二次幂的递增函数f（高于f（t）=t**2-n）。当你看到它变为正值时，你已经找到了一个上限。然后可以进行标准的二进制搜索。

2013-10-15 15:48:34

我在想我在数值分析课程中度过的可怕时光。

然后我记得，在Quake源代码中，有一个函数围绕着“网络”旋转：

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

它基本上使用牛顿近似函数（记不清确切的名字）计算平方根。

它应该是可用的，甚至可能更快，它来自一个非凡的id软件的游戏！

它是用C++编写的，但一旦你有了这样的想法，在Java中重用同样的技术应该不会太难：

我最初在以下位置找到它：http://www.codemaestro.com/reviews/9

牛顿的方法在维基百科上解释：http://en.wikipedia.org/wiki/Newton%27s_method

您可以通过链接了解更多的工作原理，但如果您不太在意，那么这大概是我在阅读博客和参加数值分析课程时所记得的：

*（long*）&y基本上是一个快速转换为long的函数，因此整数运算可以应用于原始字节。0x5f3759df-（i>>1）；line是近似函数的预先计算的种子值。*（float*）-i将值转换回浮点。y=y*（three-half-（x2*y*y））行基本上再次迭代函数上的值。

在结果上迭代函数的次数越多，逼近函数给出的值就越精确。在Quake的案例中，一次迭代“足够好”，但如果不是为了你。。。然后您可以添加所需的迭代次数。

这应该更快，因为它减少了在简单平方根中执行的除法运算的数量（实际上是一个*0.5F乘法运算），并用一些固定数量的乘法运算代替。

2008-11-17 13:50:19

我喜欢对一些输入使用几乎正确的方法。这是一个“偏移”更高的版本。代码似乎有效，并通过了我的简单测试用例。

只需替换您的：

if(n < 410881L){...}

使用此代码：

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}
2009-05-25 01:22:28

如果速度是一个问题，为什么不将最常用的一组输入及其值划分到一个查找表中，然后执行您针对特殊情况提出的任何优化魔术算法？

2008-11-17 23:29:58

这个问题让我很疑惑，所以我做了一些简单的编码，我在这里介绍它，因为我觉得它很有趣，很相关，但我不知道它有多有用。有一个简单的算法

a_n+1 = (a_n + x/a_n)/2

用于计算平方根，但它用于小数。我想知道，如果我只是用整数数学编码相同的算法，会发生什么。它甚至会汇聚到正确的答案上吗？我不知道，所以我写了一个程序。。。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>

_Bool isperfectsquare(uint64_t x, uint64_t *isqrtx) {
  // NOTE: isqrtx approximate for non-squares. (benchmarked at 162ns 3GHz i5)
  uint32_t i;
  uint64_t ai;
  ai = 1 + ((x & 0xffff000000000000) >> 32) + ((x & 0xffff00000000) >> 24) + ((x & 0xffff0000) >> 16);
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = (ai + x/ai)/2;
  ai = ai & 0xffffffff;
  if (isqrtx != NULL) isqrtx[0] = ai;
  return ai*ai == x;
}

void main() {

  uint64_t x, isqrtx;
  uint64_t i;
  for (i=1; i<0x100000000; i++) {
    if (!isperfectsquare(i*i, &isqrtx)) {
      printf("Failed at %li", i);
      exit(1);
    }
  }
  printf("All OK.\n");
}

因此，事实证明，该公式的12次迭代足以为所有64位无符号长整数（完美平方）提供正确的结果，当然，非平方将返回false。

simon@simon-Inspiron-N5040:~$ time ./isqrt.bin 
All OK.

real    11m37.096s
user    11m35.053s
sys 0m0.272s

因此697s/2^32约为162纳秒。实际上，该函数对于所有输入都具有相同的运行时。讨论中其他地方详细介绍的一些措施可以通过检查最后四位等来加快非正方形的速度。希望有人像我一样觉得这很有趣。

2022-11-12 20:13:04

推荐文章

aliyun

最新文章

标签

2025 code 京ICP备15047053号-1