How not to write a loop, revisited

[Scott Daniels]

In article <329 at accelerator.eng.ohio-state.edu> 
	rob at kaa.eng.ohio-state.edu (Rob Carriere) writes:
>... nobody I know *guarantees* that integers are representable (i.e. 
>the closest approximation to 2 might be 1.999999)
    In fact, I have read interesting arguments that propose that many
integers be purposely mis-represented.  The argument goes as follows:

Assume (for concreteness) a binary floating point representation with 
an 4-bit mantissa ranging [0..1),and a 3-bit signed exponent field, and a 
1-bit sign.  We will not use IEEE hidden most-significant bit.  Examples:
 Notation: Exponent/ binary fraction  (only scribble positive numbers here)
	-2/.1000 = 0.125   -1/.1000 = 0.25    0/.1000 = 0.5  
	 0/.1100 = 0.75     1/.1000 = 1.0     1/.1001 = 1.125
	 1/.1010 = 1.25     1/.1100 = 1.5     2/.1000 = 2.0  
	...

Now notice that in this representation, a number E/F actually represents
the range:   E / (F - 1/32)  through E / (F + 1/32).  The size of the interval
depends only on the exponent.
	1/.1110 = 1.750    represents  1.6875 through 1.8125
	1/.1111 = 1.875    represents  1.8125 through 1.9375
	2/.1000 = 2.000    represents  1.8750 through 2.1250 
	2/.1001 = 2.250    represents  2.1250 through 2.3750 

Ok, here we go:
  To represent 2.0 exactly, we could use 2/.1000, but that represents the
interval 1.8750:2.1250.  Now, there is a tighter specification which is 
entirely within that interval: 1/.1111 (which represents 1.8125:1.9375), so
we should use that tighter interval since no poin inside it is any further
from the desired value 2.0 than the range that 2/.1000 gives.  Hence the
besty representation (the tightest) for 2.0 is an interval which does not
even include 2.0!

-Scott Daniels daniels at teklds.TEK.COM (or daniels at teklds.UUCP)