Starting from:
$30
COMP250-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 + 𝑎1 𝑏𝑎𝑠𝑒 + 𝑎2 𝑏𝑎𝑠𝑒2 + … + 𝑎𝑛−1𝑏𝑎𝑠𝑒𝑛−1
𝑖=0
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
There are several learning goals
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
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.
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
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
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 = 23 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.
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 + 𝑎1 𝑏𝑎𝑠𝑒 + 𝑎2 𝑏𝑎𝑠𝑒2 + … + 𝑎𝑛−1𝑏𝑎𝑠𝑒𝑛−1
𝑖=0
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
There are several learning goals
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
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.
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
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
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 = 23 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.
1 file (6.6KB)
