Description
Introduction
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 + 𝑎1 𝑏𝑎𝑠𝑒 + 𝑎2 𝑏𝑎𝑠𝑒2 + … + 𝑎𝑛−1𝑏𝑎𝑠𝑒𝑛−1
𝑖=0
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<Integer> class. Coefficients order was described above. The starter code for the class also contains:
- code stubs of the methods that you are required to implement.
- helper methods that you are free to use, namely clone(), timesBaseToThePower(), compareTo(), toString(). You are not allowed to modify these helper methods.
- a Tester class with a simple example. Modify this example to test your code.
Your Task
Implement the following methods. We suggest you implement them in the order given. The signatures of the methods are given in the starter code. You are not allowed to change the signatures.
1) plus (30 points)
Implement the grade school addition operation.
We call it plus rather than add to avoid confusing it with the add method for lists. It is the easiest of the four methods to implement.
2) times (30 points)
Implement the grade school multiplication method. Do not store the rows in a 2D table. Instead, when you compute each row in the table, add it to an accumulated sum (using use the plus() method) which is initialized to zero. Once you have added a row, you can discard it. To compute each row, we suggest that you write a helper method timesSingleDigit() that multiplies the caller NaturalNumber object with a single digit.
The starter code provides a slow multiplication method which uses repeated addition. You should use this method to verify the correctness of your times() method for small operands.
Note how slow the ‘slow method’ is relative to grade school multiplication for large operands.
3) minus (25 points)
Implement the grade school subtraction method. The starter code verifies a.minus(b) > 0, so you can assume this in your tests.
Although this question is worth fewer points, it is perhaps more challenging than the first two, because it can be tricky to handle the borrowing properly.
4) divide (15 points)
Implement the grade school long division algorithm which is a fast algorithm for performing integer division. This is the most challenging question since you will need to figure out for yourself what this algorithm does.
We have provided you with a slow division method which is based on repeated subtraction. This is mainly to verify the correctness of your code on small inputs.
Other Requirements
Use Java naming conventions for variable names e.g. variables and method names should be mixed case with a lower case first letter.
Although your solution will be tested and graded automatically, it sometimes happens that the TA/grader needs to examine the code. In this case, it is helpful if you have added comments to describe what your solution is doing. We reserve the right to penalize you for poor style e.g. non-existing or unhelpful comments, or improper indentation. Eclipse does proper indentation automatically, as do other excellent IDEs.
Tips
We suggest that you begin by testing your code on numbers that are written in base 10. Once that is working, test it on bases 2 to 9. Use an online converter to verify your answers e.g.
http://www.cleavebooks.co.uk/scol/calnumba.htm
You may write your own helper methods, but if you do then you must be sure to document them, so that the TA grader it can easily follow what you are doing.
Some methods in the starter code “clone” the operands and work with the cloned ones rather than the original ones. This is done because the methods change the operands. For example, some methods are just easier to implement if the two operands have the same number of digits. So, if in some instance the two operands don’t have the same number of digits, then we clone and modify the smaller one by appending higher order digits with value 0. Second, a method might change the digits of one of the operands. For example, the subtraction operation a.minus(b) may require “borrowing” from higher to lower powers for the number a.
The code uses a LinkedList rather than an ArrayList. There is no significance to this, and we could have used an ArrayList instead. The advantages of using the LinkedList class is that it has methods addFirst() and addLast() which make code easier to read. Also, the method addFirst(element) is more efficient for LinkedList than the corresponding add (0, element) for an ArrayList. The disadvantage of using LinkedList is that the algorithms sometimes iterate over the coefficients, e.g. using a for loop over coefficients.get( index ) with an index variable, and this is an inefficient way to iterate through linked lists, as I’ve argued in the lecture. This an important issue in practice and you should think about it when studying array lists versus linked lists, but we will ignore this particular inefficiency for the assignment.
Get started early! Have fun! Good luck!
