Assignment V

Due date Nov. 10, 2003

In this assignment you will expand on the Number class developed on the previous assignment, and do some performance measurements.

a) First, add to the number class an exponentiation operation. N.pow (x) raises the Number N to some integer power. x is just an int, not an arbitrary precision number (result would be too large otherwise).

Write two versions of pow: one as a simple loop, and one using the "Russian Peasant" binary approach that we described on class (call it fastPow).

b) To compare the performance of the two methods, measure the elapsed time for 1000 calls to each of the two, with the same input. The call:

System.currentTimeMillis ()

yields the current time represented as a count of milliseconds since some fixed date. To measure the elapsed time for a computation, you can write:

long start = System.currentTimeMillis ();
compute...
long finish = System.currentTimeMillis ();

And then use (finish - start) for a tabulation or a performance computation.

c) The Java library includes an abstract class Number, which is the root class for a series of numeric classes. It also includes a class bigInteger, that uses an array representation for arbitrary precision integers, and has the same functionality (and more!) as our Number class. Do a timing comparison of the Java pow method on bigInteger, and compare it with your version.

To find out the details of the bigInteger class, refer to the java documentation at http://java.sun.com/j2se/1.4.2/docs/api/.