COMP 250 Assignment 2

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. For certain applications such as in cryptography, however,

one needs to work with very large positive numbers and do arithmetic operations on them. For

such applications, it is necessary to go beyond the primitive type representation.

How can one represent a very large positive integer? For any base, one can represent any

positive integer m uniquely as the sum of powers of the base. This defines a polynomial:

𝑚 = ∑ 𝑎𝑖

𝑛−1

𝑖=0

𝑏𝑎𝑠𝑒𝑖 = 𝑎0 + 𝑎1 𝑏𝑎𝑠𝑒 + 𝑎2 𝑏𝑎𝑠𝑒2 + … + 𝑎𝑛−1𝑏𝑎𝑠𝑒𝑛−1

where 𝑏𝑎𝑠𝑒 is some number (e.g. 2, 10), and the coefficients 𝑎𝑖 satisfy 0 ≤ 𝑎𝑖 < 𝑏𝑎𝑠𝑒 and

𝑎𝑛−1 > 0. Note that the condition 𝑎𝑛−1 > 0 is required for a unique representation. Also note

that when a positive integer m is 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 write out the number,

namely 𝑎𝑛−1 … 𝑎2 ,𝑎1 ,𝑎0 . For example, the integer 35461 is represented as a list of coefficients

(1,6,4,5,3).

In this assignment, we will work with arithmetic operations on large positive integers. Java has

built-in class for doing so, called BigInteger. You are not allowed to use this class. Instead

you will work with a partially implemented class MyBigInteger. Whereas the Java class

BigInteger can be used for negative and positive, our class MyBigInteger only allows us to

represent non-negative integers.

The MyBigInteger class has two fields: base and coefficients. The base field is an int with

values in {2, 3, …, 10}. We could have allowed for larger bases but that would have required

using special symbols for the numbers greater than 10, e.g. as in hexadecimal, and these extra

symbols would just complicate things. The coefficients field is an ArrayList<Integer> which

represents the 𝑎𝑖 values above.

We provide you an implementation of three of the four arithmetic algorithms that you learned in

grade school and that were discussed in lecture 1, namely plus(), times(), minus(). We also

include slow versions of slowTimes() and slowdividedBy() which implement the slow

multiplication and slow division algorithms that were mentioned in class.

We include several helper methods as well.

timesBaseToThePower()

mod()

clone()

compareTo()

toString()

primesToN().

For all of the methods, you should read the comments in the code to see what the methods do.

You are also given code stubs of the methods that you are required to implement, and a Tester

class with a simple example. Feel free to modify this Tester class as you wish.

What will you learn by doing this assignment?

There are several learning goals for this assignment.

First, you will understand much better how grade school arithmetic algorithms work and

hopefully understand their time complexity. You have been using arithmetic operations of +, – ,

*, / since you were a child and so you take them for granted. After doing this assignment, you

should understand these algorithms much better than you did before, in particular, the division

algorithm which you are asked to implement.

Second, the assignment will help understand how to represent numbers in different bases. The

definition of this representation was given on the previous page. But there are some subtleties

in that definition that arise. For example, converting a number from one base representation to

another can be tricky since the base itself that is used for the conversion method is a number

that needs to be represented in some base.

Third, one of your tasks is to work with prime numbers. Although prime numbers will arise only

occasionally in this course, they are extremely important in some application areas of computer

science such as in cryptography. Those of you taking MATH 240 Discrete Structures 1 or

MATH 346 Number Theory will be working with prime numbers. Your experience here should

complement what you will learn in those courses.

Fourth, you will get some experience working with lists. In particular, you will use methods from

the Java ArrayList class.

Lastly, this assignment will also give you more practice programming in Java! Although COMP

250 is not a course about how to program, programming is a core part of computer science and

the more practice you get, the better you will become at it.

Your Tasks

Implement the following methods. The signatures of the methods are given in the starter code.

You are not allowed to change the signatures.

Question 1: dividedBy (30 points)

Implement the dividedBy method using long division. An example of long division is given in

the lecture 1 notes PDF. This example gives the main idea of how the algorithm works.

Before attempting to write any code, study the implementations of the plus(), times(), minus()

and the various helper methods that are given to you. Make sure you understand about how

they work, since similar ideas can be used to implement dividedBy().

If you are unable to solve this question first and you wish to work on Questions 2 and 3 in the

meantime, then you may simply call the slowdividedBy() method from within the dividedBy()

instead. However, note that you will only be able to run your solution for small numbers.

We will test your dividedBy() method on moderate size numbers, with the intention of detecting

relatively slow implementation. The time complexity of your dividedBy() method should be

