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

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


当前回答

sqrt调用并不完全准确,正如前面所提到的,但它很有趣,也很有启发性,因为它不会在速度方面影响其他答案。毕竟,sqrt的汇编语言指令序列很小。英特尔有一个硬件指令,我相信Java不会使用它,因为它不符合IEEE。

那么为什么速度慢呢?因为Java实际上是通过JNI调用一个C例程,而且这样做实际上比调用一个Java子程序慢,而Java子程序本身比内联调用慢。这很烦人,Java本应该想出更好的解决方案,即在必要时构建浮点库调用。哦,好吧。

在C++中,我怀疑所有复杂的替代方案都会失去速度,但我还没有检查过它们。我所做的,也是Java人会发现有用的,是一个简单的黑客,是a.Rex建议的特例测试的扩展。使用单个长值作为位数组,不检查边界。这样,您就有了64位布尔查找。

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1=" << pp1 << "," << pp2 << "\n";  
}


inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

在我的core2双人游戏机上,PerfectSquare5的程序运行时间约为1/3。我怀疑,沿着相同的路线进一步调整可能会进一步缩短平均时间,但每次检查时,你都在用更多的测试来换取更多的消除,所以你不能在这条路上走得太远。

当然,你可以用同样的方法检查高6位,而不是单独测试阴性。

请注意,我所做的只是消除可能的正方形,但当我有一个潜在的情况时,我必须调用原始的内联的isPerfectSquare。

init2例程被调用一次以初始化pp1和pp2的静态值。请注意,在我的C++实现中,我使用的是无符号long-long,因此,既然有符号,就必须使用>>>运算符。

没有内在的必要对数组进行边界检查,但Java的优化器必须很快地解决这一问题,所以我不怪他们。

其他回答

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

答案令人印象深刻,但我没有看到一个简单的检查:

检查长右边的第一个数字是否为集合的成员(0,1,4,5,6,9)。如果不是,那么它不可能是一个“完美的正方形”。

eg.

4567-不能是完美的正方形。

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

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

你必须做一些基准测试。最佳算法将取决于输入的分布。

您的算法可能接近最佳,但在调用平方根例程之前,您可能需要快速检查以排除某些可能性。例如,通过按位“和”查看十六进制数字的最后一位。完美的正方形只能以0、1、4或9结尾,以16为底。因此,对于75%的输入(假设它们是均匀分布的),可以避免调用平方根,以换取一些非常快的位旋转。

Kip对实现十六进制技巧的以下代码进行了基准测试。当测试数字1到100000000时,此代码的运行速度是原始代码的两倍。

public final static boolean isPerfectSquare(long n)
{
    if (n < 0)
        return false;

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

当我在C++中测试类似的代码时,它实际上比原始代码运行得慢。然而,当我消除switch语句时,十六进制技巧再次使代码速度提高了一倍。

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

消除switch语句对C#代码几乎没有影响。

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

然后我记得,在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乘法运算),并用一些固定数量的乘法运算代替。