Problem $4$: BigInt: a class for large integers

$60$ points total; individual$-$only

Overview

In Java, the int data type can only represent integers from $-2,147,483,648$ to $2,147,483,647.$ This isn$$t big enough to

store very large numbers$$for example, the population of Earth $($approximately $7\mathrm{.}53$ billion as of $2017)$or to compute n$!$ for large values of n$.$

The Java libraries contain a built$-$in class called BigInteger to handle arbitrarily large integers. In this problem, you will write your own class called BigInt that has a subset of the functionality of the built$-$in Java class.

Representing integers using an array of digits

Each BigInt object will use an arrays of integers, where each element of the array represents a single digit of the integer.

We will design the class to handle non$-$negative integers with up to $20$ digits, and thus the array will have a length of $20.$

For example, the integer $57431$ would be represented using this array:

$\{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,7,4,3,1\}$

Note that:

Each element of the array is a single digit $($i$.$e$.,$ an integer from $0-9).$

The last element of the array represents the least significant digit of the integer $($i$.$e$.,$ the rightmost digit$).$

The first non$-$zero element $($if there is one$)$ represents the most significant digit of the integer. $($The one exception is when we are representing $0$ itself. Its most significant digit is the same as its least significant digit, and it is a zero!$)$

The remaining elements are leading zeros that are not significant digits.

As another example, the integer for $7\mathrm{.}53$ billion would be represented using the array

$\{0,0,0,0,0,0,0,0,0,0,7,5,3,0,0,0,0,0,0,0\}$

Task $0$: Download and review our starter code

Begin by downloading the following starter file: BigInt.java

Open this file in your IDE and review its contents. We have given you:

a class constant called MAX$\_$SIZE that represents the largest number of digits that a BigInt object can have. It will be used when constructing the array of digits.

an instance member digits, which holds a reference to the array of integers in which the digits are stored. The array of digits represents the large integer.

an instance member numSigDigits, which stores the number of significant digits in the integer. This is the same as the number of digits in the integer when it is written without leading zeroes. For example, for a BigInt that represents the integer $57431,$ numSigDigits should be $5,$ and for a BigInt that represents the integer $31,$ numSigDigits should be $2.$ This internal member should be correct for all objects, including the objects that are produced when computing the sum and the product.

a default constructor $($i$.$e$.,$ one that takes no arguments$)$; it creates a BigInt object representing the number $0.$

a set of tests in the body of a main method. At the moment, these tests are commented out, but you should gradually uncomment them and run them as you add functionality to the class.

Important guidelines

You may not add any additional fields to the BigInt class.

You may not use any variables of type long, any of Java$$s built$-$in classes for numbers $($Long$,$ BigInteger, etc.$),$ or any of Java$$s built$-$in collection classes $($e$.$g$.,$ ArrayList$).$

Task $1$: Add your first of several custom constructors

$1.$ Add a custom constructor with the following header:

public BigInt$($int$[]$ arr$)$

It should use the contents of the array that is passed in as the basis of the new BigInt object. For example, we should be able to create a BigInt for $57431$ as follows:

int$[]$ arr $=\{5,7,4,3,1\}$;

BigInt val $=$ new BigInt$($arr$)$;

Suggested approach:

Validate that a valid array has been passed to the Constructor and, the array has a length between $0$ and MAX$\_$SIZE. If the parameter is null, if the length of the array is greater than MAX$\_$SIZE, or if any of the elements of the array don$$t make sense as digits, the method should throw an IllegalArgumentException.

Note: You may want to consider writing a private helper method that helps validate that an element is a valid digit. In general, we encourage you to use a private helper method whenever doing so would help to decompose and simplify$*$ your code and$/$or your logic.$*$

Create and initialize the digits array from the input array arr. You cannot assume that the array passed to the method has a length of MAX$\_$SIZE. It cannot have a length greater than MAX$\_$SIZE but, it can be less. Make sure to validate each element before assigning to the digits array.

The constructor should also determine and initialize the correct value for the numSigDigits field. Make sure that you don$$t include non$-$significant leading zeroes in the value that you compute for numSigDigits.

Important: Make sure that the digits field ends up referring to a new array of length MAX$\_$SIZE. You should not make it refer to the array that is passed in$.$