𝑶(𝑵𝟐

) whereas the time complexity of slowdividedBy() is 𝑶(𝒃𝒂𝒔𝒆𝑵), where 𝑵 is the number

of digits of the dividend. If your implementation runs extremely slowly, e.g. if you were to just

copy the code from the slowdividedBy() method, then you will not receive any points for this

question.

Question 2: Base conversion (40 points)

Implement a method convert( int newBase ) that converts a MyBigInteger object from one

base to another. The convert method is called by a MyBigInteger object that represents a

positive integer in some base, and returns the same positive integer represented in the new

base. The bases can be any of {2, 3, 4, …, 10}.

Begin by testing your methods on numbers that are written in base 10. Once that is working,

test it on combinations of different bases from 2 to 10. Use an online converter to verify your

answers e.g. http://www.cleavebooks.co.uk/scol/calnumba.htm for small numbers. Your code

will be tested on very big numbers.

Hint: You may wish to handle three cases separately, depending on whether the original base

is smaller than, equal to, or larger than the new base.

Question 3: Prime Numbers (30 points)

A prime number is a positive integer 𝑚 > 1 whose factors are only 1 and itself. So, a number 𝑚

is prime if dividing it by any number in {2, …, 𝑚 − 1} produces a non-zero remainder. By

definition, 𝑚 = 1 is not prime.

Any positive integer 𝑚 can be written uniquely as a product of primes:

𝑚 = 𝑝1

𝛼1𝑝2

𝛼2 … 𝑝𝑘

𝛼𝑘

where 𝑝𝑖 are called prime factors and 𝛼𝑖 > 0 are the non-zero orders of the prime factors. For

example, 24 = 2

3 3

1

.

One can determine if a number 𝑚 is prime by brute force checking all the integers from 2 up to

𝑚 − 1 to see if any of them divides evenly with no remainder. However, this method is very

inefficient. It is enough to check potential factors less than or equal to √𝑚. Think why.

1

Your task is to implement a method primeFactors().

The method must return an ArrayList<MyBigInteger> whose elements are the prime factors of

𝑚, where 𝑚 is ‘this’ MyBigInteger object. The number of copies of the prime factor in the

returned list must be the order of that prime factor, and the prime factors in the list must go from

smallest to largest. For example, if 𝑚 = 24, the method must return a list (2, 2, 2, 3). If 𝑚 is

prime or if the method cannot find any prime factors, then the returned list will just contain one

element, namely, the returned list will be (𝑚). You do not need to handle the case 𝑚 = 0, 1.

For testing purposes, you may wish to have a list of prime numbers. We provide you with

efficient code for computing them. The code is an implementation of an ancient algorithm

called the Sieve of Eratosthenes which computes all the primes up to some given limit, say 𝑛.

This code is given to you as a helper method primesToN(). The maximum value of 𝑛 that you

can use is ultimately limited by the size of the JVM’s memory. One way you can use this code

is to generate large prime numbers, and then multiply these large prime numbers together to

yield a very large non-prime number. (Any number that is a product of at least two primes is

called a composite number.) This process is closely related to problems in cryptography where

one person multiplies two large prime numbers together, and the other person is given the

product and tries to compute what the two original (prime) numbers were.

We will run your primeFactors() method on some very big composite numbers. If your method

does not complete within an allocated time, then it will deemed to fail the stress test. Note that

such a failure may be only due to an inefficient dividedBy() method. In this case, you will be

double penalized for having a slow dividedBy() method. So make sure your dividedBy()

method passes its stress test.

1 Since you are only looking for prime factors, in theory you only need to check potential factors that are

themselves prime. But to only check prime factors, you would need to know in advance which potential

factors are prime, which would require some work in itself. For this assignment, we don’t require you to

restrict your checks in this way.

Other Notes

The solution that you submit will be tested and graded automatically. However, 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. If we need to check your code and

we find it is unreadable, then we reserve the right to penalize you for this.

Eclipse does proper indentation automatically, as do other excellent IDEs. So please use it.

Be sure to use Java naming conventions for variable names. In particular, variables and

method names should be mixed case with a lower case first letter.

Plagiarism

The solution that you submit must be your own work. You are expected to write the required

methods by yourself, that is, without copying anyone else’s coded solution. As stated in the

Course Outline, we will run software that examines the similarity of pairs of submissions. If two

student submissions are unusually similar, then the software will flag this. The TA’s and the

instructor will then compare the code by hand and if plagiarism is suspected then the case will

be reported to a Disciplinary Officer. See the Course Outline for further details.

Get started early! Have fun! Good luck!

## Reviews

There are no reviews yet.