A Java class for representing big integers with arbitrary number of digits and summation method - take II

Question

This post is the continuation of A Java class for representing big integers with arbitrary number of digits and summation method.

This time, I changed a manual character digit check to Character.isDigit and removed some redundant code from the sum().

Code

package com.github.coderodde.math;
import java.util.Objects;
import java.util.Random;
import java.util.Scanner;
/**
 * This class represents a non-negative integer with arbitrary number of digits.
 * Instances of this class are immutable.
 *
 * @version 1.0.1 (Oct 31, 2024)
 * @since 1.0.0 (Oct 30, 2024)
 */
public final class BigInteger {
 /**
 * This inner static class holds a single digit. It implements a doubly-
 * linked list of such digits.
 */
 private static final class Digit {
 byte value;
 Digit next;
 Digit prev;
 
 Digit(final byte digit) {
 this.value = digit;
 }
 }
 
 public static final class BigIntegerException extends RuntimeException {
 
 public BigIntegerException(final String exceptionMessage) {
 super(exceptionMessage);
 }
 }
 
 private Digit loDigit;
 private Digit hiDigit;
 
 private BigInteger() {
 
 }
 
 public BigInteger(String integerString) {
 Objects.requireNonNull(integerString, "'integerString' is null.");
 integerString = integerString.trim();
 
 // Check that is not blank. If it is, throw.
 if (integerString.isEmpty()) {
 throw new BigIntegerException("Input integer string is blank.");
 }
 
 final char[] chars = integerString.toCharArray();
 final int lastCharacterIndex = chars.length - 1;
 
 Digit digit =
 new Digit(
 convertDigitCharacterToDigit(
 chars[lastCharacterIndex]));
 
 // Initialize the least significant digit:
 loDigit = digit;
 hiDigit = digit;
 
 // Initialize all the other digits:
 for (int i = lastCharacterIndex - 1; i >= 0; i--) {
 final Digit d = new Digit(convertDigitCharacterToDigit(chars[i]));
 hiDigit.next = d;
 d.prev = hiDigit;
 hiDigit = d;
 }
 }
 
 @Override
 public String toString() {
 final StringBuilder sb = new StringBuilder();
 
 for (Digit digit = hiDigit;
 digit != null; 
 digit = digit.prev) {
 
 sb.append(Byte.toString(digit.value));
 }
 
 return sb.toString();
 }
 
 /**
 * Compute the sum of this and {@code othr} integers and return it. Both
 * {@code this} and {@code othr} remain intact.
 * 
 * @param othr the other operand.
 * 
 * @return a new instance of {@code BigInteger}.
 */
 public BigInteger sum(final BigInteger othr) {
 
 Objects.requireNonNull(othr, "The argument BigInteger is null.");
 
 Digit resultHiDigit = null;
 Digit resultLoDigit = null;
 
 Digit thisDigitIterator = this.loDigit;
 Digit othrDigitIterator = othr.loDigit;
 
 boolean carryOn = false;
 
 while (thisDigitIterator != null && 
 othrDigitIterator != null) {
 
 final byte sum = 
 (byte)(thisDigitIterator.value +
 othrDigitIterator.value + (carryOn ? 1 : 0));
 
 if (sum > 9) {
 carryOn = true;
 } else {
 carryOn = false;
 }
 
 final Digit digit = new Digit((byte)(sum % 10));
 
 if (resultHiDigit == null) {
 // Initialize the least significant digit:
 resultHiDigit = digit;
 resultLoDigit = digit;
 } else {
 // Prepend a new digit to the built big integer:
 resultHiDigit.next = digit;
 digit.prev = resultHiDigit;
 resultHiDigit = digit;
 }
 
 // Advance both the iterators:
 thisDigitIterator = thisDigitIterator.next;
 othrDigitIterator = othrDigitIterator.next;
 }
 
 // If this big integer is longer than othr, will iterate:
 while (thisDigitIterator != null) {
 
 final byte nextDigitValue = 
 (byte)(thisDigitIterator.value +
 (carryOn ? 1 : 0));
 
 carryOn = nextDigitValue > 9;
 
 final Digit digit = new Digit((byte)(nextDigitValue % 10));
 
 // Prepend digit:
 resultHiDigit.next = digit;
 digit.prev = resultHiDigit;
 resultHiDigit = digit;
 
 // Advance the iterator:
 thisDigitIterator = thisDigitIterator.next;
 }
 
 while (othrDigitIterator != null) {
 
 final byte nextDigitValue = 
 (byte)(othrDigitIterator.value +
 (carryOn ? 1 : 0));
 
 carryOn = nextDigitValue > 9;
 
 final Digit digit = new Digit((byte)(nextDigitValue % 10));
 
 // Prepend digit:
 resultHiDigit.next = digit;
 digit.prev = resultHiDigit;
 resultHiDigit = digit;
 
 // Advance the iterator:
 othrDigitIterator = othrDigitIterator.next;
 }
 
 if (carryOn) {
 // Deal with the possible carry flag:
 final Digit prefix = new Digit((byte) 1);
 resultHiDigit.next = prefix;
 prefix.prev = resultHiDigit;
 resultHiDigit = prefix;
 }
 
 // Set the data of the newly created big integer and return:
 final BigInteger result = new BigInteger();
 result.hiDigit = resultHiDigit;
 result.loDigit = resultLoDigit;
 return result;
 }
 
