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

@ElliottFrisch it performs a binary search with high being the square and low being 0, returning when the binary search finds the integer that is the square root. — Mdev, Apr 29 '14 at 18:36
@Human I don't see an array (contiguous or otherwise) in OP's post. Also, what if I pass in `10`. — Elliott Frisch, Apr 29 '14 at 18:37
@ElliottFrisch I stated it incorrectly, it starts with the high number being the square + 1 and the low being 0. It converges on the square root as a binary search would when searching for an integer in an array. — Mdev, Apr 29 '14 at 18:38
You can just get the rough estimate of getting square root of 10 as 3 approximately when you will run this piece of code. — Am_I_Helpful, Apr 29 '14 at 18:39
possible duplicate of [How can I find the Square Root of a Java BigInteger?](http://stackoverflow.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger) — Elliott Frisch, Apr 29 '14 at 18:40
@Elliott Frisch-Your comment has helped me a bit,one good reference can be attributed to http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/ — Am_I_Helpful, Apr 29 '14 at 18:54

score 5 · Accepted Answer · answered Apr 29 '14 at 18:34

5

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.

answered Apr 29 '14 at 18:34

rgettman

176,041
30
275
357

But this is not my question.What will I receive after performing this??? I want to compare two BigIntegers for the greater than or lesser than relation. How will I use this Comparable interface to help me achieve this? – Am_I_Helpful Apr 29 '14 at 18:42
Calling `compareTo` will certainly help you. You will be able to compare the values of two `BigInteger`s by calling `compareTo`. You "use" `Comparable` by calling `compareTo` which is defined by `Comparable`. The `compareTo` method must be defined because `BigInteger` declares that it implements Comparable. – rgettman Apr 29 '14 at 18:47
While you are always welcome to answer your own question, I don't see what the repetition will gain. – rgettman Apr 29 '14 at 19:01

barak manos · Answer 2 · 2014-04-29T19:40:44.277

2

You are not using the BigInteger class correctly:

You can replace high = bi.add(ZERO) with a simple high = bi.
The comparison low <= high will not compile for BigInteger operands.
The comparison mid.multiply(mid) > bi will not compile for BigInteger operands.
The arithmetic operations mid-1 and mid+1 will not compile for a BigInteger operand.
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;
    }
}

edited Apr 29 '14 at 19:40

answered Apr 29 '14 at 18:56

barak manos

29,648
10
62
114

@shekhar: Well, you've changed the code in your question, so I'm gonna remove this answer in a few minutes... – barak manos Apr 29 '14 at 19:18
My purpose will not be solved if I will assign high=bi. Please correctify it! – Am_I_Helpful Apr 29 '14 at 19:20
@shekhar: You are wrong. `high=bi.add(ZERO)` in your code is equivalent to `high=bi` in my code. In addition to that, you have several errors in your code: 1. `while(low<=high)`. 2. `if(mid.multiply(mid) > bi)`. And finally, your use of `divide(new BigInteger("2")` is not very efficient, and you can improve it by replacing it with `shiftRight(1)`. – barak manos Apr 29 '14 at 19:25
So,you should have probably read the question in a hurried state.I had already mentioned that I am presenting my wrong code,only to give a fair idea as to what I wanted to achieve. And,moreover,your take over `high=bi` is wrong as in this program,there is no need to reference to bi's address,rather,it was only intended to provide an instantiation in the beginning! – Am_I_Helpful Apr 29 '14 at 19:53
1

@shekhar: I think that your perception of Java is wrong! When you instantiate `high=bi`, it does not mean that `bi` changes whenever `high` changes. Creating a new instance with `high=bi.add(ZERO)` has no effect different than `high=bi` (except for the duplicate instance, so if anything, it makes the performance of your code worse)! – barak manos Apr 29 '14 at 19:58
-No,no,man,I agree with you.But,I am telling that there is no need to reference to an object.Rather,you should have better provided a numeric constant instantiation to the new variable.There is no loss in creating new instance(duplicate,in your view) for achieving the perfection... – Am_I_Helpful Apr 29 '14 at 20:01
@shekhar: Look inside the loop, and you'll see that `high` is changed to reference a different variable (namely, `mid0`), so there is no reason why it shouldn't reference `bi` before entering the loop. – barak manos Apr 29 '14 at 20:02
-See,in Java, objects are manipulated through reference variables, and there is no operator for copying an object—the assignment operator duplicates the reference, not the object. The clone() method provides this missing functionality. – Am_I_Helpful Apr 29 '14 at 20:04
@shekhar: You still haven't answer to me (and to yourself), why on earth you are using `high = bi.add(ZERO)`!!! – barak manos Apr 29 '14 at 20:05
-I think you need to strengthen your concepts in Java,you might be missing some important links,or getting confused over time.Check this-->>http://people.cs.clemson.edu/~turner/courses/cs428/current/webct/content/java/jasg.html – Am_I_Helpful Apr 29 '14 at 20:07
-because I want to use bi somewhere else also,but,if assigned `high=bi`,it will not serve my purpose. See,in this way high will not be referring to the same point as bi.If I come to change bi somewhere, this attribute high will also reference to the same changed location. I hope you will put something valuable now for me as well as for yourself now!!! – Am_I_Helpful Apr 29 '14 at 20:11
@shekhar: You **do not** need to create a duplicate instance for `bi`, because you are **not** changing the internal properties of the instance which is referenced by `high`. I have not been able to convince you of that, so I'm not gonna try any further. Please note the additional performance issue, subjected to the use of `divide` instead of `shiftRight` (although the internal implementation of the `BigInteger` class might be handling that efficiently; you can't be sure, so you might as well use `shiftRight` just in order to "stay on the safe side"). Good luck :) – barak manos Apr 29 '14 at 20:13
-That I agree and appreciate that you pointed. Sorry for acknowledging it late. – Am_I_Helpful Apr 29 '14 at 20:23

Relational Operation on two BigIntegers in Java

2 Answers2