| Data Type | Range of Values |
|---|---|
| byte | -27 .. 27-1 |
| short | -215 .. 215-1 |
| int | -231 .. 231-1 |
| long | -263 .. 263-1 |
The corresponding wrapper classes in the java.lang package (Byte, Short, Integer, and Long) all suffer from the same limitation, as an instance of any of these classes simply acts as a "wrapper" around a value of the similarly-named primitive data type.
However, some applications require calculations with integers whose magnitudes may be arbitrarily large, meaning that no particular upper bound can be known ahead of time. For applications such as these, none of the Java data types mentioned above are suitable. Which is why Java's standard library includes the class java.math.BigInteger.
Instances of BigInteger can represent integers of any magnitude, limited only by conditions imposed by the environment in which a program is running, such as how much memory is available. The class's documentation uses the phrase "arbitrary-precision integer", which refers to there being no upper bound ("arbitrary") on the number of digits ("precision") used in representing a number.
For this assignment, you are to complete the development of the Java class UnboundedNatural, instances of which provide a small subset of the functionality of Java's BigInteger class.
Specifically, an instance of UnboundedNatural can represent any natural number (i.e., nonnegative integer), with no upper bound on its magnitude. (Negative numbers are not representable.) The operations supported include only test-for-equality, addition, subtraction, and multiplication.
As with Java's BigInteger class, instances of UnboundedNatural are immutable, which is to say that the class includes no mutator methods. Rather, the methods that implement the arithmetic operations are generators, which means that they produce new instances of the class rather than modifying the state of any already-existing instance. For example if x and y refer to instances of UnboundedNatural, the method call
returns a new instance of the class representing the sum of the values represented by x and y. The states of the objects referred to by x and y are not changed.
Welcome to the UnboundedNatural Calculator! > 35672305934 + 67891054 Computing 35672305934 + 67891054 35740196988 > 8792345664223455 - 123456 Computing 8792345664223455 - 123456 8792345664099999 > 4569834 = 542455 Computing 4569834 = 542455 false > 4569834 = 4569834 Computing 4569834 = 4569834 true > 99999 * 10000000 Computing 99999 * 10000000 999990000000 > Goodbye. |
Given that you are probably much more familiar with decimal numerals than with numerals of any other base, it is suggested that you design your UnboundedNatural class to make use of a sequence of decimal digits for the purpose of representing a number. The two most obvious alternatives are thus to use an instance variable of type int[] or one of type ArrayList<Integer>.1. (Here is a sample program that makes use of an ArrayList.)
Each choice has its advantages and disadvantages. The major advantage of using an ArrayList is that it can grow and shrink in length "automatically", while an array's length is fixed.
Whichever choice you make, it is strongly suggested that the digits be stored in a least-to-most significant order, as this will make the code implementing addition and subtraction much simpler. For example, assuming that the instance variable is named digits (whether it is an array or an ArrayList), the integer 8603472 should be stored like this:
0 1 2 3 4 5 6
+---+ +---+---+---+---+---+---+---+
digits | *-+---------->| 2 | 7 | 4 | 3 | 0 | 6 | 8 |
+---+ +---+---+---+---+---+---+---+
|
As for how to implement the various operators, for addition and subtraction think back to the algorithms that you learned in elementary school. Both involve iterating through the digits of the two operands, going from least significant digit to most significant. Addition involves a "carry" from one column to the next, while subtraction involves "borrowing" from the next column.
To implement multiplication, you are encouraged to make use of this characterization of that operation:
| k * m = { | 0 | if k = 0 |
| k/2 * 2m | if k>0 and k is even | |
| ((k-1)/2 * 2m) + m | if k>0 and k is odd |
To support taking this approach, it will be very useful to have methods for doubling and for halving instances of UnboundedNatural. Stubbed versions of such methods are included in the provided code. To produce the double of a number using the plus() method is trivial. As for halving (more precisely, computing ⌊k/2⌋ for a given natural number k, which is equivalent to (k-1)/2 when k is odd), here is a pseudocode algorithm:
|
Given is a decimal numeral
dn-1dn-2··d1d0
(where each di is in the range [0..10)) representing the
natural number D = Σ0≤i<n
di·10i.
Produced is the decimal numeral rn-1rn-2··r1r0 that represents ⌊D/2⌋.
carryIn = 0;
i = n;
do {
i = i-1;
ri = (di + carryIn) / 2;
if di is even
{ carryIn = 0; }
else
{ carryIn = 10; }
} while i != 0;
|
[1] To make objects of UnboundedNatural more memory-efficient, you could use an instance variable of type byte[] or ArrayList<Byte> instead, but that would make doing arithmetic a little less convenient. Why? Because Java's arithmetic operators (+, -, etc.) produce values of type int even when the operands are of type, say, byte. To store the result as a value of type byte, it is necessary to perform a cast, as in (byte)(k+m).
It would also be reasonable to use an instance variable of type char[] or ArrayList<Character>.