 /**
 * Converts the character representation of a digit to a byte.
 * 
 * @param digitCharacter the digit character representation to convert.
 * 
 * @return a byte value corresponding to {@code digitCharacter}.
 */
 private static byte convertDigitCharacterToDigit(
 final char digitCharacter) {
 
 checkDigitCharacter(digitCharacter);
 return (byte)(digitCharacter - '0');
 }
 
 /**
 * Checks that {@code digitCharacter} is with the valid range.
 * 
 * @param digitCharacter the digit character to check.
 */
 private static void checkDigitCharacter(final char digitCharacter) {
 if (!Character.isDigit(digitCharacter)) {
 final String exceptionMessage = 
 String.format(
 "Invalid digit character: %c, " + 
 "must be at least '0' and at most '9'.", 
 digitCharacter);
 
 throw new BigIntegerException(exceptionMessage);
 }
 }
 
 public static void main(String[] args) {
 benchmark();
 
 System.out.println("REPL:");
 
 final Scanner scanner = new Scanner(System.in);
 
 while (true) {
 System.out.print("?> ");
 final String line = scanner.nextLine();
 final String[] tokens = line.split("\\s+");
 
 final BigInteger b1 = new BigInteger(tokens[0]);
 final BigInteger b2 = new BigInteger(tokens[1]);
 
 System.out.println("=> " + b1.sum(b2));
 }
 }
 
 private static void benchmark() {
 final Random random = new Random(666L);
 
 long start = System.nanoTime();
 
 final java.math.BigInteger jmbi1 = buildJavaBigInteger(random);
 final java.math.BigInteger jmbi2 = buildJavaBigInteger(random);
 
 long end = System.nanoTime();
 
 System.out.printf("Created java.math.BigIntegers in %d nanoseconds.\n", 
 end - start);
 
 final String bigIntString1 = jmbi1.toString();
 final String bigIntString2 = jmbi2.toString();
 
 start = System.nanoTime();
 
 final BigInteger bi1 = new BigInteger(bigIntString1);
 final BigInteger bi2 = new BigInteger(bigIntString2);
 
 end = System.nanoTime();
 
 System.out.printf("Created my BigIntegers in %d nanoseconds.\n",
 end - start);
 
 start = System.nanoTime();
 
 final java.math.BigInteger resultJavaBigInteger = jmbi1.add(jmbi2);
 
 end = System.nanoTime();
 
 System.out.printf("Java BigInteger summation in %d nanoseconds.\n",
 end - start);
 
 start = System.nanoTime();
 
 final BigInteger resultMyBigInteger = bi1.sum(bi2);
 
 end = System.nanoTime();
 
 System.out.printf("My BigInteger summation in %d nanoseconds.\n",
 end - start);
 
 System.out.printf(
 "Summation agrees: %b.\n", 
 resultJavaBigInteger
 .toString()
 .equals(resultMyBigInteger.toString()));
 }
 
