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

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


当前回答

你应该从一开始就去掉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%的数字上运行浮点部分。

其他回答

这是我能想到的最快的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;
        }
    }

}

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

标签中提到了项目Euler,其中的许多问题需要检查数字>>2^64。当您使用80字节缓冲区时,上面提到的大多数优化都不容易工作。

我使用了javaBigInteger和稍微修改过的Newton方法,它对整数更有效。问题是,精确的平方n^2收敛到(n-1)而不是n,因为n^2-1=(n-1)(n+1),最终误差仅比最终除数低一步,算法终止。在计算错误之前,通过在原始参数中添加一个参数很容易解决。(为立方体根等添加两个)

这个算法的一个优点是,你可以立即判断出这个数字是否是一个完美的平方-牛顿方法中的最终误差(不是校正)将为零。一个简单的修改也可以让您快速计算floor(sqrt(x)),而不是最接近的整数。这对于几个Euler问题很方便。

不知道最快,但最简单的方法是以正常方式取平方根,将结果乘以自身,看看它是否与原始值匹配。

由于我们在这里讨论的是整数,fasted可能涉及一个集合,您可以在其中进行查找。

我不确定它是否会更快,甚至更准确,但你可以使用约翰·卡马克的神奇平方根算法来更快地解平方根。您可能很容易对所有可能的32位整数进行测试,并验证您实际上得到了正确的结果,因为这只是一个近似值。然而,现在我想起来,使用双打也是近似的,所以我不确定这会如何发挥作用。