How to add two numbers of any length in java?

Question

Hi All,

How to add two numbers of any length in java?

Say for example, in java long size is 64 bit. So the maximum range is -9223372036854775808 to 9223372036854775807. Am i right?

So if we want to add a number which is greater than this like below, i got a error

" Integer Number too large"

long a = 9223372036854775807L;
long b = 9223372036854775808L;

In C, we can take those numbers as char array, by traversing through the address of each char and use some data structure, we can add two numbers of any size.

How to do it java. Can we traverse through the address of each character in String.

Answer 1

Check out the BigInteger class. It will be able to perform the operations you are looking for on really large numbers.

http://download.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html

Answer 2

Use BigInteger. Here is an example.

Example code (based on above link) -

BigInteger reallyBig1 = new BigInteger("1234567890123456890");
BigInteger reallyBig2 = new BigInteger("2743534343434361234");
reallyBig = reallyBig.add(reallyBig2);

Answer 3

You can use a BigInteger.

BigInteger a = new BigInteger("9223372036854775807");
BigInteger b = new BigInteger("9223372036854775808");
BigInteger result = a.add(b);

The BigInteger will let you work with numbers of any size, but you lose a considerable amount of performance over long or int.

Answer 4

The BigInteger will let you work with numbers of any size, but you lose a considerable amount of performance over long or int.

Actually, if you just need to run this operation once (user enters two numbers, and gets the result back), using BigInteger is fine. But if you need to perform the addition operation many times, you could use really your own implementation of big integer. When I was competing in ACM matches, we often used our own implementations based on char arrays (in C++). I suggest the following code. It is assumed that there are two arrays of integers, A and B. A[0] and B[0] store the lens of the corresponding numbers. A[i] and B[i] stores the digits themselves. A[1] and B[1] are the least significant digits. Therefore the number 1234 would correspond to such an array: {4,4,3,2,1}.

Now, suppose we want to sum these numbers and store them in array C in the same format. Here is an example of code, that you could use:

int len1 = A[0],  len2 = B[0], divisor = 0;
int len = len1 >= len2 ? len1 : len2;
for (int i=1;i<=len;i++) {
  if (i>len1) C[i] = B[i]+divisor;
  else if (i>len2) C[i] = A[i]+divisor;
  else C[i] = A[i]+B[i]+divisor;
  divisor = C[i]/10;
  C[i] %= 10;
}
while (divisor>0) {
  C[++len] = divisor%10;
  divisor /= 10;
}
C[0] = len;

That code uses the simple rules of arithmetic addition and should work significantly faster than the BigInteger general implementation. Have fun with using that.

Answer 5

Hi All,

Thanks for your responses.

I have tried to code by passing the numbers as string and add each character from the end. It works fine for me.

Is there any big difference between the addition of two very large numbers using BigInteger and the method, i specified above (add each character from end and store remainder in temporary variable and goes on). Is the underlying mechanism of BigInteger is same as my code(add each character from end)?

Thanks.

Answer 6

Is there any big difference between the addition of two very large numbers using BigInteger and the method, i specified above (add each character from end and store remainder in temporary variable and goes on).

The difference is that you could use a larger radix, for example. Suppose the radix is 10000, not just 10. When the code of my previous answer would be modified like this:

int len1 = A[0],  len2 = B[0], divisor = 0;
int len = len1 >= len2 ? len1 : len2;

for (int i=1;i<=len;i++) {
  if (i>len1) C[i] = B[i]+divisor;
  else if (i>len2) C[i] = A[i]+divisor;
  else C[i] = A[i]+B[i]+divisor;
  divisor = C[i]/10000;
  C[i] %= 10000;
}
while (divisor>0) {
  C[++len] = divisor%10000;
  divisor /= 10000;
}
C[0] = len;

In that case the code runs 4 time faster (since there is no difference for the virtual machine in arithmetic operations, since they depend on the constant only). Also, this means, that the array of integers will be 4 times smaller. The only problem this causes is how to format the output.