3 corrections to Steele's SIGPLAN 90 paper

[Guy Steele]

   Date: Tue, 26 Jun 90 17:17:15 PDT
   From: mrmaEng.Sun.COM (Marianne Mueller)

Thank you for a quite accurate summary.  It is heartening to
know that someone actually listened and cared!  A few minor
emendations appear below.

   At the SIGPLAN 90 conference last week, Guy Steele pointed out that an
   intrepid pre-conference implementation of what's stated in the paper
   revealed 3 mistakes.  

   1.  Table 9 (page 125)

	   for 		-1: USER!("");
	   substitute      -1:USER!("0"); and delete the comment


   2.  Table 10 (page 125)

	   for		fill(-k, "0")
	   substitute	fill(-k-1, "0")

   3.  Table 5 (page 124)
	   insert		k <-- 0  after assertion

And also delete k <-- 0 from Table 6.

   The paper is "How to Print Floating-Point Numbers Accurately", Guy L.
   Steele (glsathink.com) and Jon L. White (jonlalucid.com), pp 112-126,
   Proceedings of SIGPLAN 90, SIGPLAN Notices Volume 26, Number 6, June
   1990.

   The presentation was interesting since he didn't try to go through all
   the algorithms blow by blow but instead focused on the motivation and
   what it is he's trying to accomplish.  So audience participation was
   high!

   Here's a transcription of some notes I took.  If I got part of this
   wrong maybe glsathink can correct me.

   The base conversion problems are:
	   1. Avoid scaling

		   See Matula[68] for a discussion of why we want to
		   avoid scaling; the idea is that	if L and L' are 
		   consecutive floating point numbers, then 
		   L * (10**k) = L' * (10**k) so if you scale you might
		   lose information. 

Well, the equality *might* hold so you *might* lose information,
depending on the exact values of L and k.

		   Also, note that an n-bit binary fraction may 
		   require up to n decimal digits to represent it
		   accurately.   You need

			   2 + floor(   n   )
				     --------       digits.  See Matula[68].
				     log 10
					2


	   2. When should we stop printing the integer part?

I actually said "fraction part", but in fact the difficulty
applies to the integer part as well.

	   3. How do you round?

		   Sidetrack: Why do we round?
			   1.  aesthetic - it looks nicer
			   2.  rounding preserves information in a way
			       that truncation cannot
			   3.  portability - if we round correctly then
			       numeric input and output (let alone
			       programs!) is more easily ported from
			       fp format to fp format

   The goals of the printing algorithm he presents are:

	   1.  Preserve information
	   2.  Use the minimum number of digits (e.g. last digit printed is
		   never 0)
	   3.  Round correctly in ALL cases
	   4.  Generate digits left to right (other algorithms generate
		   digits right to left which is somewhat inconvenient)

   The main ideas are:

	   1. Use integer arithmetic only
	   2. Use BIGNUM rationals (to avoid scaling problems; also, use
		   rational representations)
	   3. Use explicit interval arithmetic to decide

		   * when to stop	
		   * how to round correctly


   The 4 goals of the printing algorithm, expressed in a mathematical way, are:

	   1.   -                         +
	       v  +  v   <   V   <   v + v
	      ----------            --------
		   2		    2

	       +			     -
	      v   is the successor and v   is the predecessor of a fp
	      number v.   V (Capital V) is the value printed (refer
	      to page 119 for a more rigorous description of all this.)

	      Note that this bound is NOT the same as saying that

		   | V - v | < b**(-p)
			       -------	
				  2

	       because of discontinuities in representable floating 
	       point numbers (due to jumps in exponents)

	   2.  Define the output V of the printing algorithm like so:

			 H
		   V =  Sum   D * (B**i)
		       i = N   i

		where H and N are integers and the D (H >= k >= N) 
		are digits.                         k

		The goal is: H is as small as possible, and N is 
		as large as possible. 

			       N
	   3.   | V - v | <=  B		(correct rounding)
			     ---
			      2


	   4.  Digits D are generated in order
		       K



   For the future, Guy Steele said it would be interesting to see if
   there is a fast 99% approach.  The printing algorithm needs to be
   correct 100% of the time - how about if it is also FAST 99% of the
   time?  One idea is to use approximate computations like the Clinger &
   Bellerophon algorithms also presented at SIGPLAN 90.

You managed to say this part better than I did!

   Matula[68] == Matula, David W., "In-and-Out Conversions",
   Communications of the ACM 11, 1 (January 1968), 47-50.