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

我使用内置的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;

会影响性能。

其他回答

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

您的算法可能接近最佳,但在调用平方根例程之前,您可能需要快速检查以排除某些可能性。例如,通过按位“和”查看十六进制数字的最后一位。完美的正方形只能以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#代码几乎没有影响。

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

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的想法并不成功。

使用牛顿的方法计算整数平方根,然后对这个数字进行平方并进行检查,这应该快得多,就像您在当前解决方案中所做的那样。牛顿方法是其他答案中提到的卡马克解的基础。你应该能够得到更快的答案,因为你只对根的整数部分感兴趣,这样你就可以更快地停止近似算法。

另一个可以尝试的优化:如果数字的数字根不以1、4、7或9这个数字不是一个完美的正方形。这可以作为在应用较慢的平方根算法之前消除60%输入的快速方法。

这是我能想到的最快的Java实现,使用了本线程中其他人建议的技术组合。

Mod-256测试不精确的mod-3465测试(避免以某些误报为代价的整数除法)浮点平方根,舍入并与输入值比较

我也尝试了这些修改,但它们对性能没有帮助:

附加mod-255测试将输入值除以4的幂快速逆平方根(要处理高N值,需要3次迭代,足以使其比硬件平方根函数慢。)

public class SquareTester {

    public static boolean isPerfectSquare(long n) {
        if (n < 0) {
            return false;
        } else {
            switch ((byte) n) {
            case -128: case -127: case -124: case -119: case -112:
            case -111: case -103: case  -95: case  -92: case  -87:
            case  -79: case  -71: case  -64: case  -63: case  -60:
            case  -55: case  -47: case  -39: case  -31: case  -28:
            case  -23: case  -15: case   -7: case    0: case    1:
            case    4: case    9: case   16: case   17: case   25:
            case   33: case   36: case   41: case   49: case   57:
            case   64: case   65: case   68: case   73: case   81:
            case   89: case   97: case  100: case  105: case  113:
            case  121:
                long i = (n * INV3465) >>> 52;
                if (! good3465[(int) i]) {
                    return false;
                } else {
                    long r = round(Math.sqrt(n));
                    return r*r == n; 
                }
            default:
                return false;
            }
        }
    }

    private static int round(double x) {
        return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
    }

    /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
    private static final long INV3465 = 0x8ffed161732e78b9L;

    private static final boolean[] good3465 =
        new boolean[0x1000];

    static {
        for (int r = 0; r < 3465; ++ r) {
            int i = (int) ((r * r * INV3465) >>> 52);
            good3465[i] = good3465[i+1] = true;
        }
    }

}

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

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

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