Java BigInteger implementation

Question

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: ");
 }
 }
 }
}

Answer 1

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.

• user97059: 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?
• Peter Taylor: 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.
• Roland Illig: Instead of InvalidArgumentException (which comes from .NET), Java code typically uses IllegalArgumentException.