检查BigInteger是不是一个完美的正方形 [英] Check if BigInteger is not a perfect square

问题描述

我有一个BigInteger值，假设它是282并且在变量x中。我现在想写一个while循环，声明：

I have a BigInteger value, let's say it is 282 and is inside the variable x. I now want to write a while loop that states:

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

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

How would I do such a thing using BigInteger?

编辑：这样做的目的是为了写一个此方法。正如文章所述，必须检查b2是否不是正方形。

The purpose for this is so I can write this method. As the article states one must check if b2 is not square.

推荐答案

计算整数平方根，然后检查它的正方形是你的号码。这是我使用 Heron方法计算平方根的方法：

Compute the integer square root, then check that its square is your number. Here is my method of computing the square root using Heron's method:

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

这篇关于检查BigInteger是不是一个完美的正方形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！