检查 BigInteger 是否不是完全平方数

Question

我有一个 BigInteger 值，假设它是 282 并且位于变量 x 内。我现在想编写一个 while 循环，其中指出：

while b2 isn't a perfect square:
    a ← a + 1
    b2 ← a*a - N
endwhile

我如何使用 BigInteger 来做这样的事情？

编辑：这样做的目的是让我可以编写此方法。正如文章所述，必须检查 b2 是否不是平方。

Answer 1

我发现使用了 sqrt 方法这里< /a>，并简化了平方测试。

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;
}

Answer 2

public static Boolean PerfectSQR(BigInteger A){BigInteger B=A.sqrt(), C=B.multiply(B);return (C.equals(A));}

Answer 3

不要使用这个...

 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 在下面评论的那样 - 这不起作用。我很抱歉发布错误的答案。

Answer 4

using System.Numerics; // needed for BigInteger

/* Variables */
BigInteger a, b, b2, n, p, q;
int flag;

/* Assign Data */
n = 10147;
a = iSqrt(n);

/* Algorithm */
do
{   a = a + 1;
    b2 = (a * a) – n;
    b = iSqrt(b2);
    flag = BigInteger.Compare(b * b, b2);
} while(flag != 0);

/* Output Data */
p = a + b;
q = a – b;


/* Method */
    private static BigInteger iSqrt(BigInteger num)
    { // Finds the integer square root of a positive number            
        if (0 == num) { return 0; }     // Avoid zero divide            
        BigInteger n = (num / 2) + 1;   // Initial estimate, never low            
        BigInteger n1 = (n + (num / n)) / 2;
        while (n1 < n)
        {   n = n1;
            n1 = (n + (num / n)) / 2;
        }
        return n;
    } // end iSqrt()

Answer 5

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;
}

我使用 JavaScript BigInt 尝试了上述操作：

function isPerfectSqrt(n, root) {
  const lowerBound = root**2n;
  const upperBound = (root+1n)**2n
  return lowerBound <= n && n < upperBound;
}

发现它的速度（在 Node V8 中）仅比单行代码快 60% 左右：

function isPerfectSqrt(n, root) {
  return (n/root === root && n%root === 0n)
}

Answer 6

您想要进行完全平方检验的数字是 A。B 是 A 的整数平方根，.sqrt() 函数返回平方根的整数下限。返回 B*B=A 的布尔值。如果它是完全平方数，则布尔返回为“true”；如果不是完全平方，则返回“false”。

public static Boolean PerfectSQR(BigInteger A) {
    BigInteger B = A.sqrt();
    return B.multiply(B).equals(A);
}

另一种方法是使用 sqrtAndRemainder() 函数。如果余数 B[1] 为零，则它是完全平方数。然后返回布尔值 TRUE，如下所示。

public static Boolean PerfectSQR(BigInteger A) {
    BigInteger [] B=A.sqrtAndRemainder();
    return B[1].equals(BigInteger.ZERO);
}

Answer 7

计算整数平方根，然后检查它的平方是否是您的数字。这是我使用 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, i.e. 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;
}