Comp 212 Project 2
Accurate Floating-Point Sum

Due April 3, 2000 at 10:00 AM

The accuracy of floating-point arithmetic is limited by the fact that floating-point numbers are implemented using a finite number of digits. Internally, the implementation of floating-point numbers is similar to a number written in scientific notation, for example, -5.678 * 10⁹. In other words, the sign (-), the mantissa (5.678), and the exponent are stored as separate fields, and the number of digits in the mantissa and exponent is fixed.

If we add a very large number with a very small number, our result may (incorrectly) be just the larger number. The reason is that to add the numbers we must, normalize them, that is, they need to have the same exponent. Usually, we change the smaller number to have the same exponent as the larger number. So, for example, if we normalize -5.678 * 10⁹ and 5.432 * 10¹, 5.432 * 10¹ becomes 0.000 * 10⁹, because we've insufficient digits in the mantissa. Ooops.

To avoid this problem, one possible way to sum a list of positive floating-point numbers is as follows.

• Insert the floating-point numbers into an Ordered Container.
• Insert the ``gaps'' between ``adjacent'' floating-point numbers into a Priority Queue. Two floating-point numbers are adjacent if there does not exist a third number in the list that falls between the two. (Clearly, a gap might be the difference between two numbers. Is there a better notion of gap for our purpose?)
• While the Priority Queue has one or more elements, do the following.
  1. Extract the minimum gap from the Priority Queue.
  2. Find the corresponding elements in the Ordered Container.
  3. Remove them from the Ordered Container.
  4. Remove the other two gaps for these numbers from the Priority Queue. Hint: Mark each gap as deleted and leave it in the queue. (Think State Pattern.) Later, when you extract a gap, a ``deleted'' gap will do nothing.
  5. Add the floating-point numbers together.
  6. Insert their sum into the Ordered Container. Hint: Duplicate numbers (i.e., no gap between them) turn out to be troublesome. It is easy to avoid having duplicate keys in your Ordered Container: add the numbers immediately.
  7. Compute the two new gaps for this number.
  8. Insert them into the Priority Queue.

Your program should accept a list of (possibly negative) floating-point numbers as input through the standard input stream, with one floating-point number per line. It should recognize the end of the list when this stream reports end-of-file (EOF). It should then compute and print the sum to the standard output stream.

Your priority queue must be based upon a heap. You should apply the ``Object'' Adapter Pattern to construct a priority queue from a heap. Your ordered container must be based upon the circular list presented in class. Again, you should apply the ``Object'' Adapter Pattern. Furthermore, the ordered container's methods should be implemented as Visitors to the circular list.

Code samples are provided for your convenience!

Submission

The project is broken up into two milestones.  Each milestone is to be submitted electronically.  You can use slack days on this project.  You are given a total of five slack days for the whole semester. Specific submission instructions will be posted on the Comp212 web page.  The complete milestone set should contain the following:

• An ASCII README file to indicate what you have and/or have not done, and to point out specific details that you feel we need to know when grading your work. 
• UML diagrams of all your class designs.
• All the Java source code necessary to compile and execute your test code.

Milestone #1: due March 27, at 10:00 AM - the priority queue and ordered container classes as well as testing code for these classes.  40% of the project grade

Milestone #2: due April 3, at 10:00 AM - the complete program. 60% of the project grade