检查BigInteger是不是一个完美的正方形
我有一个BigInteger值，假设它是282并且在变量x内。 我现在想写一个while循环，声明：
while b2 isn't a perfect square: a ← a + 1 b2 ← a*a - N endwhile 我如何使用BigInteger做这样的事情？
编辑：这样做的目的是我可以写这个方法 。 正如文章所述，必须检查b2是否不是正方形。
计算整数平方根，然后检查其正方形是否为数字。 这是我使用Heron方法计算平方根的方法 ：
private static final BigInteger TWO = BigInteger.valueOf(2); /** * Computes the integer square root of a number. * * @param n The number. * * @return The integer square root, ie the largest number whose square * doesn't exceed n. */ public static BigInteger sqrt(BigInteger n) { if (n.signum() >= 0) { final int bitLength = n.bitLength(); BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2); while (!isSqrt(n, root)) { root = root.add(n.divide(root)).divide(TWO); } return root; } else { throw new ArithmeticException("square root of negative number"); } } private static boolean isSqrt(BigInteger n, BigInteger root) { final BigInteger lowerBound = root.pow(2); final BigInteger upperBound = root.add(BigInteger.ONE).pow(2); return lowerBound.compareTo(n) <= 0 && n.compareTo(upperBound) < 0; }
我在这里找到了一个sqrt方法，并简化了平方测试。
private static final BigInteger b100 = new BigInteger("100"); private static final boolean[] isSquareResidue; static{ isSquareResidue = new boolean[100]; for(int i =0;i<100;i++){ isSquareResidue[(i*i)%100]=true; } } public static boolean isSquare(final BigInteger r) { final int y = (int) r.mod(b100).longValue(); boolean check = false; if (isSquareResidue[y]) { final BigInteger temp = sqrt(r); if (r.compareTo(temp.pow(2)) == 0) { check = true; } } return check; } public static BigInteger sqrt(final BigInteger val) { final BigInteger two = BigInteger.valueOf(2); BigInteger a = BigInteger.ONE.shiftLeft(val.bitLength() / 2); BigInteger b; do { b = val.divide(a); a = (a.add(b)).divide(two); } while (a.subtract(b).abs().compareTo(two) >= 0); return a; }
我用这个：
SQRPerfect是我要测试的数字：这也有一个很好的Square Root，所以如果你需要它也可以使用它。 如果你将Square Root带入Perfect Square测试，你可以加快一点，但我喜欢这两个function。
if(PerfectSQR(SQRPerfect)){ Do Something } public static Boolean PerfectSQR(BigInteger A) { Boolean p=false; BigInteger B=SQRT(A); BigInteger C=B.multiply(B); if (C.equals(A)){p=true;} return p; } public static BigInteger SQRT(BigInteger A) { BigInteger a=BigInteger.ONE,b=A.shiftRight(5).add(BigInteger.valueOf(8)); while ((b.compareTo(a))>=0){ BigInteger mid = a.add(b).shiftRight(1); if (mid.multiply(mid).compareTo(A)>0){b=mid.subtract(BigInteger.ONE);} else{a=mid.add(BigInteger.ONE);} } return a.subtract(BigInteger.ONE); }
不要用这个……
BigInteger n = ...; double n_as_double = n.doubleValue(); double n_sqrt = Math.sqrt(n_as_double); BigInteger n_sqrt_as_int = new BigDecimal(n_sqrt).toBigInteger(); if (n_sqrt_as_int.pow(2).equals(n)) { // number is perfect square }
正如Christian Semrau在下面评论的那样 – 这不起作用。 我很抱歉发布了错误的答案。