Java中两个BigInteger的关系运算

Question

在尝试使用BINARY SEARCH方法计算BigInteger的平方根时，我在如何协调两个BigInteger以满足比较操作的问题上左右为难。比如，我想检查两个BigInteger变量之间是否存在相等、大于或小于的条件。

这是错误的一段代码，大致了解我想要执行什么。为解决这一问题所作的任何努力都将不胜感激。

public static BigInteger squareroot(BigInteger bi){
    //BigInteger bkl;
    BigInteger low,high,mid;
low=ONE;
high=bi.add(ZERO);
while(low<=high)
{
    mid =(low.add(high)).divide(new BigInteger("2"));
    if(mid.multiply(mid).equals(bi))
        return mid;
    if(mid.multiply(mid) > bi)
        high = mid -1 ;
    else
        low = mid + 1;
}
return mid;
}

Answer 1

BigIntegers是Objects，因此无法将它们的内容与关系运算符(如>(进行比较，而==不会比较内容；它将比较对象引用。

但是，BigInteger确实实现了Comparable<BigInteger>，所以改为调用compareTo。

• 对于相等，请使用left.compareTo(right) == 0
• 对于小于，请使用left.compareTo(right) < 0
• 对于大于，请使用left.compareTo(right) > 0

Answer 2

您没有正确使用BigInteger类：

1. 您可以用简单的high = bi替换high = bi.add(ZERO)
2. 比较low <= high不会针对BigInteger操作数进行编译
3. 比较mid.multiply(mid) > bi不会针对BigInteger操作数进行编译
4. 算术运算mid-1和mid+1不会针对BigInteger操作数进行编译
5. 使用CCD_ 21不是很有效；请改用shiftRight(1)

请尝试此方法：

public static BigInteger squareroot(BigInteger bi)
{
    BigInteger low  = BigInteger.ZERO;
    BigInteger high = bi;
    while (true)
    {
        BigInteger mid0 = low.add(high).shiftRight(1);
        BigInteger mid1 = mid0.add(BigInteger.ONE);
        BigInteger square0 = mid0.multiply(mid0);
        BigInteger square1 = mid1.multiply(mid1);
        if (square0.compareTo(bi) > 0)
            high = mid0;
        else if (square1.compareTo(bi) <= 0)
            low = mid1;
        else
            return mid0;
    }
}