HW#4 --- last modified March 02 2019 21:25:40..
Solution set.
Due date: Apr 24
Files to be submitted:
Hw4.tex
Prime.zip
Purpose:To learn about computer algebra and number theoretic algorithms
Specification:
First, do the following problems out of CLRS and submit them in Hw4.tex : 31.1-7, 31.2-4, 31.5-1, 31.7-3.
Then I would like you to write a java program Prime.java which will be run from the command line with a line
like:
java Prime file.txt confidence
Here the command line argument file.txt is the name of a file whose contents will be read by your program; the command
line argument confidence is supposed to be an integer such that the odds of failure of your algorithms are less
than 2-confidence.
Your program should read out of this file a sequence of ASCII digits between 0-9 which represent some
number which might be a prime number. This sequence of digits with be hundreds of characters long. Your program
then runs your implementation of the Miller-Rabin algorithm from page 892. This algorithm will be quite challenging
to implement. If you are not already working in a group, it is strongly advised you join a group in order to have
some chance of completing this project. Fortunately, the implementation of the algorithm can be split into several
testable subgoals which I can give partial credit for. You can implement each of these separate subgoals in a class
by itself and submit the whole project as Prime.zip. The classes I would like to see are ToBinary, ToDecimal, Multiply, Add,
Subtract, Divide, Mod, ModularExponentiation. Each class should have public methods which can be used by the other classes if
needed. In addition, each class should have a main which can be used to test it from the command line. A specification for how
each class should act on the command line is described below:
ToBinary: If run with a line like:
java ToBinary file.txt
ToBinary should read a sequence of ASCII digits between 0-9 from file.txt and it should output the ASCII for the
corresponding
binary number. It should work for files containing hundred or thousands of digits.
ToDecimal: If run with a line like:
java ToDecimal file.txt
ToDecimal should read a sequence of ASCII binary digits (either 0 or 1) from file.txt and it should output the ASCII for
the
corresponding decimal number. It should work for files containing hundred or thousands of digits.
Add: If run with a line like:
java Add file1.txt file2.txt
Add should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It
should then output a sequence of ASCII binary digits which is the result of adding these two numbers. It should work for
files containing hundred or thousands of digits.
Subtract: If run with a line like:
java Subtract file1.txt file2.txt
Subtract should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It
should then output a sequence of ASCII binary digits which is the result of subtracting these two numbers. It should work for
files containing hundred or thousands of digits.
Multiply: If run with a line like:
java Multiply file1.txt file2.txt
Multiply should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It
should then output a sequence of ASCII binary digits which is the result of multiplying these two numbers. It should work for
files containing hundred or thousands of digits.
Multiply: If run with a line like:
java Divide file1.txt file2.txt
Divide should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It
should then output a sequence of ASCII binary digits which is the result of dividing these two numbers (number of file1
divided by number of file 2). It should work for
files containing hundred or thousands of digits.
Mod: If run with a line like:
java Mod file1.txt file2.txt
Mod should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from file2.txt. It
should then output a sequence of ASCII binary digits which is the result of modding these two numbers (number of file1 mod
the number of file2). It should work for
files containing hundred or thousands of digits.
ModularExponentiation: If run with a line like:
java ModularExponentiation file1.txt file2.txt file3.txt
ModularExponentiation should read a sequence of ASCII binary digits (either 0 or 1) from file1.txt and similarly from
file2.txt and file3.txt. Let x, y, z denote respectively the numbers parsed out of file1, file2, and file3. It
should then output a sequence of ASCII binary digits which is the result of xy mod z. It should work for
files containing hundred or thousands of digits.
Point Breakdown
Book problems (1pt each) |
4pts
|
Departmental coding guidelines for Java followed |
1pt
|
ToBinary, ToDecimal, Multiply, Add, Subtract, Divide, Mod, ModularExponentiation work as describe(1/2 point each) |
4pts
|
Prime.java works as described |
1pt
|
Total | 10pts |
|