Class Project

Step 5: Binary precision functions

Deadline: Hand in either Step 5 or Step 6 on Wednesay 3 December 2003, 11:59 PM, and the other at the end of the quarter (TBA when I work out grading deadlines).

In this step, create the binprecfunc implementation of xreal: modify the precfunc implementation by replacing the ratpair implementation of ratintvl with the intpair implementation of binratintvl.

The essential point of this step is to reduce the inefficiency in precfunc due to the use of unnecessarily complex rational endpoints. We could approach this by carefully considering each ratintvl produced by a precfunc xreal, and sometimes expanding it to a slightly larger and substantially simpler interval. But it looks more promising just to limit the intervals a priori to a nice simple set of intervals.

Binary rational intervals as approximations to real numbers

A binary rational interval is a closed interval in the real line of the form

[(m-1)*2^n, (m+1)*2^n]

For every pair real number x and every positive real number p>0, there is a binary rational interval of width <=p containing x in its interior.

[(m-1/2)*2^n, (m+1/2)*2^n]

I edited the specification of the rational interval datatype (ratintvl-4.txt) rather superficially into a specification of the binary rational interval datatype (binratintvl-1.txt) Some of the operations translate directly from rational intervals to binary rational intervals. But in some cases, an exact operation on two binary rational intervals yields a rational interval that is not a binary rational interval. Since we are using these intervals to represent approximations to real numbers, the right thing to produce is the smallest binary rational interval containing the correct rational interval. For example, the sum of two binary rational intervals is not always a binary rational interval:

[(0-1)*2^0, (0+1)*2^0] + [(0-1)*2^1, (0+1)*2^1] = [-3, 3]

I proposed some variations in output functions that might be handy when working with binratintvls. I have not experimented with the specifications, and I wrote them up under time pressure in a rather sick mental haze, so watch out for errors, and don't hesitate to propose improvements.

Implement binratintvls as lists of two integers, where (list m n) represents [(m-1)*2^n, (m+1)*2^n]. Or, at your discretion, you may choose to negate the exponent nbinratintvl functions that you use in your binprecfunc implementation of xreal. I'm not sure how many that is, but I think that it is worth studying the binratintvl datatype to understand how the concepts work.

If you are confused about binratintvl, I suggest that you implement the functions converting between binratintvl and ratintvl, and find out what happens when you implement operations through the translation. For example,

(define (add_binratintvl br1 br2)
   (ratintvl->binratintvl
      (add_ratintvl
         (binratintvl->ratintvl br1)
         (binratintvl->ratintvl br2)
         )
      )
   )

Binary precision functions

The articles by Hans Boehm that I handed out have a nice treatment of the representation of exact real numbers by binary precision functions. In Boehm's terms, a binary precision function is a function from integers to integers. Such a function b represents a real number x if

x in [(b(n)-1)*2^n, (b(n)+1)*2^n]

Reimplement the xreal functions that you implemented before, using some reasonable variation on Boehm's binary precision functions. Call this implementation binprecfunc. At your discretion, you may use functions that return a whole representation of a binary rational interval, or just the integer mantissa as specified by Boehm. You may represent the exponent directly, or use its negation so that a bigger number means greater precision.

Determine as well as you can by time tests how well the binprecfunc implementation improves the performance of precfunc. Look for examples on which precfunc appears to be very inefficient because of the use of unnecessarily complex rational endpoints, and discover whether binprecfunc does much better. If possible, show that the rough rate of increase in time is less for binprecfunc. If there is only a multiplicative improvement in time, it needs to be quite large to be convincing. A factor of 5 or more might be explained by the mere fact that a ratintvl in the ratpair implementation has 4 integers, while a binratintvl in the intpair implementation has only 2, and a binprecfunc function only needs to return 1. A factor of 100 or more is probably significant, but a thorough understanding of its significance requires some analysis, and probably some instrumenting of functions to count conceptual steps as well as pure timings. I bet you can find substantial differences in the rough timing rates.

What to hand in

• An appropriately named file containing your definitions of xreal functions in your binprecfunc implementation.
  
  
• If your xreal functions, or your demonstrations, depend on any binratintvl functions, an appropriately named file containing your definitions of those functions. (Writing/submitting those functions that aren't used is optional.)
  
  
• One or more files demonstrating the apparently correct operation of your xreal functions---not thorough tests but just a quick sanity check of the conversion from precfunc to binprecfunc.
  
  
• One or more files of timing inputs, using my timetest from progutils-3.scm or test code of your own if you like it better.
  
  
• A file called README.txt or START.txt containing very short and simple instructions how to execute your tests. If this takes more than 2 lines, you probably need to write a Scheme file to automate things more for the grader.
  
  
• A text file called comments.txt, or a variant in another format, containing a discussion of your observations.

Copyright Michael J. O'Donnell <michael_odonnell@acm.org>. Licensed for free use.
This page is generated from PHP source code, with supporting files.