Tim's list of critical cases for base conversion

[Tim Peters]

>  [dgh, detailing some experiences with the putative "nasty"
>   input cases, that don't seem so nasty after all ...]
>  ...
>  So I suspect it's mainly good for finding implementations that didn't
>  try very hard to meet IEEE 754 ...

While it wasn't intended as a QA list (it was produced as a side effect
of an attempt to guess what the worst <=17-digit decimal -> IEEE double
input case might look like), in that context I would expect it to
produce failures on fully IEEE-conforming input routines that took the
option (indirectly encouraged by the 754 std) of doing input conversions
using the minimal double-extended precision.

I.e., IEEE-754 does *not* require proper rounding for the majority of
those cases (the magnitudes of most of the exponents exceed the "Max N"
(from section 5.6's Table 3) for which correct rounding is required);
the minimal double-extended format (from which the various magic numbers
in Table 2 and Table 3 were presumably derived) offers just 64-53 = 11
extra bits of precision; none of the test cases can be reliably resolved
with (just) 11 extra bits of precision; hence an IEEE-conforming input
routine that uses the minimal double-extended precision is doing a crap
shoot on most of those input cases.  In short, it's not "a bug" if an
input routine gets most of those wrong, since 754 didn't require that
most of them be done right to begin with ...

All that aside, I still think finding "the worst" <=17-significant
digit decimal -> IEEE double case is an interesting problem.  Think it's
solvable, too, but can't make much time for it.  One analytical approach
to it ends up needing to solve a couple thousand instances of this
problem:

   Given:
      A fixed integer c, c > 0.
      Fixed integers a, b and limit, all in [0,c).

   Find:
      An integer i in [0,limit] such that the value of

      (a + b*i) mod c

      is minimal over all i in [0,limit].

This "feels" efficiently solvable, but I couldn't hack up a good
approach in an hour of playing with it, and couldn't find a canned
solution either.  Anyone have a solution on tap?  If so, I'd sure like
to hear about it!

Note that the integers are generally huge (e.g., c = 2**751, b =
2*5**324, a = (2**53+1)*5**324, limit = 2**52-1 are typical), so any
form of brute search isn't good enough.  E.g., trying all the i in
[0,limit] is out of the question; solving "x = (a+b*i) mod c" for i,
first with x = 0, then x = 1, then x = 2, ... until hitting a solution i
in [0,limit], is also out of the question (in general -- it *may*
succeed very quickly, but you can't count on that, and the worst case is
unthinkable).

open-for-clues-ly y'rs  - tim

Tim Peters   Kendall Square Research Corp
timaksr.com,  ksr!timaharvard.harvard.edu