Parts 2 and 3 of this assignment are programming problems. Parts 1 and 4 may be done by defining the appropriate Java methods, or by hand. In any case you will need to define classes
NewNumber, and their appropriate methods (5 in total) so that the entire test program will run.
If you define a Java method to do this part, your method is to be a static method of the
NewNumber class and have the name
newReciprocal. If you do this part by hand, test with the arguments r=49 and n=1000.
binaryReciprocalthat extends the Binary Euclid's algorithm of p. 457 of our text so that it computes and returns the reciprocal of x mod n. If x and n are not relatively prime, you are to return 0.
It's probably easiest to mimic the Extended Euclidean algorithm, and find i and j with ix + jn = 1. Do be careful that i and j are integers. One observation that may be helpful in this regard is that if ia + jb = 1, then (i+b)a + (j-a)b = 1 and (i-b)a + (j+a)b = 1. Your method is to return a nonnegative integer less than n.
For partial credit (15 points), you may instead rewrite and code this
EuclidBinaryGCD algorithm so that it's tail recursive -- that is, so that the result of each recursive call is returned directly without further processing. You may use auxiliary methods as long as they are tail recursive. Test with the test cases given in
A4.java as well as the additional pairs (2460, 1000) and (24600, 1000).
NewNumberclass that each take a base of class
java.math.BigIntegerand an exponent of type
int, and return the result (as an instance of
java.math.BigInteger) of raising the given base to the given power. The first of these methods is to use a version of the NaiveExponentiation algorithm on p. 462 of the text, while the second is to use a version of the FastExponentiation algorithm on p.463 of the text. But note that in neither case are you to compute your powers mod n.
NewNumber class is also to maintain a simulated timer and methods
resetClock that respectively return the
long value of the clock, and set the timer value to 0. The timer is to be incremented after every multiplication by the product of the lengths of the factors.
Presumably you will need to use methods and fields of the
java.math.BigInteger class, along the lines of their use in
FFTwith a public method
multiply, which takes two arrays of
doubles representing coefficients of polynomials (constant term first) and returns an array of
doubles representing the product polynomial. This method is to use the Fast Fourier Transform algorithm to multiply the polynomials. You may ignore any rounding errors that appear in the coefficients of your products. Use the pseudocode in the textbook (but make sure you give appropriate credit). Do use complex numbers rather than nth roots of 1 in some Zp.
If you instead choose to work by hand, test your algorithm on the two products: (x+2)(3x-4) and (2x3+x2+2x-2)(x3-x+2). Use the algorithm in the textbook, and show the values of the polynomials aeven and aodd, and the sequences yeven and yodd, using a tree diagram like that used in the "Cormen, Ch 30, convolution example, n=8" in the handout at http://www.cs.sjsu.edu/faculty/smithj/oldclass/288s07/exs-solutions.html.
mainmethod of) the
A4class, available on the class web site. You are to turn in hard and soft copies of your class definitions. You are also to turn in a hard copy of the results of your tests, and of any work that you do by hand for problems 1 and 4.
As always, you may add any other public or private methods or classes you find useful.