« Windows Programming | Main | Leonid Meteors »

Interval Arithmetic and Prolog

I taught myself Prolog back in 1984.  At the time I had a Sharp MZ-80B microcomputer which ran the CP/M operating system (like MS-DOS only slightly better).  I bought a Prolog interpreter and played around with it, using it to write a system for cataloging stock in the school science department where I worked as a lab technician.

Although I found the language intriguing, several things about it disappointed me.  One was the way it handled arithmetic.  Basically, when it came to arithmetic, Prolog just threw logic out of the window and did it in the same way that imperative languages did it.  I thought its designers had missed an opportunity here.  I had already come across interval arithmetic in volume 2 of Knuth's 'The Art of Computer Programming', the idea of which is that, instead of representing real values by single approximate numbers, you represent them by pairs of real numbers: a lower bound and an upper bound.  One of the problems with the single approximate number representation is that it almost always gives results that are approximations and hence are logically speaking incorrect.  The beauty of interval arithmetic is that it allows you to always make logically correct statements about real values.  This seemed to me to be a much more 'Prologish' way of doing arithmetic.

There is a minor complication in that, with some arithmetic operations, the interval returned is actually split into 2 or more intervals.  For example, if you divide 1 by the interval [-0.1,+0.1] you get a result which is the union of [-infinity,-10] and [+10, +infinity].  However, this can easily be handled by Prolog's back-tracking mechanism in which one of the intervals is returned first and the other is only returned if the first computation fails and back-tracks to this point again.

Nearly a decade later I came across the Motorola 68040 microprocessor and was surprised to find that it included hardware support for interval arithmetic in the form of special rounding modes (round towards plus infinity and round towards minus infinity).  Such modes are necessary to enable the lower and upper bounds to be determined efficiently.  These rounding modes were specified in the IEEE 754 standard for binary floating point arithmetic.  It pleased me that some experts thought interval arithmetic important enough to include provisions for it in a standard.  I later learnt that there is quite a lot of research in the use of interval arithmetic for certain kinds of computations.

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.
Author Email (optional):
Author URL (optional):
All HTML will be escaped. Hyperlinks will be created for URLs automatically.