3 corrections to Steele's SIGPLAN 90 paper

[Marianne Mueller]

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


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. 

		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?

	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.

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