1.2. Implementation

LongInteger: implementation.

We are going to create a class called LongInteger inheriting SignedNumeral that can store an indefinite size of an integer value beyond the primitive types such as int and long.

What is so special about primitive data types in Java?

Java SE provides a similar class called BigInteger although the implementations of LongIntegerandBigIntegerare completely independent.

Field

Let us declare the member field digits that is an array of bytes holding the values of this integer:

public class LongInteger extends SignedNumeral<LongInteger> {
    /** The values of this integer (excluding the sign). */
    protected byte[] digits;
    ...

• L1: LongInteger is passed to specify the generic type T in SignedNumeral.

The i'th dimension of digits is the i'th least significant digit in the integer such that the integer 12345 would be stored as digits = {5, 4, 3, 2, 1}, which makes it convenient to implement the arithmetic methods, add() and multiply().

Is the array of bytes the most efficient way of storing a long integer?

Constructors

Let us define the following three constructors:

/** Creates a long integer with the default value of "0". */
public LongInteger() {
    this("0");
}

/**
 * Creates a long integer by copying the specific object.
 * @param n the object to be copied.
 */
public LongInteger(LongInteger n) {
    super(n.sign);
    digits = Arrays.copyOf(n.digits, n.digits.length);
}

/**
 * Creates a long integer with the specific sign and values.
 * @param n the sign and values to be set.
 * @see #set(String)
 */
public LongInteger(String n) {
    set(n);
}

• L2: the default constructor that initializes this integer with 0 by calling the constructor in L20.

• L10: a copy constructor that initializes this integer with n.

  • super(): calls the corresponding constructor in the super class, SignedNumeral.

  • Arrays.copyOf(): creates a new array by copying n.digits.

• L20: a constructor that initializes this integer with n by passing it to the set() method.

Do the constructors in L10 and L20 call any constructor in the super class?

Arrays.copyOf() is a static method referenced by the class type Arrays, not an object. Java provides many classes with static methods that are commonly used (e.g., Arrays, Collections).

Can you call non-static methods or fields in the body of a static method?

The static keyword must not be abused to quickly fix compile errors unless it is intended.

Method: set()

Let us define the set() method that takes a string and sets the sign and the value of this integer:

/**
 * Sets the sign and values of this integer.
 * @param n the sign and values to be set.
 * @throws NullPointerException when `n` is null.
 * @throws InvalidParameterException when `n` contains non-digit character
 *         except for the first character that can be [+-\d].
 */
public void set(String n) {
    // 'n' must not be null
    if (n == null)
        throw new NullPointerException();

    // set this.sign
    sign = switch (n.charAt(0)) {
        case '-' -> { n = n.substring(1); yield Sign.NEGATIVE; }
        case '+' -> { n = n.substring(1); yield Sign.POSITIVE; }
        default -> Sign.POSITIVE;
    };

    // set this.digits
    digits = new byte[n.length()];

    for (int i = 0, j = n.length() - 1; i < n.length(); i++, j--) {
        byte v = (byte)(n.charAt(i) - 48);
        if (0 > v || v > 9) {
            String s = String.format("%d is not a valid value", v);
            throw new InvalidParameterException(s);
        }
        digits[j] = v;
    }
}

• L1-7: javadoc comments.

  • L4: this method throws NullPointerException if n is null.

  • L5: this method throws InvalidParameterException if the format of n is invalid.

• L10-11: throws the NullPointerException.

• L14-18: checks the first character of n and sets this.sign using the switch expression.

  • String member methods: charAt(), substring().

  • yield: returns the value of this switch statement for the condition (introduced in Java 14).

• L21-30: sets the value of n to this.digits .

  • L23: for-loop can handle multiple variables such as i and j.

  • L24: gets the ASCII value of n.charAt(i).

  • L25-28: throws the InvalidParameterException if v is not a digit.

  • L29: stores the value in the reverse order.

