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 FFT and NewNumber, and their appropriate methods (5 in total) so that the entire test program will run.

1. (20 points) Define a version of the Extended Euclidean algorithm that works purely top down. More precisely, define a recursive function that takes nonnegative integers r and n and returns the reciprocal of r mod n (or 0 if none exists) by maintaining, for any subproblem with arguments u and v, values i_u, i_v, j_u, and j_v such that u = i_ur + j_un and v = i_vr + j_vn. Note that it's easy to find initial values for i_u, i_v, j_u, and j_v, and that it's easy to determine the desired answer from their final values. You may still reduce directly from arguments u and v to arguments v and u mod v, assuming that u >= v. Your method (or function) is to return a nonnegative integer less than n.

   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.

2. (25 points) Define a static method binaryReciprocal that 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).

3. (25 points) Define two static methods naivePower and fancyPower for the NewNumber class that each take a base of class java.math.BigInteger and 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.

   The NewNumber class is also to maintain a simulated timer and methods getClockTime and 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 A4.main.

4. (30 points) Programming version: Define an class FFT with 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 Z_p.

   If you instead choose to work by hand, test your algorithm on the two products: (x+2)(3x-4) and (2x³+x²+2x-2)(x³-x+2). Use the algorithm in the textbook, and show the values of the polynomials a^even and a^odd, and the sequences y^even and y^odd, 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.

As always, you may add any other public or private methods or classes you find useful.