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

我使用内置的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中检查数组边界。


当前回答

如果最后的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性能不佳而取消;查看修订历史以查看。)

其他回答

如果最后的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性能不佳而取消;查看修订历史以查看。)

整数牛顿法

如果希望避免非整数运算,可以使用以下方法。它基本上使用了为整数运算而修改的牛顿法。

/**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

此实现无法与使用Math.sqrt的解决方案竞争。但是,可以通过使用其他文章中描述的过滤机制来提高其性能。

这是最简单和最简洁的方法,尽管我不知道它在CPU周期方面的比较。如果您只想知道根是否是整数,那么这非常有用。如果你真的关心它是不是整数,你也可以弄清楚。这里有一个简单(纯)函数:

private static final MathContext precision = new MathContext(20);

private static final Function<Long, Boolean> isRootWhole = (n) -> {
    long digit = n % 10;
    if (digit == 2 || digit == 3 || digit == 7 || digit == 8) {
        return false;
    }
    return new BigDecimal(n).sqrt(precision).scale() == 0;
};

如果您不需要微优化,那么这个答案在简单性和可维护性方面更好。如果要计算负数,则需要相应地处理,并将绝对值发送到函数中。我包含了一个小的优化,因为由于二次残差mod 10,没有完美的正方形具有2、3、7或8的十位数。

在我的CPU上,在0-10000000上运行此算法平均每次计算需要1000-1100纳秒。

如果执行的计算次数较少,则早期的计算需要更长的时间。

我有一个负面评论,说我以前的编辑不适用于大量数据。OP提到了Longs,Long的最大完美正方形是9223372030926249001,因此该方法适用于所有Longs。

有人指出,完美正方形的最后d位只能取某些值。数字n的最后d位(以b为基数)与n除以bd时的余数相同,即C符号n%pow(b,d)。

这可以推广到任何模数m,即n%m可以用来排除某些百分比的数字是完全平方。您当前使用的模数是64,这允许12,即19%的余数作为可能的平方。通过一点编码,我找到了模数110880,它只允许2016,即1.8%的余数作为可能的平方。因此,根据模数运算(即除法)和查找表与机器上的平方根的成本,使用这个模数可能会更快。

顺便说一句,如果Java有办法为查找表存储一个压缩的位数组,那么不要使用它。现在110880个32位字的RAM不多,提取一个机器字将比提取一个位更快。

如果你想要速度,考虑到整数的大小是有限的,我想最快的方法是(a)按大小划分参数(例如,按最大位集划分类别),然后对照该范围内的完美平方数组检查值。