CSc 221 Spring 2007 Homework 3

Due before the beginning of class Tuesday, March 6. Yes, only a week after HW2, but we will have done all the lectures about the root finding before HW2 is due. There will be new teams for HW3.

We are going to have a contest, to see which team can find the most decimal places in an approximation to the square root of 2. The method is extremely fast, so it should be simple to surpass the five million that is the most I know. The limit is the size of memory, I think. The winning team will receive . . . well, I haven't decided yet, but it will be something of great worth, although perhaps not financially. Perhaps a personally autographed certificate?

Let's bag the contest. There are complexities I hadn't anticipated.

ADDED 3.4.2007:  Don't try to do everything in one class! It can probably be done, but with some difficulty, and it's not good practice. Somewhere you have to have a main method, and that should not be in the class that implements rational numbers with BigInteger. Make another class--name doesn't matter--and put a main method in it. Write a no-arg constructor, and invoke it in your main method. That is, if your class is, say, HW3, your constructor will of course be HW3, and in your main method you can say:
    HW3 MyProg = new HW3();

Or if the details aren't right, just put your Newton-Raphson iteration formula and the call to the toString() method in the main method. I really don't want 500-line main methods, but this would be a dozen. Walk before you run.

ADDED 2.27.2007: Well, it may not be that easy. I've gotten up to about 43,000 digits, and now I'm stuck: the method for converting a RationalBigInteger to decimal dies. I'm investigating, but so far don't have a clue. However, we will NOT change the due date; we'll change the goal. Maybe getting more than 5 million digits is out  of reach. But I have a feeling you will whip the problem, whatever it is.

2 is an irrational number, of course (you should be able to prove that), so we compute an approximation. We'll use the Babylonian Method, which is the fastest way, and is also the oldest example of an algorithm. I have no idea how the Babylonians discovered it, but it's really simple: compute a succession of approximations, each approximation being the average of the previous approximation and 2 divided by the previous approximation. (Satisfy yourself that the result really is a close approximation; takes a tiny bit of algebra.)

I go back a ways on this. In 1952 I wired up a plugboard for the IBM Card Programmed Calculator that I was working on at General Electric, using the Newton-Raphson method for computing square roots. I will show you in class that the Babylonian Method is exactly the Newton-Raphson for the square root of 2, except that the Babylonians needs only three arithmetic operations at each iteration, whereas Newton-Raphson uses four. I didn't know that!

For a cool summary of everything you could want to know about this general subject, and much much more, see http://en.wikipedia.org/wiki/Methods_of_computing_square_roots. This will not be on the exam.

We will work with rational numbers, in which every number is represented as the quotient of two integers. We will use  the BigInteger class from imported from java.math. I will give you a huge hint; you do the rest. Here is a method that adds two rational numbers:

// add two RationalBigInteger numbers
public RationalBigInteger add( RationalBigInteger right )
{
    BigInteger ad = numerator.multiply(right.denominator);
    BigInteger bc = denominator.multiply(right.numerator);
    BigInteger resultNumerator = ad.add(bc);
    BigInteger resultDenominator =
        denominator.multiply(right.denominator);
    return new RationalBigInteger( resultNumerator,
        resultDenominator );
}

You also may need methods that do arithmetic in which one operand is a rational number and the other is just a BigInteger:

// Add a BigInteger to a RationalBigInteger
    public RationalBigInteger add( BigInteger right )
    {
    BigInteger resultNumerator =
        numerator.add(denominator.multiply(right));
    return new RationalBigInteger( resultNumerator, denominator);
}

Since I'm feeling generous I'll give you a constructor, too:

 // two-argument constructor, for two strings
    public RationalBigInteger( String theNumerator, String theDenominator )
    {
        numerator = new BigInteger(theNumerator);
        denominator = new BigInteger(theDenominator);
        reduce();
}

Your program needs to check its answer: square the result, and be sure you are close to 2. You need a method to print a rational number, which requires conversion to a base-10 decimal number; use repeated subtraction, which I will sketch in lecture.

When we have a winner I'll put that fact on my Web site, and then we'll game Google into putting our result high in the list if anybody queries "square root of 2." (But don't tell Google, or be too obvious about it; they don't like people messing with their heads.)

Small checklist.

• Be sure all arithmetic results are reduced to lowest terms. Just find the gcd (look it up if you don't know) and divide numerator and denominator by it. Can save a tiny bit of time by checking to see if the gcd is 1, in which case the fraction is already in lowest terms, meaning that the numerator and denominator have no factor in common except 1. Can also be stated: the numerator and denominator are relatively prime.
• Your testing to be sure that the square of your answer is indeed 2 can be quite informal. HW4 will involve automating this testing, using an important technique called unit testing. Eclipse facilitates unit testing by providing the JUnit package.
• We don't honestly care much about the square root of 2. The purpose of the HW is to give you practice with the ideas of OOP, through the Rational Big Integer class. A quiz or exam might ask you about the method of computation; if so, I will explicitly tell you that.

Back to the top of the Spring 2007 CSc 221 page

Back to Dan McCracken's Home Page