Some nasty input ("short" decimal -> IEEE double) cases

[Tim Peters]

David noted, in his interesting discussion of the table-maker's dilemma,
that because the set of representable fp numbers is finite, there is
always a worst case, such that if enough extra precision is used to
resolve that case, that much extra precision suffices to handle all
cases.

This gets a bit twisted in Jon's original example of decimal->binary
input since, although the set of representable fp numbers is finite, the
set of possible decimal input strings is not (and is dense in the reals
-- the user can enter a number arbitrarily close to any end case the
current rounding discipline has problems with).

But if we take the IEEE- (and I guess still NCEG-, although not dgh-)
blessed option of ignoring input digits beyond the 17th (when reading
into an IEEE double), the problem is magically <grin> rendered finite
again, and Jon's original question of how much extra precision is needed
is a very interesting one.

I don't know the answer and don't have time to think about it either,
but thought folks might find the following summary of some old "brute
force" work interesting.  Under the round-to-nearest/even discipline,
and ignoring denorms, the difficult cases are those that lead to a
binary number close to

2#1.s1 * 2^exp

where s is any string of 52 bits and exp is an integer in [-1022,1023].
Rather than look for "short" (<= 17 decimal digits) decimal strings that
caused to this to happen, I wrote a program that, in outline

0. Do the following forever:
1. Pick a random 52-bit s.
2. For every exp in [-1022,1023]:

      Construct the number x = 2#1.s1 * 2^exp

      Convert x to a decimal fp notation, to 22 significant digits.  If
      the conversion is not exact, but the last 5 digits of the decimal
      representation are within 25 (on either side) of "00000", remember
      x; else move on to the next x (because this x can't be triggered
      by any input "pretty close" to no more than 17 significant decimal
      digits, or is exactly an end-case and so presumably recognizable
      as such).

Of course the computations in step 2 need to be done, carefully, in an
extended precision, and luckily I had an arbitrary-precision fp
conversion tool sitting around that could handle this.

After letting run it for a day, it cranked out about 1200 "interesting"
cases, of which I'll attach 100 of the worst below.  These can be used
for various things:  (1) As a source of examples some of which your (or
your favorite vendor's) less-than-perfect input routine are almost
certain to fail on (in the sense of not delivering the best possible
answer); (2) As hard proof that at least 24 extra bits are needed to do
correct no-more-than-17-decimal-digit -> IEEE-double input; (3) As a
spur to finding even worse cases; (4) As a source of random clues
<grin>.  It's hard to believe that *the* worst case can be *much* worse
than these, but then a day of run-time wasn't long enough to cover a
significant number of the 2**52 possibilities for s.

an-expert-in-algebraic-number-theory-could-have-fun-with-this-in-an-
   analytical-framework-ly y'rs  - tim

Each line is one case, and contains:

1) A decimal input in conventional fp notation.
2) The hex representation of the best possible IEEE 8-byte
   approximation.
3) The input in an odd hex fp notation, properly rounded to 81
   significant bits.  E.g., the last part of the first line is

   1.19e9b378432b3 800019e *2^-551

   This says the input is 16#1.19e9b378432b3800019e times 2 to the
   10#-551 power, and the blank "in the middle" separates the 53 bits
   that are retained in the IEEE 8-byte format from the excess that
   controls the rounding; in this case the excess is (rounded, & hex)
   800019, which means the excess is strictly larger than a half ulp
   (although if you suffered a "too low" rounding error in one of the
   first 19 excess bit positions, you might be fooled into thinking the
   excess was actually a little less than a half ulp ...).

