COMP 250 Assignment 2 Solved

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
++
2
2
+
… +
  −1
  −1





1







  =0












whereis some number (e.g. 2, 10), and the coefficients

satisfy
0 ≤   <and
  −1 > 0  for any   > 0.
[ADDED: Nov 14]
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). Note = 0 is represented as (0).

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:
=    1122…

where are called prime factors and > 0 are the non-zero orders of the prime factors. For example, 24 = 23 31.

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!