Adding two big integers represented as strings

Question

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

    public static void add(String a, String b){
        ArrayList<String> res = new ArrayList<String>();
        StringBuilder myString = null;
        int i = a.length() - 1;
        int j = b.length() - 1;
        while(true){
            int i1 = Integer.parseInt(Character.toString(a.charAt(i)));
            int i2 = Integer.parseInt(Character.toString(b.charAt(j)));
            Integer i3  = i1 + i2 + carry;
            if(i3 > 9){
                carry = 1;
                i3 = i3 - 10;
            }else carry = 0;
            res.add(i3.toString());
            i--;j--;
            if(i < 0){
                res.add(carry.toString());
                break;
            }
        }
        Collections.reverse(res);
        for(String r : res){
            System.out.print(r);
        }
    }
} 

This program adds 2 numbers whose length is greater than limit of Long. I think my logic is kind of bulky. Can something be done to improve this?

Answer 1

Loop structure's OK, logic's reasonably good. There is obviously a Java library alternative of BigInteger, but I assume you knew that. Some efficiency issues with excessive toString() and string-ification of what could be character operations.

Here are some tips:

1. Use int where nulls are not possible, not Integer.
2. carry is only used locally -- keep it local. Referencing it outside the method can only be erroneous, so it shouldn't be visibly exposed to make that possible..
3. Carry calculation from i3 is OK here, but could in related algorithms be brittle -- it can't handle a digit-sum > 19 as the maximum carry it can produce is 1.
4. If addition completes with a carry of 0, it will output an unnecessary 0 digit.
5. If Strings are your inputs, you should probably build a String as the result via a StringBuilder -- not an ArrayList.
6. myString should be called result or sb, if you're building the result in it.
7. Build using StringBuilder in reverse order, and do it by character calculation (char) (i3 + '0') rather than toString() if you want to maximize efficiency.
8. Return the result from your function, and do the printing in main() instead. there. That way you have a general-purpose add() function and a fixed-purpose main() method for testing.

Is that complete enough?

Answer 2

This is only a partial refactoring, I have extracted some methods and fixed some problems. For example: if the two numbers have different lenghts, your program throws an exception:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.charAt(Unknown Source)
at it.test.refactor.MyClass.add(MyClass.java:21)
at it.test.refactor.MyClass.main(MyClass.java:11)

I'll do some more refactoring later :)

package it.test.refactor;

import java.util.regex.Pattern;

public class Main {

    private static final String DEFAULT1 = "00033000010";
    private static final String DEFAULT2 = "1";

    public static void main(String[] args) {
        if (args.length == 1 || args.length > 2) {
            System.err.println("Usage: MyClass integer1 integer2\n \n exemple: MyClass 123432 4321234");
            return;
        }
        if (args.length == 0) {
            System.out.println("Warning: using default parameters: " + DEFAULT1 + " + " + DEFAULT2);
            System.out.println(new TextualNumbers().add(DEFAULT1, DEFAULT2));
        } else {
            System.out.println(new TextualNumbers().add(args[0], args[1]));
        }
    }
}

class TextualNumbers {

    private static Pattern onlyDigits = Pattern.compile("\\A[0-9]*\\z");

    public String add(String firstAddend, String secondAddend) {
        validate(firstAddend);
        validate(secondAddend);
        PartialInputProcessor resultWithCarry = new PartialInputProcessor(0);
        int maxLen = Math.max(firstAddend.length(), secondAddend.length());
        StringBuilder res = new StringBuilder(maxLen + 1);
        for (int charIndex = 0; charIndex < maxLen; charIndex++) {
            int first = parseIntOrGet0(firstAddend, firstAddend.length() - charIndex - 1);
            int second = parseIntOrGet0(secondAddend, secondAddend.length() - charIndex - 1);
            resultWithCarry.processInputs(first, second);
            res.append(resultWithCarry.getPartialResult());
        }
        res.append(String.valueOf(resultWithCarry.getCarry()));
        String response = trimLeadingZeros(res.reverse().toString());
        return response;
    }

    private void validate(String addend) {
        if (addend == null) {
            throw new NullPointerException();
        }
        if (addend.length() == 0) {
            throw new IllegalArgumentException("[ " + addend + " ] is not a positive integer.");
        }

        if (!(onlyDigits.matcher(addend).matches())) {
            throw new IllegalArgumentException("[ " + addend + " ] is   not a positive integer.");
        }
    }

    private int parseIntOrGet0(String intString, int charPosition) {
        if (intString.length() <= charPosition || charPosition < 0) {
            return 0;
        } else {
            return Character.digit(intString.charAt(charPosition), 10);
        }
    }

    private String trimLeadingZeros(String a) {
        while (a.startsWith("0")) {
            a = a.substring(1);
        }
        return a;
    }

}

 class PartialInputProcessor {

    private int carry;
    private String partialResult;

    public PartialInputProcessor(int initialCarry) {
        this.carry = 0;
    }

    public String getCarry() {
        return String.valueOf(carry);
    }

    public String getPartialResult() {
        return partialResult;
    }

    public void processInputs(int input1, int input2) {
        int partialSum = input1 + input2 + carry;
        carry = partialSum / 10;
        partialResult = String.valueOf(partialSum % 10);
    }

}

