8

私は BigInteger 値を持っています。それが 282 で、変数 x 内にあるとしましょう。次のように while ループを書きたいと思います。

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

BigInteger を使用してそのようなことを行うにはどうすればよいですか?

編集:これの目的は、このメソッドを記述できるようにすることです。記事に記載されているように、b2 が正方形でないかどうかを確認する必要があります。

4

7 に答える 7

12

整数の平方根を計算し、その平方根が自分の数であることを確認します。ヘロンの方法を使用して平方根を計算する方法は次のとおりです。

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;
}
于 2010-04-21T18:45:50.467 に答える
2

ここで使用されている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;
}
于 2010-04-21T18:54:14.963 に答える
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
 }

Christian Semrauが以下にコメントしたように、これは機能しません。間違った答えを投稿してすみません。

于 2010-04-21T18:55:30.617 に答える