A simple class for holding non-negative integers with arbitrary number of digits. Supports only summation operation.

com.github.coderodde.math.BigInteger.java

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.0 (Oct 30, 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 (thisDigitIterator == null && 
            othrDigitIterator == null) {
            
            // Once here, all we need to do is to check the 'carryFlag':
            if (carryOn) {
                final Digit prefixDigit = new Digit((byte) 1);
                resultHiDigit.next = prefixDigit;
                prefixDigit.prev = resultHiDigit;
                resultHiDigit = prefixDigit;
            }
            
            final BigInteger result = new BigInteger();
            result.hiDigit = resultHiDigit;
            result.loDigit = resultLoDigit;
            return result;
        }
        
        // 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 (digitCharacter < '0' || digitCharacter > '9') {
            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);
        final java.math.BigInteger jmbi1 = buildJavaBigInteger(random);
        final java.math.BigInteger jmbi2 = buildJavaBigInteger(random);
        
        final String bigIntString1 = jmbi1.toString();
        final String bigIntString2 = jmbi2.toString();
        
        final BigInteger bi1 = new BigInteger(bigIntString1);
        final BigInteger bi2 = new BigInteger(bigIntString2);
        
        long start = System.nanoTime();
        
        final java.math.BigInteger resultJavaBigInteger = jmbi1.add(jmbi2);
        
        long 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;
    }
}

com.github.coderodde.math.BigIntegerTest.java

package com.github.coderodde.math;

import com.github.coderodde.math.BigInteger.BigIntegerException;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

public final class BigIntegerTest {
    
    private static final int BOUND = 1_000_000_000;
    
    @Test
    public void sumZeroAndZero() {
        assertEquals(
                "0", 
                new BigInteger("0").sum(new BigInteger("0")).toString());
    }
    
    @Test(expected = NullPointerException.class)
    public void throwsOnNullString() {
        new BigInteger(null);
    }
    
    @Test(expected = BigIntegerException.class)
    public void throwsOnBlankString() {
        new BigInteger("   ");
    }
    
    @Test(expected = BigIntegerException.class)
    public void throwsOnInvalidDigit1() {
        new BigInteger("12x4");
    }
    
    @Test(expected = BigIntegerException.class)
    public void throwsOnInvalidDigit2() {
        new BigInteger("12#4");
    }
    
    @Test
    public void bruteForceTest() {
        final Random random = new Random(13L);
        
        for (int i = 0; i < 1000; i++) {
            final int int1 = Math.abs(random.nextInt(BOUND));
            final int int2 = Math.abs(random.nextInt(BOUND));
            
            final String int1String = Integer.toString(int1);
            final String int2String = Integer.toString(int2);
            
            final BigInteger bigInteger1 = new BigInteger(int1String);
            final BigInteger bigInteger2 = new BigInteger(int2String);
            
            final BigInteger bigIntegerSum = bigInteger1.sum(bigInteger2);
            final int intSum = int1 + int2;
            
            final String intSumString = Integer.toString(intSum);
            
            assertEquals(intSumString, bigIntegerSum.toString());
        }
    }
}