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中检查数组边界。

当前回答

用牛顿法计算平方根的速度快得惊人。。。只要起始值是合理的。然而，没有合理的起始值，在实践中，我们以平分和对数（2^64）行为结束。要真正做到快速，我们需要一种快速的方法来获得一个合理的初始值，这意味着我们需要进入机器语言。如果一个处理器在奔腾中提供了一个像POPCNT这样的指令，它对前导零进行计数，我们可以使用它来获得一个具有一半有效位的起始值。小心地，我们可以找到一个固定数量的牛顿步数，这将总是足够的。（因此，前面提到了需要循环并具有非常快的执行。）

第二种解决方案是通过浮点设备，它可能具有快速的sqrt计算（如i87协处理器）。即使通过exp（）和log（）进行偏移，也可能比牛顿退化为二进制搜索更快。这有一个棘手的方面，即依赖于处理器的分析，以确定后续是否需要改进。

第三种解决方案解决了一个稍有不同的问题，但很值得一提，因为问题中描述了情况。如果你想为稍有不同的数字计算很多平方根，你可以使用牛顿迭代，如果你从来没有重新初始化起始值，但只需将其保留在之前的计算停止的地方。我已经在至少一个欧拉问题中成功地使用了这一方法。

2018-12-27 02:42:56

其他回答

如果最后的X位数字是N，那么应该可以更有效地包装“不能是完美的正方形”！我将使用java 32位int，并生成足够的数据来检查数字的最后16位，即2048个十六进制int值。

...

好吧。要么我遇到了一些超出我理解范围的数论，要么我的代码中有一个错误。无论如何，以下是代码：

public static void main(String[] args) {
    final int BITS = 16;

    BitSet foo = new BitSet();

    for(int i = 0; i< (1<<BITS); i++) {
        int sq = (i*i);
        sq = sq & ((1<<BITS)-1);
        foo.set(sq);
    }

    System.out.println("int[] mayBeASquare = {");

    for(int i = 0; i< 1<<(BITS-5); i++) {
        int kk = 0;
        for(int j = 0; j<32; j++) {
            if(foo.get((i << 5) | j)) {
                kk |= 1<<j;
            }
        }
        System.out.print("0x" + Integer.toHexString(kk) + ", ");
        if(i%8 == 7) System.out.println();
    }
    System.out.println("};");
}

结果如下：

（ed：由于pretify.js性能不佳而取消；查看修订历史以查看。）

2009-02-22 06:22:01

当观察到正方形的最后n位时，我检查了所有可能的结果。通过连续检查更多位，可以消除多达5/6的输入。我实际上是为了实现费马的因子分解算法而设计的，而且速度非常快。

public static boolean isSquare(final long val) {
   if ((val & 2) == 2 || (val & 7) == 5) {
     return false;
   }
   if ((val & 11) == 8 || (val & 31) == 20) {
     return false;
   }

   if ((val & 47) == 32 || (val & 127) == 80) {
     return false;
   }

   if ((val & 191) == 128 || (val & 511) == 320) {
     return false;
   }

   // if((val & a == b) || (val & c == d){
   //   return false;
   // }

   if (!modSq[(int) (val % modSq.length)]) {
        return false;
   }

   final long root = (long) Math.sqrt(val);
   return root * root == val;
}

伪代码的最后一位可用于扩展测试以消除更多值。上述测试针对k=0、1、2、3

a的形式为（3<<2k）-1b的形式为（2<<2k）c的形式为（2<<2k+2）-1d的形式为（2<<2k-1）*10

它首先测试它是否具有幂模为2的平方残差，然后根据最终模量进行测试，然后使用Math.sqrt进行最终测试。我从最上面的帖子中提出了这个想法，并试图扩展它。我感谢任何评论或建议。

更新：使用模数（modSq）和44352的模数基数的测试，我的测试在OP更新中的96%的时间内运行，最多可达1000000000。

2011-12-04 04:30:52

为了记录在案，另一种方法是使用素分解。如果分解的每个因子都是偶数，那么这个数就是一个完美的平方。所以你想要的是看看一个数是否可以分解成质数平方的乘积。当然，你不需要获得这样的分解，只是为了看看它是否存在。

首先建立一个小于2^32的素数平方表。这远远小于一个包含所有整数的表，直到这个极限。

解决方案如下：

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

我想这有点神秘。它所做的是在每一步中检查质数的平方除以输入数。如果这样做了，那么它将尽可能地将数字除以平方，以从素数分解中删除这个平方。如果通过这个过程，我们得到1，那么输入数是素数平方的分解。如果平方比数字本身大，那么这个平方或任何更大的平方都无法分割它，所以数字不能是素数平方的分解。

考虑到现在的sqrt是在硬件中完成的，并且需要在这里计算素数，我想这个解决方案要慢得多。但正如mrzl在他的回答中所说，它应该比sqrt的解决方案给出更好的结果，sqrt的工作时间不会超过2^54。

2008-12-02 10:00:22

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

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