3
\$\begingroup\$

I've written a java application that can handle operations on big integers implemented with array list of digits.

I have a difficulty with the way I implemented the divide method, because when the difference between the two numbers is high, the operation can take a huge amount of time.

I'd like to hear your thoughts about this implementation and ways it can be improved. Here is the class and its test class:

BigInt.java

import java.util.ArrayList;

public class BigInt implements Comparable<BigInt> {

    private static final char MINUS_CHAR = '-';
    private static final char PLUS_CHAR = '+';

    // Saves the digits of the number - last element represents the smallest unit of the number
    private ArrayList<Integer> numberDigits = new ArrayList<>();

    // Indication if the number is negative
    private boolean negative;

    // String representation as given by the user
    private String stringNumber;

    BigInt(String number){

        if (number.equals("")){
            stringNumber = "0";
            numberDigits.add(0);
        }
        else {
            // Dealing with the positive/negative signs
            char firstChar = number.charAt(0);
            if (firstChar == MINUS_CHAR || firstChar == PLUS_CHAR) {
                if (firstChar == MINUS_CHAR)
                    negative = true;

                number = number.substring(1);
            }

            // Regex to remove zeros at the beginning of the number
            number = number.replaceFirst("^0+(?!$)", "");
            stringNumber = number;

            // Saving the digits
            for (int index = 0; index < number.length(); index++) {
                int curDigNumericVal = Character.getNumericValue(number.charAt(index));

                // Current char is not a valid digit
                if (curDigNumericVal == -1)
                    throw new IllegalArgumentException();

                numberDigits.add(curDigNumericVal);
            }
        }
    }

    private boolean isNegative() {
        return negative;
    }

    private void flipNegativity() {
        if (stringNumber == "0")
            return;

        negative = !negative;
        if (stringNumber.charAt(0) == MINUS_CHAR){
            stringNumber = stringNumber.substring(1);
        } else {
            stringNumber = MINUS_CHAR + stringNumber;
        }
    }

    // Adding another bigInt number to the current bigInt number
    BigInt plus(BigInt otherNumber) {

        // current is negative, other is positive - subtract current from the other
        if (negative && !otherNumber.isNegative()) {
            return otherNumber.minus(new BigInt(stringNumber));
        }

        // other is negative - subtract its value
        if (otherNumber.isNegative()) {
            return minus(new BigInt(otherNumber.toString()));
        }

        // Setting the longer number of the two numbers
        ArrayList<Integer> longerNumber, shorterNumber;
        if (numberDigits.size() >= otherNumber.numberDigits.size()) {
            longerNumber = numberDigits;
            shorterNumber = otherNumber.numberDigits;
        }
        else {
            longerNumber = otherNumber.numberDigits;
            shorterNumber = numberDigits;
        }

        int lengthsDifferences = longerNumber.size() - shorterNumber.size();


        StringBuilder resultString = new StringBuilder();

        // Initializing a carry for every addition
        int carry = 0;


        // Iterating from smallest unit digit to the biggest
        for (int index = shorterNumber.size() - 1; index >= 0; index--) {
            int shorterNumberDigit = shorterNumber.get(index);
            int longerNumberDigit = longerNumber.get(index + lengthsDifferences);

            int newDigit = shorterNumberDigit + longerNumberDigit + carry;

            // Calculating the carry and the new digit
            carry = newDigit / 10;
            newDigit = newDigit % 10;

            resultString.append(newDigit);
        }

        // Adding digits of longer number
        for (int index = lengthsDifferences - 1; index >= 0; index--) {
            int currDig = longerNumber.get(index);

            // Check if need to add carry
            if (currDig + carry == 10) {
                resultString.append(0);
                carry = 1;
            } else {
                resultString.append(currDig + carry);
                carry = 0;
            }
        }

        // Check if there is carry on last digit
        if (carry > 0)
            resultString.append(carry);

        return new BigInt(resultString.reverse().toString());
    }

    BigInt minus(BigInt otherNumber){

        // If the other number is negative, add its value
        if (otherNumber.isNegative()) {
            return plus(new BigInt(otherNumber.stringNumber));
        }

        // subtract a bigger number than the current
        if (this.compareTo(otherNumber) < 0) {
            BigInt result = otherNumber.minus(this);
            result.flipNegativity();
            return result;
        }

        // Other number is positive and not greater than current:
        int lengthsDifferences = numberDigits.size() - otherNumber.numberDigits.size();

        StringBuilder resultString = new StringBuilder();

        int carry = 0;

        for (int index = otherNumber.numberDigits.size() - 1; index >=0 ; index--) {
            int biggerNumDig = numberDigits.get(index + lengthsDifferences) - carry;
            int smallerNumDig = otherNumber.numberDigits.get(index);

            carry = 0;

            if (biggerNumDig < smallerNumDig){
                carry = 1;
                biggerNumDig += 10;
            }

            resultString.append(biggerNumDig - smallerNumDig);
        }

        for (int index = lengthsDifferences - 1; index >=0 ; index--) {
            int currDig = numberDigits.get(index);

            // Check if carry is needed
            if (carry > currDig){
                resultString.append(currDig + 10 - carry);
                carry = 1;
            } else {
                resultString.append(currDig - carry);
                carry = 0;
            }
        }

        return new BigInt(resultString.reverse().toString());
    }

