Decimal to binary conversion

[Vaughan Pratt]

>Date: Sun, 25 Feb 96 21:59:53 PST
>From: Vern Paxson <uunet!ee.lbl.gov!vern>
>Here's the table analogous to the one you posted:
>Digits	Input			Extra Bits Required
>1       $9 \cdot 10^{-265} $  		13    
>2       $85 \cdot 10^{-037} $ 		16    
>...
>20      $25188282901709339043 \cdot 10^{-252} $ 73    
>...

Taking Fred Tydeman's largest number of extra bits for each number
of decimal digits in the exponent gives the following correspondence.

D=Digits, T=Tydeman, P=Paxson

D   T  P	 D   T  P	 D   T  P	 D   T  P
1: 13 13	 6: 30 30	11: 45 45	16: 63 63
2: 17 16	 7: 33 30	12: 49 49	17: 66 64
3: 20 20	 8: 37 37	13: 53 53	18: 72 69
4: 24 24	 9: 42 42	14: 57 57	19: 73 73
5: 27 26	10: 45 42	15: 58 57	20: 74 73

Looks like Fred didn't leave too many stones unturned.

Also, it looks like a good predictor for the number of bits required in
these extreme cases is total number of bits allowed in the number,
namely

	digits_input/.30103 + 11 (exponent bits)

Not too surprising.

Both Fred and Vern hold the exponent bits at 11, which does not reflect
real distributions for bounded number of mantissa bits.  Typical one-
and two-decimal-digit constants don't often have a multiplier of
10^-265.  What would be even more interesting would be this table with
the exponent bits restricted to some fraction of the mantissa bits, or
even a two-dimensional table with separate bounds on the lengths of
exponent and mantissa.  I'm not volunteering but maybe someone else
whose fancy is tickled by this problem might enjoy tabulating it.  A
plausible conjecture is that it will simply bear out the obvious
generalization of the above formula to the case of variable number of
exponent bits.

Vaughan Pratt


<PRE>