1.4939888796310381e-166	1d819e9b378432b4  1.19e9b378432b3 800019e *2^-551
9.4152307727516469e-81	2f51dcab428658bb  1.1dcab428658ba 8000036 *2^-266
1.8202535637741795e157	6095366db3607a1c  1.5366db3607a1b 8000184 *2^522
1.4562028510193436e158	60c5366db3607a1c  1.5366db3607a1b 8000184 *2^525
8.7838666617320957e-148	2166769af6aa2c24  1.6769af6aa2c23 800002d *2^-489
1.5057902774989001e-177	1b38684cd9e76d2b  1.8684cd9e76d2a 800019d *2^-588
3.5496649754116973e164	6218a80a02d0e950  1.8a80a02d0e94f 800005b *2^546
7.0993299508233946e164	6228a80a02d0e950  1.8a80a02d0e94f 800005b *2^547
4.5866399254463548e-98	2bb914906cd79d18  1.914906cd79d17 800007e *2^-324
2.2933199627231774e-98	2ba914906cd79d18  1.914906cd79d17 800007e *2^-325
1.1466599813615887e-98	2b9914906cd79d18  1.914906cd79d17 800007e *2^-326
5.7332999068079435e-99	2b8914906cd79d18  1.914906cd79d17 800007e *2^-327
2.0335285262210365e30	4639aaaf5f390133  1.9aaaf5f390133 7fffe46 *2^100
1.6268228209768292e31	4669aaaf5f390133  1.9aaaf5f390133 7fffe46 *2^103
4.3926460437583367e-287	047ac13c0207b704  1.ac13c0207b704 7ffff3b *2^-952
9.9455049926023556e-247	0cdbd0b58424ad67  1.bd0b58424ad67 7ffffe3 *2^-818
4.9727524963011778e-247	0ccbd0b58424ad67  1.bd0b58424ad67 7ffffe3 *2^-819
2.4863762481505889e-247	0cbbd0b58424ad67  1.bd0b58424ad67 7ffffe3 *2^-820
4.3960346009020968e-209	14ace798bbe71e48  1.ce798bbe71e48 7ffff4e *2^-693
2.1980173004510484e-209	149ce798bbe71e48  1.ce798bbe71e48 7ffff4e *2^-694
1.0990086502255242e-209	148ce798bbe71e48  1.ce798bbe71e48 7ffff4e *2^-695
5.4950432511276210e-210	147ce798bbe71e48  1.ce798bbe71e48 7ffff4e *2^-696
2.7475216255638105e-210	146ce798bbe71e48  1.ce798bbe71e48 7ffff4e *2^-697
1.3242099347212899e191	679db88237020ea5  1.db88237020ea4 800033e *2^634
4.0289383544945442e-127	25b1745db9627822  1.1745db9627822 7fffe95 *2^-420
2.0144691772472721e-127	25a1745db9627822  1.1745db9627822 7fffe95 *2^-421
2.9879777592620762e-166	1d919e9b378432b4  1.19e9b378432b3 800019e *2^-550
3.0186177120688203e238	71728aea5c310df4  1.28aea5c310df3 80001de *2^792
8.5578636523079267e-105	2a53a0a0760c08b4  1.3a0a0760c08b4 7ffff64 *2^-346
1.8315006815418874e-213	13c3baf5df5d1bd3  1.3baf5df5d1bd3 7fffbc4 *2^-707
1.1180696226618902e-133	2454510014386d78  1.4510014386d77 8000421 *2^-442
5.1218353967186271e-87	2e0460ae75bc1835  1.460ae75bc1834 8000146 *2^-287
2.2488733940820161e41	4884a71370dd2641  1.4a71370dd2640 80003f2 *2^137
5.6743205674525343e-78	2fe5067bc1a1070f  1.5067bc1a1070e 80000a8 *2^-257
3.6405071275483590e157	60a5366db3607a1c  1.5366db3607a1b 8000184 *2^523
2.9124057020386872e158	60d5366db3607a1c  1.5366db3607a1b 8000184 *2^526
5.8248114040773744e158	60e5366db3607a1c  1.5366db3607a1b 8000184 *2^527
1.9444097731801549e-216	1325730a53c826b8  1.5730a53c826b8 7fffd53 *2^-717
6.3453762374158837e-19	3c276909d56e6d67  1.76909d56e6d67 7fffecf *2^-61
7.6922085097811529e-85	2e77e8d28c1494df  1.7e8d28c1494df 7ffff27 *2^-280
1.0324493277457791e39	480845d40fa3e2da  1.845d40fa3e2d9 8000516 *2^129
2.0648986554915582e39	481845d40fa3e2da  1.845d40fa3e2d9 8000516 *2^130
3.3501413719415813e158	60d8669fbc00170c  1.8669fbc00170b 80001cd *2^526
5.2125065012687501e97	5438673c99a6b566  1.8673c99a6b565 800017f *2^324
6.0231611099956004e-177	1b58684cd9e76d2b  1.8684cd9e76d2a 800019d *2^-586
3.0115805549978002e-177	1b48684cd9e76d2b  1.8684cd9e76d2a 800019d *2^-587
9.1732798508927096e-98	2bc914906cd79d18  1.914906cd79d17 800007e *2^-323
4.0906288604802991e179	65393c98acf195a8  1.93c98acf195a7 800016e *2^596
4.0670570524420730e30	4649aaaf5f390133  1.9aaaf5f390133 7fffe46 *2^101
3.2536456419536584e31	4679aaaf5f390133  1.9aaaf5f390133 7fffe46 *2^104
6.5072912839073168e31	4689aaaf5f390133  1.9aaaf5f390133 7fffe46 *2^105
1.2290942431995137e200	6979b100a87d380a  1.9b100a87d3809 80003c2 *2^664
2.4581884863990274e200	6989b100a87d380a  1.9b100a87d3809 80003c2 *2^665
9.6402130615633027e48	4a1a62686ac9e8af  1.a62686ac9e8ae 80000cb *2^162
3.0531674690562831e252	745aa6fb523cd65f  1.aa6fb523cd65e 80003b3 *2^838
8.7852920875166734e-287	048ac13c0207b704  1.ac13c0207b704 7ffff3b *2^-951
1.2933758233903452e-123	266b5c1bf96c7a33  1.b5c1bf96c7a32 800072c *2^-409
1.6167197792379315e-124	263b5c1bf96c7a33  1.b5c1bf96c7a32 800072c *2^-412
2.7677887895252831e-86	2e2b879b4efbdd5a  1.b879b4efbdd5a 7fffd0a *2^-285
1.5607645472565903e-251	0bdc9b6a93a22548  1.c9b6a93a22548 7fff7f0 *2^-834
8.7920692018041936e-209	14bce798bbe71e48  1.ce798bbe71e48 7ffff4e *2^-692
1.9533391547899406e-78	2fccf3819b220f41  1.cf3819b220f40 8000672 *2^-259
1.6861909259633096e-214	138d105aaf4e338e  1.d105aaf4e338d 800052f *2^-711
2.1077386574541370e-215	135d105aaf4e338e  1.d105aaf4e338d 800052f *2^-714
1.0538693287270685e-215	134d105aaf4e338e  1.d105aaf4e338d 800052f *2^-715
2.6484198694425798e191	67adb88237020ea5  1.db88237020ea4 800033e *2^635
7.0700459675578346e-211	144dc063c086fd40  1.dc063c086fd3f 80001ca *2^-699
3.5350229837789173e-211	143dc063c086fd40  1.dc063c086fd3f 80001ca *2^-700
3.8746602621607623e180	656de161000fa244  1.de161000fa244 7fffec3 *2^599
7.7493205243215246e180	657de161000fa244  1.de161000fa244 7fffec3 *2^600
3.2661218564178881e-282	057e5ad87171d2e6  1.e5ad87171d2e6 7fffd45 *2^-936
5.5906570661430723e191	67bf5e8e121ac28e  1.f5e8e121ac28e 7fffed8 *2^636
2.1265063170656098e-19	3c0f61b6b6bcddfa  1.f61b6b6bcddf9 8000478 *2^-63
1.0632531585328049e-19	3bff61b6b6bcddfa  1.f61b6b6bcddf9 8000478 *2^-64
7.4975727418122478e-298	023f61b6b6bcddfa  1.f61b6b6bcddf9 8000140 *2^-988
3.7487863709061239e-298	022f61b6b6bcddfa  1.f61b6b6bcddf9 8000140 *2^-989
3.9628858404746327e-59	33cfd72ef2893821  1.fd72ef2893820 80001db *2^-195
1.3557686312315382e185	665fe83c0120e9cf  1.fe83c0120e9cf 7fff87f *2^614
6.5709648563234561e-232	0ff0528d311fdb96  1.0528d311fdb96 7fffe90 *2^-768
8.0578767089890884e-127	25c1745db9627822  1.1745db9627822 7fffe95 *2^-419
5.9759555185241524e-166	1da19e9b378432b4  1.19e9b378432b3 800019e *2^-549
7.4699443981551905e-167	1d719e9b378432b4  1.19e9b378432b3 800019e *2^-552
1.7160852761408831e-92	2ce1e5eb7d1f4e47  1.1e5eb7d1f4e46 8000514 *2^-305
1.4282213872448298e-88	2db22ef0fcc20bdb  1.22ef0fcc20bdb 7fff801 *2^-292
6.0372354241376406e238	71828aea5c310df4  1.28aea5c310df3 80001de *2^793
1.4297093860589080e114	57a293f9079d52ae  1.293f9079d52ad 800088a *2^379
1.1437675088471264e115	57d293f9079d52ae  1.293f9079d52ad 800088a *2^382
9.7582484048396769e-146	21d37f0658dca555  1.37f0658dca555 7fffe87 *2^-482
2.2361392453237804e-133	2464510014386d78  1.4510014386d77 8000421 *2^-441
2.7951740566547255e-134	2434510014386d78  1.4510014386d77 8000421 *2^-444
7.6037203079586341e-185	19b4ad8197c7db71  1.4ad8197c7db71 7fffe67 *2^-612
9.5602199811058283e-245	0d44e38b1b7e08a0  1.4e38b1b7e08a0 7fffe9a *2^-811
9.1012678188708975e156	6085366db3607a1c  1.5366db3607a1b 8000184 *2^521
7.2810142550967180e157	60b5366db3607a1c  1.5366db3607a1b 8000184 *2^524
3.8888195463603098e-216	1335730a53c826b8  1.5730a53c826b8 7fffd53 *2^-716
5.1007714063797051e109	56b5b80881b4e1ef  1.5b80881b4e1ef 7fffcf2 *2^364
1.6522655790924354e257	7556021621780b67  1.6021621780b66 8000890 *2^854
1.9963998014742381e126	5a2798085893670b  1.798085893670a 80006b9 *2^419
1.2621744586016618e153	5fb81961577a6647  1.81961577a6647 7fff3cf *2^508
6.7002827438831626e158	60e8669fbc00170c  1.8669fbc00170b 80001cd *2^527