Jo Ko Jo Ko - 15 days ago 5
Java Question

How to implement Big Integer subtraction in Java?

I want to subtract 2 big integer numbers and by not using the API like BigInteger, and implement the sum operation on my own.

I have already implemented, as shown in the following, where I can add 2 big integer numbers not using

BigInteger
.

class BigIntAdd{
public static void main(String args[]){
String s1 = "7654729850328997631007285998163550104";
String s2 = "5980139243970186632651869926335829102";
add(s1, s2);
}

public static String add(String addend1, String addend2) {
StringBuilder buf = new StringBuilder();
for ( int i1 = addend1.length() - 1, i2 = addend2.length() - 1, carry = 0;
i1 >= 0 || i2 >= 0 || carry != 0;
i1--, i2-- ) {
int digit1 = i1 < 0 ? 0 :
Integer.parseInt(Character.toString(addend1.charAt(i1)));
int digit2 = i2 < 0 ? 0 :
Integer.parseInt(Character.toString(addend2.charAt(i2)));

int digit = digit1 + digit2 + carry;
if (digit > 9) {
carry = 1;
digit -= 10;
} else {
carry = 0;
}

buf.append(digit);
}
return buf.reverse().toString();
}


How can I revise the code so that it can subtract 2 big integer numbers?

Answer

Here is a very simple example of subtraction of BigInteger. Sorry in advance as I used character array instead of String to represent the numbers, but you can get the idea.

private static char[] subtractValue(char[] greater, char[] smaller) {
        char[] result = new char[greater.length];
        int index = 1;
        int carry = 0;
        int digit;

        // 1. subtract shorter part
        while (index <= smaller.length) {
                digit = Character.getNumericValue(greater[greater.length-index]) - Character.getNumericValue(smaller[smaller.length-index]) - carry;
                carry = digit < 0 ? 1 : 0;
                digit = digit + (carry == 1? 10 : 0);
                result[greater.length - index] = Character.forDigit(digit, 10);
                index++;
        }

        // 2. carry rippling
        while (index <= greater.length) {
                digit = Character.getNumericValue(greater[greater.length-index]) - carry;
                carry = digit < 0 ? 1 : 0;
                digit = digit + (carry == 1 ? 10 : 0);
                result[greater.length - index] = Character.forDigit(digit, 10);
                index++;
        }

        // 3. trim out trailing zeros
        int i;
        for(i = 0; i < result.length - 1 && result[i] == '0'; i++) {
        }
        return Arrays.copyOfRange(result, i, result.length);
}

You can invoke it this way:

char[] bigger = new char[]{'7', '7', '8'};
char[] smaller = new char[]{'1', '2', '3'};
String result = Arrays.toString(subtractValue(bigger, smaller));
System.out.println(result);

Hope it helps!

Edit

1. Subtract shorter part

This section of code simply subtract every ith digit of smaller from greater and if there is any carry, it will propagate the carry for (i + 1)th digit.

 2 1 0
 1 2 3
 -----
 0 8 7

2. Carry rippling

This section subtract if there is any carry left from prevous step and propagate the new carry if needed until the carry becomes zero.

In (1) part, we did - 
2 0 0
0 7 8
------
0 2 2

Now, we have still carry 1 left from (1) to subtract

2 0 0
1
-----
1 2 2

3. Trim out trailing zeros

This section trim out the trailing zeros.

1 2 3
1 2 1
-----
0 0 2

After trimming zeros

2
Comments