  • L27: String.format() is a static method in String.

When should we use throw statements over try..catch blocks for error handling and vice versa?

This type of method is called a setter. Java encourages making member fields private and creating getters and setters to access the fields for encapsulation, which is not necessarily encouraged by other languages.

Method: add()

Let us override the add() method that calls two helper methods:

@Override
public void add(LongInteger n) {
    if (sign == n.sign)
        addSameSign(n);
    else
        addDifferentSign(n);
}

• L3-4: adds n to this integer that has the same sign by calling addSameSign().

• L5-6: adds n to this integer that has a different sign by calling addDifferentSign().

The following shows an implementation of addSameSign() based on the simple arithmetic:

/**
 * Adds the specific integer that has the same sign as this integer.
 * @param n the integer to be added with the same sign.
 */
protected void addSameSign(LongInteger n) {
    // copy this integer to result[]
    int m = Math.max(digits.length, n.digits.length);
    byte[] result = new byte[m + 1];
    System.arraycopy(digits, 0, result, 0, digits.length);

    // add n to result
    for (int i = 0; i < n.digits.length; i++) {
        if (i < n.digits.length)
            result[i] += n.digits[i];
        if (result[i] >= 10) {
            result[i] -= 10;
            result[i + 1] += 1;
        }
    }

    // set this.digits
    digits = result[m] == 0 ? Arrays.copyOf(result, m) : result;
}

• L7-9: creates the byte array result by copying values in this integer.

  • L8: the dimension of result can be 1 more than m after the addition.

  • Static methods: Math.max(), System.arraycopy().

• L12-19: adds n to results (if exists) from the least significant digit.

  • L15-18: pass a carry to the next digit.

• L22: trims the most significant digit if it is 0.

What are tradeoffs to make the size of result to be m instead of m+1 and vice versa?

The following shows addDifferentSign() that throws UnsupportedOperationException:

/**
 * Adds the specific integer that has a different sign from this integer.
 * @param n the integer to be added with a different sign
 */
protected void addDifferentSign(LongInteger n) {
    throw new UnsupportedOperationException();
}

The implementation of addDifferentSign() is quite similar to addSameSign() although it involves a few more logics. We will leave this as an exercise.

In practice, addSameSign()and addDifferentSign() should be private. We made them protected for exercise purposes.

Method: multiply()

Let us override the multiply() method:

@Override
public void multiply(LongInteger n) {
    // set this.sign
    sign = (sign == n.sign) ? Sign.POSITIVE : Sign.NEGATIVE;

    // multiply this and n and save it to result
    byte[] result = new byte[digits.length + n.digits.length];
    for (int i = 0; i < digits.length; i++) {
        for (int j = 0; j < n.digits.length; j++) {
            int k = i + j, prod = digits[i] * n.digits[j];
            result[k] += prod;
            result[k + 1] += result[k] / 10;
            result[k] %= 10;
        }
    }

    // set this.digits
    int m; for (m = result.length - 1; m > 0; m--)
        if (result[m] != 0) break;
    digits = ++m < result.length ? Arrays.copyOf(result, m) : result;
}

• L4: sets the sign after the multiplication.

• L7-15: multiplies n to this integer:

  • L7: the max-dimension of results is digits.length + n.digits.length.

  • L12-13: pass a carry to the next digit.

• L18-20: trims the most significant digit iteratively if it is 0.

