CSE 160
HW 8
Due Tuesday, April 14, 2008

Reading: Read Ch8 in the Objects First text.  Work along with it, using BlueJ.
                 
A) A finite sequence, revisited.

1) We will modify the Term class of Lab 5 to operate in arbitrary bases, not just base 10. An additional field of a Term will be the base. We will keep the existing Term() constructor, which assumes the default base of 10, and plan a second constructor Term(int base) which allows you to specify any (positive) base (up to 36). Keep clear about the difference between the value of a term, which is an integer, and its representation in a particular base, which will be a string. The sequence definition depends on the base, not just the integer value. The entire sequence will always be in a single base---whatever base its first term was constructed in.  But now we can have a different sequence for easch base. For bases larger than 10, our "digits" will include A, B, C, ..., in the usual way.  If you are unfamiliar with the usual way, look up "hexadecimal" in your discrete math text. We will want a getString() method, which returns the value of a term as represented in its base. You should be able to design your program so it works easily in any base from 2 to 36. (After 36, you would need letters beyond "Z", so we won't worry about them.)

2) Before generalizing your code to arbitrary bases, first design some unit tests that can be automated, so you can check that you don't lose base 10 functionality. One way to do this is to write a nth(int n) method which returns the nth successor of a term. (The 0th successor is the term itself. The 1st successor is what we called nextTerm().  To easily code the nth, think recursively.) Then for your tests, you can create a Term() and find its 10th, 100th, and 1000th successor, and use getValue() on each. Implement these tests with a test class. You can also make a test for the value of the LastTerm() class, but as it is rather slow, only run it after passing all your other tests.

3) After you have a good set of tests automated, implement the arbitrary base feature (including its JavaDocs, of course). You can check it behaves as before for base 10, and also works properly in other bases.  For example, the entire sequence in base 3, is: 1, 10, 12.  I get that the 199th term in base 16 is "DF". (I count the initial term as index zero, of course.)

4) When you submit your .jar file, include in your email the answer to these questions: What is the last term in each base 2 through 9?  What is the 500th term in base 16?


B) Creating arithmetic from a successor relation.

Recall our recursive definition of exponentiation, which is written in terms of multiplication and a decrement function (and a test for equality to zero). Write an analogous recursive definition of multiplication in terms of addition and a decrement function.  Write a recursive definition of addition in terms of an increment function and a decrement funciton. Putting these together, we can build arithmetic from just an increment function and a decrement function. Furthermore, we can build the decrement function from the increment function by searching for the x that when incremented gives us the thing we want to decrement. So all we really need is a set of "numbers" (including a zero) and knowledge of what we get when we increment each of them. We will explore this idea by using an enumerated type to give us the numbers, and explicitly writing an increment function. To keep things simple, we will have a finite set of numbers and do arithmetic modulo N.  For example with N=5, we can write:

public enum Num
{
   ZERO, ONE, TWO, THREE, FOUR, ERROR;

    public Num successor() {
       if (this==ZERO) return ONE;
       if (this==ONE) return TWO;
       if (this==TWO) return THREE;
       if (this==THREE) return FOUR;
       if (this==FOUR) return ZERO;
       return ERROR;
    }
}
 
(The ERROR element is there in case one wanted to return something for errors like division by zero.)

Expand this plan to cover numbers modulo N=10. Write a predecessor function which works by searching. Write a recursive addition, multiplication, and exponentiation method for these enums. Test your methods.  Write a Test class with the following code to print out a seven-times table (mod 10):

    Num x = Num.SEVEN;
    for (Num n : Num.values())
       if (n != Num.ERROR) System.out.println(n + " * " + x + " = " + n.times(x));

Your code should be general, so that if you later modified the enum to include more elements, all the other methods would not require any change.  Note that the order in which you list the elements in the first line of Num should have no effect on the calculations; it should only effect the sequence in which the values() method places them in the array.

Send your .jar file to the TA.