Я сделал, чтобы BigInteger оценил, скажем, это 282 и в переменной x. Я теперь хочу записать некоторое время цикл, который указывает:
while b2 isn't a perfect square:
a ← a + 1
b2 ← a*a - N
endwhile
Как я сделал бы такую вещь использование BigInteger?
Править: Цель для этого так, я могу записать этот метод. Поскольку в статье говорится, что нужно проверить, не является ли b2 квадратным.
Вычислите квадратный корень целого числа, затем убедитесь, что его квадрат - это ваше число. Вот мой метод вычисления квадратного корня с использованием метода Герона :
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 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
}
Как прокомментировал ниже Кристиан Семрау - это не работает. Прошу прощения за неправильный ответ.
Я нашел метод 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;
}