SUNY Geneseo Department of Computer Science

Problem Set 3 -- Logic

Purpose

Background

This exercise is based on material in chapter 5 of our text, particularly sections 5.2 and 5.3. This material was also covered in the January 26 lecture.

All of the problems in this exercise are inspired by real code I have had to write in my own work. They all revolve around the fact that computer representations of real numbers (e.g., Java types float and double) have limited precision and accuracy -- real numbers are represented using a fixed number of bits, and thus there is a limit to how exactly a compuuter can represent a real value, and how close two real numbers can get to each other and still be detectably different to the computer. The limited accuracy of real numbers leads to a problem called "round-off error," whereby the results of computer calculations on real numbers are generally not exactly the same as the mathematically correct results; the more complicated a calculation is, the more round-off error accumulates in its result. Imprecision and round-off mean that it is almost always a mistake to make exact comparisons between real numbers. For example, in code such as

    float x;
    ... calculate a value for x ...
    if ( x == 0.0 ) {
        ...
    }

The x == 0.0 test will probably not succeed when one expects x to equal 0 mathematically. Instead of exact comparisons, one should always compare real numbers to a small range of values. For example, the above code is better written

    float x;
    ... calculate a value for x ...
    if (  -TOLERANCE < x  &&  x < TOLERANCE  ) {
        ...
    }

where TOLERANCE is a constant reflecting how accurately you think x's value will be computed. As long as x is within TOLERANCE of being 0, this form of the test will succeed.

Exercise

Solve the following problems:

Problem 1

A point in two-dimensional space can be represented by its real-valued x and y coordinates. Using the idea of comparisons with tolerances from the "Background" section, one could test whether such a point is (0,0) by writing

    -TOLERANCE < x  &&  x < TOLERANCE  &&  -TOLERANCE < y  &&  y < TOLERANCE

Part A

Show the expression you would write to test whether a point is not (0,0).

Part B

A variation on the above test determines whether a point lies on either of the axes:

    ( -TOLERANCE < x  &&  x < TOLERANCE )  ||  ( -TOLERANCE < y && y < TOLERANCE )

Show the expression you would write to determine whether a point was on neither axis.

Problem 2

Writing expressions such as -TOLERANCE < x && x < TOLERANCE all over a program is a pain, and an invitation to trouble if you ever have to change the test for some reason (imagine having to find a few hundred of these tests to replace TOLERANCE with a different name). It is better to write a single comparison function, and call it where comparisons are needed. But there are six possible comparisons (equal, not equal, less, greater, less than or equal, greater than or equal), all of which could plausibly need to incorporate a tolerance -- it's still painful to have to write 6 similar functions. The best of all designs would write just one main comparison function, and define all the other comparisons in terms of it. For example, suppose you have a function less(x,y) that returns true if x is less than y (to within some tolerance) and false otherwise. Then you can test whether x is greater than y by writing

    less(y,x)

and whether x is not equal to y by writing

    less(x,y) || less(y,x)

Show how to use this hypothetical less function and Boolean operations to compute the other three comparisons (equal, less than or equal, and greater than or equal).

Problem 3

Suppose the hypothetical less function is implemented as

    public static boolean less( double x, double y ) {
        return x < y - TOLERANCE;
    }

With this implementation of less, the test for x being equal to y that you developed in Problem 2 could be logically equivalent to the expression

    y - TOLERANCE < x  &&  x < y + TOLERANCE

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office. Please bring written answers to each of the problems to the meeting.