Java workaround for BigInteger

Question

I was working on a scenario wherein i had to implement BODMAS in Java and the operands could have as many as 1000 digits. So i chose to implement it in the following manner - I converted the infix expression (expression on which BODMAS was to be implemented) to postfix And then i evaluated the postfix expression by parsing every BigInteger that it had. I was successful in this implementation.

Now i get to know that I can not use BigInteger and have to make do with the basic data types like int,string, etc. I have been thinking about how this could be done and to be frank, havent made any significant progress. Any help or suggestions on how BigInteger can be implemented using the basic data types would be of great help

p1nG

Answer 1

A straightforward way to implement large integers is to store them as an array of decimal digits, eg. 1234 could be represented by:

int[] bignum = new int[] {1, 2, 3, 4};

You would need to implement longhand addition, subtraction, multiplication, division, and whatever else you need.

You may find that storing the numbers "reversed" might be easier, so store 1234 as:

int[] bignum = new int[] {4, 3, 2, 1};

A more advanced implementation would use base 2^32 or something much larger than base 10.

Answer 2

Here is a free implementation of BigInteger from Open JDK. It's covered by GPL2 (is that a problem?)

And even if you can't copy&paste it, you can learn how the bits are stored and manipulated in an int[] array.

An alternative may be the colt library from CERN. At least it can handle giant bit fields.

Edit

After finding out the meaning of BODMAS (thought it was a cipher algorithm or something else and had to be done on a special and limited JDK ;-)) ), I guess the colt advice is not appropriate ;)

I don't delete this answer, even though now I think, p1NG has no 'legal' restriction against using (or reimplementing) BigInteger...