我有一个 BigInteger 值，假设它是 282，并且在变量 x 内。我现在想写一个 while 循环来说明：
while b2 isn't a perfect square:
a ← a + 1
b2 ← a*a - N
endwhile
我将如何使用 BigInteger 做这样的事情？
编辑：这样做的目的是让我可以编写这个方法。正如文章所述，必须检查 b2 是否不是正方形。
问问题
7093 次
7 回答
12
计算整数平方根，然后检查它的平方是你的数字。这是我使用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;
}
于 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 回答
1
public static Boolean PerfectSQR(BigInteger A){BigInteger B=A.sqrt(), C=B.multiply(B);return (C.equals(A));}
于 2017-09-15T07:02:54.173 回答
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 回答
0
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()
于 2019-08-11T17:49:15.947 回答
0
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)
}
于 2019-11-16T17:41:32.250 回答
0
您要对其进行完美平方测试的数字是 A。B 是 A 的整数平方根，.sqrt() 函数返回平方根的整数下限。返回 B*B=A 的布尔值。如果它是一个完美的正方形，则布尔返回为“真”，如果它不是一个完美的正方形，则返回“假”。
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);
}
于 2021-06-22T09:36:05.557 回答