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

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


当前回答

有人指出,完美正方形的最后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不多,提取一个机器字将比提取一个位更快。

其他回答

你应该从一开始就去掉N的2次方部分。

第二次编辑下面m的神奇表达式应该是

m = N - (N & (N-1));

而不是书面的

第二次编辑结束

m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

第一次编辑:

轻微改进:

m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

第一次编辑结束

现在像往常一样继续。这样,当你到达浮点部分时,你已经去掉了所有2次方部分为奇数(大约一半)的数字,然后你只考虑剩下的1/8。也就是说,你在6%的数字上运行浮点部分。

我参加聚会已经很晚了,但我希望能提供一个更好的答案;更短,(假设我的基准是正确的)也更快。

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;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Each square ends with an even number of zeros.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Now x is either 0 or odd.
    // In binary each odd square ends with 001.
    // Postpone the sign test until now; handle zero in the branch.
    if ((x&7) != 1 | 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;
}

第一个测试很快捕捉到大多数非正方形。它使用一个长的64项表,因此没有数组访问成本(间接和边界检查)。对于均匀随机的长,有81.25%的概率在这里结束。

第二个测试捕获因式分解中奇数为2的所有数字。Long.numberOfTrailingZeros方法非常快,因为它被JIT编译成一条i86指令。

删除尾随零后,第三个测试处理以二进制形式的011、101或111结尾的数字,这些数字不是完美的正方形。它还关心负数,也处理0。

最后的测试是双倍算术。由于double只有53位尾数,从long到double的转换包括大值的舍入。尽管如此,测试是正确的(除非证明是错误的)。

试图结合mod255的想法并不成功。

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

如果你做了一个二进制斩试图找到“正确”的平方根,你可以很容易地检测到你得到的值是否足够接近:

(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

因此,在计算了n^2之后,选项如下:

n ^2=目标:已完成,返回truen^2+2n+1>target>n^2:你很接近,但并不完美:return falsen^2-2n+1<目标<n^2:同上目标<n^2-2n+1:低位n上的二进制斩波目标>n^2+2n+1:较高n上的二进制斩波

(抱歉,这使用n作为您当前的猜测,并将其作为参数的目标。对此感到困惑深表歉意!)

我不知道这是否会更快,但值得一试。

编辑:二进制斩不必接受整个整数范围,或者(2^x)^2=2^(2x),所以一旦你在目标中找到了最高位(这可以用一个小技巧来完成;我完全忘记了怎么做),你就可以快速得到一系列可能的答案。请注意,一个简单的二进制斩仍然只需要31或32次迭代。

整数牛顿法

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

/**
 * 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的解决方案竞争。但是,可以通过使用其他文章中描述的过滤机制来提高其性能。