 private static java.math.BigInteger 
 buildJavaBigInteger(final Random random) {
 java.math.BigInteger bi = java.math.BigInteger.ONE;
 
 for (int i = 0; i < 1000; i++) {
 bi = bi.multiply(
 java.math.BigInteger.valueOf(
 random.nextLong(Long.MAX_VALUE / 4)));
 }
 
 return bi;
 }
}

Benchmark output

Created java.math.BigIntegers in 51811999 nanoseconds.
Created my BigIntegers in 19018300 nanoseconds.
Java BigInteger summation in 80999 nanoseconds.
My BigInteger summation in 8918599 nanoseconds.
Summation agrees: true.
REPL:
?> 11 99
=> 110
?> 

Critique request

Please tell me anything that comes to mind regarding how to improve my attempt.

• greybeard: (The creation benchmark compares apples to oranges: build both from Strings.)
• greybeard: how to improve my attempt requires knowing goals and quality measures: please tell. Did you look at the GMP documentation?

Answer 1

 boolean carryOn = false;

 final byte sum = 
 (byte)(thisDigitIterator.value +
 othrDigitIterator.value + (carryOn ? 1 : 0));
 
 if (sum > 9) {
 carryOn = true;
 } else {
 carryOn = false;
 }

First, you could simplify that if.

 carryOn = sum > 9;

No reason to use five lines when one will do. However, an even easier solution would be to not use a boolean for this.

 byte carry = 0;
 final byte sum = (byte)(thisDigitIterator.value
 + othrDigitIterator.value) + carry;
 carry = sum / 10;

No need to branch. This has the same result as your code with fewer operations.

Unfortunately, the slowest operation in the loop is likely to be new Digit. To fix that, you need to switch data types. E.g. use an array of primitives instead of a linked list of objects.

Answer 2

Here is what comes to mind for me:

1. I would prefer an array over a doubly linked list. On a 32-bit JVM, the next and prev references each cost at least 4 bytes, meaning each digit takes 9 bytes to store (17 on a 64-bit JVM). In comparison, a contiguous array would take only 1 byte per digit. For more storage efficiency, 10 digit values per byte is leaving 246 values unused; I would prefer storage in base 256. At that point, you might as well store each 'digit' as an unsigned int (base 4,294,967,296) to improve performance on digit operations, costing only 4 bytes per digit.
2. If you store the number of digits in each BigInteger, you can simplify the sum function by reassigning references so that the first operand has at least as many digits as the second operand. This avoids the third while loop and some redundant checks (note that result.numDigits = a.numDigits, potentially adding 1 for carryOn). This is more natural with an array but can be adapted to the current code:

// require a has at least as many digits as b
BigInteger a;
BigInteger b;
if (this.numDigits >= othr.numDigits)
{
 a = this;
 b = othr;
}
else
{
 a = othr;
 b = this;
}
Digit thisDigitIterator = a.loDigit;
Digit othrDigitIterator = b.loDigit;
while (othrDigitIterator != null) {
 // ...
}
while (thisDigitIterator != null) {
 // ...
}

3. The error message for invalid digit characters could be more explicit:

private static void checkDigitCharacter(final char digitCharacter) {
 if (!Character.isDigit(digitCharacter)) {
 throw new BigIntegerException(String.format(
 "Invalid digit character: '0' <= %c <= '9' is false.", digitCharacter
 ));
 }
}

Hope this helps!