[issue9009] Improve quality of Python/dtoa.c

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

Patch that does a fairly significant rewrite of strtod;  it's still (mostly) based on Gay's code, but there are some significant changes.

Some background:  strtod, after dealing with easy cases, works roughly as follows:

(1) Using floating-point arithmetic, create a double *rv* holding an approximation to the input value; this approximation may be out from the true value by several ulps (perhaps as much as 10 ulps;  certainly not more than 100 ulps).

(2) If the input string is very long, truncate it (accepting that this introduces a small error), and work with the truncated value below.

(3) Use integer arithmetic to compute (an approximation to) ulps difference between *rv* and true value.  Possibly return immediately if
the ulps difference can be proved to be <= 0.5 ulps, and we're not in any of various exceptional cases.

(4) Use the ulps difference to correct *rv* to a new value.

(5) If the ulps difference has fractional part close to 0.5, or if the correction takes us past a power of 2, or if it takes use near/to the max representable double, or to 0.0, go around the correction loop again.

(6) If we still can't decide (because the ulps difference is very close to 0.5), call bigcomp to settle the issue once and for all.


The new patch simplifies the above procedure considerably:

- scaling of rv is used for very large values as well as very small ones; this simplifies handling of overflow, meaning that there's only a single place where overflow has to be detected.

- the adjustment step handles adjustments that cross power-of-2 boundaries correctly.

- as a result of the above two simplifications, there's never any need to do a second correction step, so the main correction loop is no longer a loop; a single correction is performed.

- we always use the bigcomp function in hard cases, so there's no longer any need for the computation of ulps_difference to detect the case where the error is exactly 0.5 ulps.


The patch isn't quite ready to apply;  I want to expand some of the comments a little.

----------
Added file: http://bugs.python.org/file17720/rewrite_strtod.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue9009>
_______________________________________