Answer 3

Your code breaks if the input strings are of different lengths.

It is important to note that you don't support negative or non-integer inputs.

I would expect the add() function to return the result as a String: public static String add(String a, String b). (You probably intended to do that, since you declared myString but never used it.)

Instead of accumulating the result in an ArrayList<String>, I would just use the StringBuilder. (StringBuilder is essentially an ArrayList of char. It even has a .reverse() method.)

The carry variable should be local to the add() function; there is no reason why it should be stored in the state of the class. It's confusing, and it makes your code non-thread-safe. (Also, int should be preferred over Integer whenever possible.)

MyClass is a pointless name. BigInteger would be a good name, but it would be a bad idea to use the same name as a class in the standard Java library, even if they are in different packages. Name it something similar to BigInteger.

Your variable names could be improved with parallelism. It's hard to remember that i1 and i correspond to a, and i2 and j correspond to b. Naming the variables digit1, i1, addend1 and digit2, i2, addend2 would be better.

A while (true) { … } loop with a break inside suggests that the code structure could be improved. I think that a for-loop provides a better structure.

/**
 * Adds two non-negative integers represented as string of digits.
 *
 * @exception NumberFormatException if either argument contains anything other
 *            than base-10 digits.
 */
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();
}

Answer 4

Loop structure's OK, logic's reasonably good. There is obviously a Java library alternative of BigInteger, but I assume you knew that. Some efficiency issues with excessive toString() and string-ification of what could be character operations.

Here are some tips:

1. Use int where nulls are not possible, not Integer.
2. carry is only used locally -- keep it local. Referencing it outside the method can only be erroneous, so it shouldn't be visibly exposed to make that possible..
3. Carry calculation from i3 is OK here, but could in related algorithms be brittle -- it can't handle a digit-sum > 19 as the maximum carry it can produce is 1.
4. If addition completes with a carry of 0, it will output an unnecessary 0 digit.
5. If Strings are your inputs, you should probably build a String as the result via a StringBuilder -- not an ArrayList.
6. myString should be called result or sb, if you're building the result in it.
7. Build using StringBuilder in reverse order, and do it by character calculation (char) (i3 + '0') rather than toString() if you want to maximize efficiency.
8. Return the result from your function, and do the printing in main() instead. there. That way you have a general-purpose add() function and a fixed-purpose main() method for testing.

Is that complete enough?

Answer 5

This is my version with basic java API's

package geeks.in.action.algo.numtoword;

public class AddTwoBigNumbers {

public static void main(String[] args) {
    try {
        System.out.println("Addition:" + addIntegers("9999", "9999"));
        System.out.println("Addition:" + addIntegers("1233434323432454521", "99872343237868642"));
        System.out.println("Addition:" + addIntegers("1233434323432454521", "37868642"));
        System.out.println("Addition:" + addIntegers("37868642", "1233434323432454521"));
    } catch (final Exception e) {
        System.out.println("Exception : " + e.getMessage());
    }
}

private static String addIntegers(String number1, String number2) throws Exception {
    validate(number1, number2);
    System.out.println("Adding: " + number1 + "+" + number2);
    char[] num1char = number1.toCharArray();
    char[] num2char = number2.toCharArray();
    if (num1char.length > num2char.length) {
        num2char = formatToSameLength(num1char, num2char);
    } else if (num1char.length < num2char.length) {
        num1char = formatToSameLength(num2char, num1char);
    }
    final char[] addition = new char[num1char.length + 1];
    char carrry = '0';
    for (int i = num1char.length - 1; i >= 0; i--) {
        final int sum = Character.getNumericValue(num1char[i]) + Character.getNumericValue(num2char[i]) + Character.getNumericValue(carrry);
        final char[] csum = String.valueOf(sum).toCharArray();
        carrry = '0';
        if (csum.length > 1 && i == 0) {
            addition[i + 1] = csum[1];
            addition[0] = csum[0];
        } else if (csum.length > 1) {
            carrry = csum[0];
            addition[i + 1] = csum[1];
        } else {
            addition[i + 1] = csum[0];
        }
    }
    return String.valueOf(addition);
}

private static void validate(String number1, String number2) throws Exception {
    if (number1.trim().isEmpty() || number2.trim().isEmpty() || !isNumber(number1) || !isNumber(number2)) {
        throw new Exception("Number is not present or not a valid number");
    }
}

private static boolean isNumber(String number) {
    try {
        Integer.parseInt(number);
        return true;
    } catch (final NumberFormatException nfe) {
    }
    return false;
}

private static char[] formatToSameLength(char[] num1char, char[] num2char) {
    final int diff = num1char.length - num2char.length;
    final char[] num = new char[num1char.length];
    for (int i = 0; i < diff; i++) {
        num[i] = '0';
    }
    for (int i = 0; i < num2char.length; i++) {
        num[diff + i] = num2char[i];
    }
    return num;
}
}