    // Multiply bigInt
    BigInt multiply(BigInt otherNumber){

        BigInt finalResult = new BigInt("0");
        BigInt currentUnit = new BigInt("1");

        for (int otherNumIndex = otherNumber.numberDigits.size() - 1; otherNumIndex >=0; otherNumIndex--){
            int currentOtherNumDigit = otherNumber.numberDigits.get(otherNumIndex);

            // Holds the result of multiplication of the number by the current digit of the other number

            BigInt currentResult = new BigInt("0");
            BigInt currentDigitUnit = new BigInt(currentUnit.toString());

            for (int index = numberDigits.size() - 1; index >=0; index--) {
                int currentDigit = numberDigits.get(index);
                int digitsMultiplication = currentDigit * currentOtherNumDigit;

                currentResult = currentDigitUnit.MultiplyUnit(digitsMultiplication);
                currentDigitUnit.multiplyByTen();
            }

            currentUnit.multiplyByTen();
            finalResult = finalResult.plus(currentResult);
        }

        // Check if need to flip negativity
        if (otherNumber.isNegative() && !isNegative() || isNegative() && !otherNumber.isNegative())
            finalResult.flipNegativity();

        return finalResult;
    }

    BigInt divide(BigInt otherNumber) {

        if (isBigIntZero(otherNumber))
            throw new ArithmeticException();

        // Handling the case where the current number is positive and the other is negative
        if (otherNumber.isNegative() && !isNegative()) {
            BigInt result = divide(new BigInt(otherNumber.stringNumber));
            result.flipNegativity();
            return result;

            // Handling the case where the current number is negative and the other is positive
        } else if (!otherNumber.isNegative() && isNegative()) {
            BigInt result = new BigInt(stringNumber).divide(otherNumber);
            result.flipNegativity();
            return result;
        }

        int compareResult = this.compareTo(otherNumber);
        if (compareResult == 0)
            return new BigInt("1");
        else if (compareResult < 0)
            return new BigInt("0");

        BigInt result = new BigInt("0");
        BigInt tempNumber = new BigInt("0");

        while (tempNumber.compareTo(this) < 0) {
            tempNumber = tempNumber.plus(otherNumber);
            result = result.plus(new BigInt("1"));
        }

        return result;

    }

    private boolean isBigIntZero(BigInt number) {
        return number.stringNumber.replace("0", "").equals("");

    }

    // Multiply a unit of BigInt with an integer. Example: 1000000000000000000 * 54
    private BigInt MultiplyUnit(int majorUnits){

        // Setting the string representation
        String majorUnitsString = String.valueOf(majorUnits);
        String newNumber = majorUnitsString + stringNumber.substring(1);

        return new BigInt(newNumber);
    }

    private void multiplyByTen() {
        this.numberDigits.add(0);
        stringNumber += '0';
    }

    @Override
    public int compareTo(BigInt other) {

        // Current is negative, other is positive
        if (isNegative() && !other.isNegative())
             return -1;

        // Current is positive, other is negative
        else if (!isNegative() && other.isNegative()){
            return 1;
        }

        // Both are negative
        else if (isNegative()){
            // Current is negative and has more digits - therefore it is smaller
            if (numberDigits.size() > other.numberDigits.size())
                return -1;
            // Current is negative and has less digits - Therefore it is bigger
            else if (numberDigits.size() < other.numberDigits.size())
                return 1;

            // Both have same number of digits - need to iterate them
            else
                for (int index = 0; index < numberDigits.size(); index++) {

                    // Current has bigger negative digit - therefore it is smaller
                    if (numberDigits.get(index) > other.numberDigits.get(index))
                        return -1;

                    // Current has smaller negative digit - therefore it is smaller
                    else if (numberDigits.get(index) < other.numberDigits.get(index))
                            return 1;
                }

                // If we have reached here, the numbers are completely identical
                return 0;
        }

        // If we have reached here, both numbers are positive

        // Current is positive and has more digits - Therefore it is bigger
        if (numberDigits.size() > other.numberDigits.size()) {
            return 1;
        }

        // Current is positive and has less digits - Therefore it is smaller
        else if (numberDigits.size() < other.numberDigits.size())
            return -1;

            // Both have same number of digits - need to iterate them
        else
            for (int index = 0; index < numberDigits.size(); index++) {

                // Current has bigger positive digit - therefore it is bigger
                if (numberDigits.get(index) > other.numberDigits.get(index))
                    return 1;

                    // Current has smaller positive digit - therefore it is smaller
                else if (numberDigits.get(index) < other.numberDigits.get(index))
                    return -1;
            }

        // If we have reached here, the numbers are completely identical
        return 0;
    }