  • L20: ++m increments m before the comparison.

What is the worst-case complexity of the multiply() method?

Method: main()

Let us create a runnable class called LongIntegerRun that contains the main method:

Can we define the main method in LongInteger instead without creating LongIntegerRun?

public class LongIntegerRun {
    static public void main(String[] args) {
        System.out.println(args);
    }
}

• L2: the parameter args is passed from the command line.

Why does the main method need to be static?

This prints something like the following:

[Ljava.lang.String;@d716361

• [: one-dimensional array.

• L: the element of this array is an object.

• java.lang.String: the type of object.

• d716361: the hash code of this array in hexadecimal.

What is the hash code of an object?

Every object implicitly inherits Object that defines a few member methods including toString(), which gets called automatically by the println() method to retrieve the string representation of this object. We can use the helper method Arrays.toString() that gives a more readable representation:

static public void main(String[] args) {
    System.out.println(Arrays.toString(args));
}

How is the Arrays.toString() method implemented?

Since no argument is passed to the main method at the moment, this prints an empty array:

[]

If you set the arguments to 123 -456 using the [Run - Edit Configurations - Program arguments]setting, it prints the following array:

[123, -456]

Given those two arguments, we can create two integers:

static public void main(String[] args) {    
    LongInteger a = new LongInteger(args[0]);
    LongInteger b = new LongInteger(args[1]);
    
    System.out.println(a);
    System.out.println(b);
}

This prints something like the following, which are returned by a.toString():

edu.emory.cs.algebraic.LongInteger@4d7e1886
edu.emory.cs.algebraic.LongInteger@3cd1a2f1

How is the toString() method implemented in the Object class?

Method: toString()

To print a more readable representation, we need to override the toString() method in LongInteger:

public class LongInteger extends SignedNumeral<LongInteger> {
    ...
    @Override
    public String toString() {
        StringBuilder build = new StringBuilder();
        if (sign == Sign.NEGATIVE) build.append("-");
        for (int i = digits.length - 1; i >= 0; i--)
            build.append(digits[i]);
        return build.toString();
    }
    ...

• L5: StringBuilder provides an efficient way of concatenating different data types into one string.

What are the advantages of using StringBuilder instead of concatenating values with the + operator as follows:

String s = "";
if (sign == Sign.NEGATIVE) s += "-";
for (int i = digits.length - 1; i >= 0; i--)
    s += digits[i];
return s;

Given the overridden method, the above main method now prints the following:

123
-456

What are the advantages of overriding toString() instead of creating a new method with the same code, and calling the new method to get the string representation of LongInteger?

Method: compareTo()

Java does not allow operator overloading, so it is not possible to use logical operators to compare the two integers above, a and b:

boolean c = a < b;  // gives a compile error

In fact, any object that is comparable must inherit the interface Comparable as follows:

public class LongInteger extends SignedNumeral<LongInteger> 
                         implements Comparable<LongInteger> {
...
}

• L2: LongInteger is passed to Comparable as a generic type.

Is extends always used to inherit a class whereas implements is used to inherit an interface?

The Comparable interface contains one abstract method called compareTo() that returns a negative value if this object is smaller than n, a positive value if this object is greater than n, and zero if this object equals to n. The compareTo() method must be overridden by the LongInteger class:

@Override
public int compareTo(LongInteger n) {
    if (isPositive())
        return n.isNegative() ? 1 : compareAbs(n);
    else
        return n.isPositive() ? -1 : -compareAbs(n);
}

The compareAbs() method compares the absolute values of this and n:

/**
 * @param n the object to be compared.
 * @return a negative integer, zero, or a positive integer as the absolute value of this object is
 * less than, equal to, or greater than the absolute value of the specified object.
 */
public int compareAbs(LongInteger n) {
    int diff = digits.length - n.digits.length;

    if (diff == 0) {
        for (int i = digits.length - 1; i >= 0; i--) {
            diff = digits[i] - n.digits[i];
            if (diff != 0) break;
        }
    }

    return diff;
}

• L7: if digits has more dimensions, its absolute value is greater.

• L10-13: compares the significant digits iteratively.

Is it safe to use the same variable i to iterate both digits and n.digits?

Once LongInteger properly inherits Comparable by overriding compareTo(), objects instantiated by this class can be compared using many built-in methods.

static public void main(String[] args) {
    List<LongInteger> list = new ArrayList<>();
    
    list.add(new LongInteger("78"));
    list.add(new LongInteger("-45"));
    list.add(new LongInteger("0"));
    list.add(new LongInteger("6"));
    list.add(new LongInteger("-0"));
    list.add(new LongInteger("-123"));
    
    list.sort(Comparator.naturalOrder());
    System.out.println(list);

    list.sort(Comparator.reverseOrder());
    System.out.println(list);
}

• L2: ArrayList is a specific implementation of the interface List.

  • All collections in Java inheriting AbstractCollection uses generics.

  • <>: the diamond operator that infers the generic type from its declaration.

• L11: sorts the list in ascending order using sort() and Comparator.naturalOrder().

• L14: sorts the list in descending order using sort() and Comparator.reverseOrder().

What is the advantage of declaring list as List instead of ArrayList? What kind of sorting algorithm does Collections.sort() use?

The above code prints the following sorted lists:

[-123, -45, -0, 0, 6, 78]
[78, 6, 0, -0, -45, -123]

What would be the case that needs to distinguish -0 from 0?