Description
Computers represent integers as binary numbers (base 2), typically using a relatively small number of bits e.g. 16, 32, or 64. In Java, integer primitive types short, int and long use these fixed number of bits, respectively. Using a fixed number of bits for integers limits the range of values that one can work with, however. This limitation is a significant problem in cryptography, for example, where one uses large integers to transform files so that they are encrypted.
For any base, one can represent any positive integer p uniquely as the sum of powers of the base. This defines a polynomial:
? = ∑ ??
?−1
?=0
????? = ?0 + ?1 ???? + ?2 ????2 + … + ??−1?????−1
where the coefficients ?? satisfy 0 ≤ ?? < ???? and ??−1 0. The last condition is important for uniqueness and comes up below in the Tips where we briefly discuss the case that two operands have a different number of digits.
The positive integer p can be represented as a list of coefficients (?0 ,?1 ,?2 , … ??−1). The ordering of the coefficients is opposite to the usual ordering that we use to represent numbers, namely ??−1 … ?2 ,?1 ,?0 e.g. integer 35461 is represented as a list of coefficients (1,6,4,5,3).
In this assignment, you will implement basic arithmetic operations on large positive integers. Java has class for doing so, called BigInteger. You will implement your own version of that class. In particular, you will implement basic arithmetic algorithms that you learned in grade school. Your representation will allow you to perform these operations in any base from 2 to 10. The methods could be extended to larger bases but we will not bother since it would require symbols for the numbers {10, 11, ..} and otherwise the solution would be the same.
You are given a partially implemented NaturalNumber class. The class has two private fields: base and coefficients. The coefficients ?? of the number are represented using the LinkedList