    @Override
    public boolean equals(Object o) {
        // self check
        if (this == o)
            return true;

        // null check
        if (o == null)
            return false;

        // type check and cast
        if (getClass() != o.getClass())
            return false;

        BigInt other = (BigInt) o;
        // field comparison

        return other.toString().equals(stringNumber);
    }

    @Override
    public String toString() {
        return stringNumber;
    }
}

Main

import com.sun.javaws.exceptions.InvalidArgumentException;

import java.util.Scanner;

public class Main {

    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        BigInt firstNumber;
        BigInt secondNumber;

        System.out.println("Enter first number: ");
        firstNumber = inputBigIntNumber();

        System.out.println("Enter second number: ");
        secondNumber = inputBigIntNumber();

        System.out.println("The result of plus is: " + firstNumber.plus(secondNumber));
        System.out.println("The result of minus is: " + firstNumber.minus(secondNumber));
        System.out.println("The result of multiply is: " + firstNumber.multiply(secondNumber));

        try {
            System.out.println("The result of divide is: " + firstNumber.divide(secondNumber));
        } catch (ArithmeticException ex){
            System.out.println("Can not divide by zero");
        }

    }

    // Taking a valid integer input from the user (greater than 0)
    private static BigInt inputBigIntNumber(){

        String str = scanner.nextLine();

        while (true) {
            try {
                return new BigInt(str);
            }
            catch (IllegalArgumentException ex) {
                System.out.println("Invalid number, please try again: ");
            }
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

Main

import com.sun.javaws.exceptions.InvalidArgumentException;

Are you using Eclipse? This looks like an IDE being unhelpful. The InvalidArgumentException you want is in java.lang.


    public static void main(String[] args) {
        BigInt firstNumber;
        BigInt secondNumber;

        System.out.println("Enter first number: ");
        firstNumber = inputBigIntNumber();

        System.out.println("Enter second number: ");
        secondNumber = inputBigIntNumber();

        System.out.println("The result of plus is: " + firstNumber.plus(secondNumber));
        System.out.println("The result of minus is: " + firstNumber.minus(secondNumber));
        System.out.println("The result of multiply is: " + firstNumber.multiply(secondNumber));

        try {
            System.out.println("The result of divide is: " + firstNumber.divide(secondNumber));
        } catch (ArithmeticException ex){
            System.out.println("Can not divide by zero");
        }

    }

This isn't a great way of doing tests. Much better to have unit tests.

I tested it with input 17 42 and the value given for the multiplication is 420, which is clearly wrong.


BigInt

    // Saves the digits of the number - last element represents the smallest unit of the number
    private ArrayList<Integer> numberDigits = new ArrayList<>();

Thumbs up for documenting the endianness clearly. In my experience the opposite endianness is easier to work with.

I think BigInt is immutable, so I'm not sure what advantage there is to using ArrayList<Integer> over int[], and the boxing/unboxing is an obvious disadvantage.


    // Indication if the number is negative
    private boolean negative;

I would call it isNegative as a hint that it's a Boolean and to read well in if statements.


    // String representation as given by the user
    private String stringNumber;

I'm curious as to why the class keeps two copies of the digits. Is that a time/memory tradeoff due to toString() being a bottleneck?


    private boolean isNegative() {
        return negative;
    }

Why is this private? It might be useful if it were public, but for private use you have access to the field.


    private void flipNegativity() {
        if (stringNumber == "0")
            return;

        negative = !negative;

Ah, it's not immutable. Some explicit documentation of this at the top of the class would be nice.


    // Adding another bigInt number to the current bigInt number
    BigInt plus(BigInt otherNumber) {
    BigInt minus(BigInt otherNumber){
    // Multiply bigInt
    BigInt multiply(BigInt otherNumber){

Again, not public?


        BigInt finalResult = new BigInt("0");
        BigInt currentUnit = new BigInt("1");

        for (int otherNumIndex = otherNumber.numberDigits.size() - 1; otherNumIndex >=0; otherNumIndex--){
            int currentOtherNumDigit = otherNumber.numberDigits.get(otherNumIndex);

            // Holds the result of multiplication of the number by the current digit of the other number

            BigInt currentResult = new BigInt("0");
            BigInt currentDigitUnit = new BigInt(currentUnit.toString());

            for (int index = numberDigits.size() - 1; index >=0; index--) {
                int currentDigit = numberDigits.get(index);
                int digitsMultiplication = currentDigit * currentOtherNumDigit;

                currentResult = currentDigitUnit.MultiplyUnit(digitsMultiplication);
                currentDigitUnit.multiplyByTen();
            }

            currentUnit.multiplyByTen();
            finalResult = finalResult.plus(currentResult);
        }

Maybe you could factor out the addition into a method which takes two input BigInts or representations thereof and a power of 10 offset for the second. Then you could share the code with add and reuse it here, saving all the multiplyByTen() etc.

Sketch code:

int[] accumulator = new int[worst case length of the output];
for (int powerOfTen = 0; powerOfTen < numberDigits.size(); powerOfTen++) {
    addImpl(accumulator, powerOfTen, numberDigits.get(powerOfTen), otherNumber.numberDigits);
}

The core of add(BigInt) would be

accumulator = new int[worst case length of the output]
addImpl(accumulator, 0, 1, numberDigits);
addImpl(accumulator, 0, 1, otherNumber.numberDigits);

    BigInt divide(BigInt otherNumber) {

This could use a comment about rounding. It looks like it rounds to zero: is that correct?

        // Handling the case where the current number is positive and the other is negative
        if (otherNumber.isNegative() && !isNegative()) {
            BigInt result = divide(new BigInt(otherNumber.stringNumber));
            result.flipNegativity();
            return result;

            // Handling the case where the current number is negative and the other is positive
        } else if (!otherNumber.isNegative() && isNegative()) {
            BigInt result = new BigInt(stringNumber).divide(otherNumber);
            result.flipNegativity();
            return result;
        }

        int compareResult = this.compareTo(otherNumber);
        if (compareResult == 0)
            return new BigInt("1");
        else if (compareResult < 0)
            return new BigInt("0");

That doesn't look right. If both numbers are negative and this.compareTo(otherNumber) < 0 then the result should be at least 1.

        BigInt result = new BigInt("0");
        BigInt tempNumber = new BigInt("0");

        while (tempNumber.compareTo(this) < 0) {
            tempNumber = tempNumber.plus(otherNumber);
            result = result.plus(new BigInt("1"));
        }

The keywords you need to search for are long division. That's the algorithm they teach you in school which everyone forgets by the time they leave school.


    @Override
    public int compareTo(BigInt other) {

        // Current is negative, other is positive
        if (isNegative() && !other.isNegative())
             return -1;

        // Current is positive, other is negative
        else if (!isNegative() && other.isNegative()){
            return 1;
        }

Might be good to add an equality test before anything else: at the very least if (this == other) return 0. Other than that, so far, so good; but then it goes off the rails. It might be a lot simpler to look at the sign of this.minus(other).


    @Override
    public boolean equals(Object o) {
        // self check
        if (this == o)
            return true;

        // null check
        if (o == null)
            return false;

        // type check and cast
        if (getClass() != o.getClass())
            return false;

        BigInt other = (BigInt) o;
        // field comparison

        return other.toString().equals(stringNumber);
    }

If you override equals you should also override getHashCode() to ensure that the class works correctly with HashSet, HashMap, etc.

\$\endgroup\$
  • \$\begingroup\$ thanks for the useful comments. Could you further explain this statement: Maybe you could factor out the addition into a method which takes two input BigInts or representations thereof and a power of 10 offset for the second. Then you could share the code with add and reuse it here, saving all the multiplyByTen() etc. And moreover, regarding your suggestion using the minus method in the compareTo - I would really like to do that but the minus method uses the CompareTo and the plus uses the minus so it can't be used as well. Do you have another suggestion to solve that? \$\endgroup\$ – user97059 Mar 30 at 17:09
  • 1
    \$\begingroup\$ I've added some outline code which I hope will make that clearer. Fair point on the circular reference between minus and compareTo. My own big integer class just does addition and multiplication because it's for combinatoric problems where the bottleneck in Java's built-in BigInteger is toString(), but I think that maybe the solution would be to do the addition using tens complement: that way it's just an addition and a bit of bookkeeping at the end if the result turns out to be negative. \$\endgroup\$ – Peter Taylor Mar 30 at 17:23
  • 2
    \$\begingroup\$ Instead of InvalidArgumentException (which comes from .NET), Java code typically uses IllegalArgumentException. \$\endgroup\$ – Roland Illig Mar 30 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy