### Assignment #4, CS 155, Section 1

#### due November 13, 2007 100 points

final version

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 iu, iv, ju, and jv such that u = iur + jun and v = ivr + jvn. Note that it's easy to find initial values for iu, iv, ju, and jv, 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 `double`s representing coefficients of polynomials (constant term first) and returns an array of `double`s 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.

You are to test your classes by executing the (`main` method of) the `A4` class, 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.