# COMP 250 Assignment 1 Solved

30.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

# 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

𝑝 = ∑  𝑎𝑖  𝑏𝑎𝑠𝑒𝑖 = 𝑎+ 𝑎𝑏𝑎𝑠𝑒 + 𝑎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  ,𝑎  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.

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)

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.