Relational Operation on two BigIntegers in Java

Question

While trying to compute the square root of a BigInteger using BINARY SEARCH method,I was stuck in between as to how to comapre two BigIntegers for satisfying comparison operation. Like, I wanted to check for equality,greater than or lesser than conditions between two BigInteger variables.

Here is the wrong piece of code with rough idea of as to what I want to perform.Any efforts to resolve the issue would be appreciated.

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 are Objects so you cannot compare their contents with relational operators such as >, and == won't compare contents; it will compare object references.

However, BigInteger does implement Comparable<BigInteger>, so call compareTo instead.

• For equality, use left.compareTo(right) == 0.
• For less than, use left.compareTo(right) < 0.
• For greater than, use left.compareTo(right) > 0.

Answer 2

You are not using the BigInteger class correctly:

1. You can replace high = bi.add(ZERO) with a simple high = bi.
2. The comparison low <= high will not compile for BigInteger operands.
3. The comparison mid.multiply(mid) > bi will not compile for BigInteger operands.
4. The arithmetic operations mid-1 and mid+1 will not compile for a BigInteger operand.
5. Using divide(new BigInteger("2")) is not very efficient; use shiftRight(1) instead.

Try this method instead:

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