Add bignum fall-back when the fast dtoa doesn't succeed. This removes Gay's d...

Add bignum fall-back when the fast dtoa doesn't succeed. This removes Gay's dtoa for the double->string direction. We still need it for the string->double direction.

Committed: http://code.google.com/p/v8/source/detail?r=5840

[Florian Loitsch, 2010-09-20 14:15:48]

These are the remaining dtoa-changes I had on my hard-drive.

[Florian Loitsch, 2010-10-28 11:33:41]

Updated bignum-implementation. It is now the same as for the pending strtod CL.

[Florian Loitsch, 2010-11-08 14:32:37]

Updated to latest revision.
This CL uses the checked-in bignum implementation now.

[William Hesse, 2010-11-15 15:48:30]

Please add more comments to bignum-dtoa explaining the basic principles, and
giving a big-picture view of what each function accomplishes.  Otherwise, LGTM.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc
File src/bignum-dtoa.cc (right):

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode39
src/bignum-dtoa.cc:39: // Returns an estimation of k such that 10^(k-1) <= v <
10^k.
This is unclear. Explains that the input is the exponent from a normalized fp
number f * 2^e, where 2^52 <= f < 2^53.  The output is an approximation for the
exponent of the decimal approximation .digits * 10^k.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode41
src/bignum-dtoa.cc:41: // Note: the same is true for v + wiggle_plus (instead of
simply v) (see
What is wiggle_plus?

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode66
src/bignum-dtoa.cc:66: // Explanation for (v + wiggle_plus): the computation
takes advantage of the
Can the wiggle stuff be put where wiggle is used?

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode99
src/bignum-dtoa.cc:99: if (need_wiggles) {
Call these delta_plus and delta_minus, or something, and explain that v_plus =
(f + delta_plus) * 2^e is the boundary between v and the next representable
float, and so on.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode312
src/bignum-dtoa.cc:312: // Produces the least amount of digits so that the
result lies in the wiggle
Give more big picture comments - result lying in the wiggle room means produce
enough digits d of strtod(v) so that v is the closest representable number to d
* 10^exp.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode319
src/bignum-dtoa.cc:319: static void GenerateDigits(Bignum* numerator, Bignum*
denominator,
GenerateShortestDigits?

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode423
src/bignum-dtoa.cc:423: // digit = numerator / denominator (integer division).
Include "Assumes numerator / denominator < 10" (or < 16, or whatever).

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode436
src/bignum-dtoa.cc:436: // Correct bad digits (in case we had a sequence of
'9's).
Propagate the carry until we hit a non-'9' or til we reach the first digit.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode442
src/bignum-dtoa.cc:442: if (buffer[0] == '0' + 10) {
Propagate a carry past the top place.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode459
src/bignum-dtoa.cc:459: if (-(*decimal_point) > requested_digits) {
Explain this.  People don't know what all these quantities are.  
// Number is smaller than 0.00...001, with requested_digits 0s after the decimal
point.  Return 0.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode465
src/bignum-dtoa.cc:465: denominator->Times10();  // Bring fraction back to range
0.1 - 1.
Why does this bring the fraction to that range?

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode496
src/bignum-dtoa.cc:496: bool need_wiggles = (mode == BIGNUM_DTOA_SHORTEST);
bool compute_shortest_approximation =, instead of need_wiggles?

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode517
src/bignum-dtoa.cc:517: // 4e-324. In this case the denominator needs less than
324*4 binary digits.
fewer than

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode518
src/bignum-dtoa.cc:518: // The maximum double is 1.7976931348623157e308 which
needs less than
fewer

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h
File src/bignum-dtoa.h (right):

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode35
src/bignum-dtoa.h:35: // 0.9999999999999999 becomes 0.1
Better description, not just an example.

Or say "see below, at declaration of BignumDtoa."

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode37
src/bignum-dtoa.h:37: // Fixed number of digits after the comma.
Return a fixed number of digits after the decimal point (or radix point).

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode41
src/bignum-dtoa.h:41: // Fixed number of digits (independent of the comma).
Return a fixed number of digits, no matter what the exponent is.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode59
src/bignum-dtoa.h:59: //   'requested_digits' digits after the comma. The
produced digits might be too
decimal point, radix point.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode69
src/bignum-dtoa.h:69: //   'requested_digits', the function is allowed to return
less digits, in which
fewer

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode72
src/bignum-dtoa.h:72: // The given memory-management functions are only needed
for internal bignum
No memory management functions are passed in anymore.

http://codereview.chromium.org/3468003/diff/50001/src/dtoa.h
File src/dtoa.h (right):

http://codereview.chromium.org/3468003/diff/50001/src/dtoa.h#newcode76
src/dtoa.h:76: // at least kBase10MaximalLength + 1 and otherwise the
requested_digits
+ 1.  Otherwise, the size of the output is limited to requested_digits digits
plus the null terminator.

http://codereview.chromium.org/3468003/diff/50001/test/cctest/test-bignum-dto...
File test/cctest/test-bignum-dtoa.cc (right):

http://codereview.chromium.org/3468003/diff/50001/test/cctest/test-bignum-dto...
test/cctest/test-bignum-dtoa.cc:44: // Removes trailing '0' digits.
// Can return the empty string if all digits are 0.

http://codereview.chromium.org/3468003/diff/50001/test/cctest/test-bignum-dto...
test/cctest/test-bignum-dtoa.cc:255: 
Are these tests taken from the Gay strtod implementation?  Otherwise, the above
tests could be merged into the below ones, right?

[Florian Loitsch, 2010-11-16 14:32:06]

Please have another look.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc
File src/bignum-dtoa.cc (right):

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode39
src/bignum-dtoa.cc:39: // Returns an estimation of k such that 10^(k-1) <= v <
10^k.
On 2010/11/15 15:48:30, William Hesse wrote:
> This is unclear. Explains that the input is the exponent from a normalized fp
> number f * 2^e, where 2^52 <= f < 2^53.  The output is an approximation for
the
> exponent of the decimal approximation .digits * 10^k.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode41
src/bignum-dtoa.cc:41: // Note: the same is true for v + wiggle_plus (instead of
simply v) (see
On 2010/11/15 15:48:30, William Hesse wrote:
> What is wiggle_plus?

Changed to v+ (v's positive boundary).

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode66
src/bignum-dtoa.cc:66: // Explanation for (v + wiggle_plus): the computation
takes advantage of the
On 2010/11/15 15:48:30, William Hesse wrote:
> Can the wiggle stuff be put where wiggle is used?

Reworked comment.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode99
src/bignum-dtoa.cc:99: if (need_wiggles) {
On 2010/11/15 15:48:30, William Hesse wrote:
> Call these delta_plus and delta_minus, or something, and explain that v_plus =
> (f + delta_plus) * 2^e is the boundary between v and the next representable
> float, and so on.

Refactored (slightly) method and comments.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode312
src/bignum-dtoa.cc:312: // Produces the least amount of digits so that the
result lies in the wiggle
On 2010/11/15 15:48:30, William Hesse wrote:
> Give more big picture comments - result lying in the wiggle room means produce
> enough digits d of strtod(v) so that v is the closest representable number to
d
> * 10^exp.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode319
src/bignum-dtoa.cc:319: static void GenerateDigits(Bignum* numerator, Bignum*
denominator,
On 2010/11/15 15:48:30, William Hesse wrote:
> GenerateShortestDigits?

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode423
src/bignum-dtoa.cc:423: // digit = numerator / denominator (integer division).
On 2010/11/15 15:48:30, William Hesse wrote:
> Include "Assumes numerator / denominator < 10" (or < 16, or whatever).

added ASSERT.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode436
src/bignum-dtoa.cc:436: // Correct bad digits (in case we had a sequence of
'9's).
On 2010/11/15 15:48:30, William Hesse wrote:
> Propagate the carry until we hit a non-'9' or til we reach the first digit.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode442
src/bignum-dtoa.cc:442: if (buffer[0] == '0' + 10) {
On 2010/11/15 15:48:30, William Hesse wrote:
> Propagate a carry past the top place.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode459
src/bignum-dtoa.cc:459: if (-(*decimal_point) > requested_digits) {
On 2010/11/15 15:48:30, William Hesse wrote:
> Explain this.  People don't know what all these quantities are.  
> // Number is smaller than 0.00...001, with requested_digits 0s after the
decimal
> point.  Return 0.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode465
src/bignum-dtoa.cc:465: denominator->Times10();  // Bring fraction back to range
0.1 - 1.
On 2010/11/15 15:48:30, William Hesse wrote:
> Why does this bring the fraction to that range?

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode496
src/bignum-dtoa.cc:496: bool need_wiggles = (mode == BIGNUM_DTOA_SHORTEST);
On 2010/11/15 15:48:30, William Hesse wrote:
> bool compute_shortest_approximation =, instead of need_wiggles?

renamed to need_boundary_deltas.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode517
src/bignum-dtoa.cc:517: // 4e-324. In this case the denominator needs less than
324*4 binary digits.
On 2010/11/15 15:48:30, William Hesse wrote:
> fewer than

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.cc#newcode518
src/bignum-dtoa.cc:518: // The maximum double is 1.7976931348623157e308 which
needs less than
On 2010/11/15 15:48:30, William Hesse wrote:
> fewer

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h
File src/bignum-dtoa.h (right):

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode35
src/bignum-dtoa.h:35: // 0.9999999999999999 becomes 0.1
On 2010/11/15 15:48:30, William Hesse wrote:
> Better description, not just an example.
> 
> Or say "see below, at declaration of BignumDtoa."

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode37
src/bignum-dtoa.h:37: // Fixed number of digits after the comma.
On 2010/11/15 15:48:30, William Hesse wrote:
> Return a fixed number of digits after the decimal point (or radix point).

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode41
src/bignum-dtoa.h:41: // Fixed number of digits (independent of the comma).
On 2010/11/15 15:48:30, William Hesse wrote:
> Return a fixed number of digits, no matter what the exponent is.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode59
src/bignum-dtoa.h:59: //   'requested_digits' digits after the comma. The
produced digits might be too
On 2010/11/15 15:48:30, William Hesse wrote:
> decimal point, radix point.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode69
src/bignum-dtoa.h:69: //   'requested_digits', the function is allowed to return
less digits, in which
On 2010/11/15 15:48:30, William Hesse wrote:
> fewer

Done.

http://codereview.chromium.org/3468003/diff/50001/src/bignum-dtoa.h#newcode72
src/bignum-dtoa.h:72: // The given memory-management functions are only needed
for internal bignum
On 2010/11/15 15:48:30, William Hesse wrote:
> No memory management functions are passed in anymore.

Done.

http://codereview.chromium.org/3468003/diff/50001/src/dtoa.h
File src/dtoa.h (right):

http://codereview.chromium.org/3468003/diff/50001/src/dtoa.h#newcode76
src/dtoa.h:76: // at least kBase10MaximalLength + 1 and otherwise the
requested_digits
On 2010/11/15 15:48:30, William Hesse wrote:
> + 1.  Otherwise, the size of the output is limited to requested_digits digits
> plus the null terminator.

Done.

http://codereview.chromium.org/3468003/diff/50001/test/cctest/test-bignum-dto...
File test/cctest/test-bignum-dtoa.cc (right):

http://codereview.chromium.org/3468003/diff/50001/test/cctest/test-bignum-dto...
test/cctest/test-bignum-dtoa.cc:44: // Removes trailing '0' digits.
On 2010/11/15 15:48:30, William Hesse wrote:
> // Can return the empty string if all digits are 0.

Done.

http://codereview.chromium.org/3468003/diff/50001/test/cctest/test-bignum-dto...
test/cctest/test-bignum-dtoa.cc:255: 
On 2010/11/15 15:48:30, William Hesse wrote:
> Are these tests taken from the Gay strtod implementation?  Otherwise, the
above
> tests could be merged into the below ones, right?

They could be merged, but the numbers from Gay are simply random values, whereas
most of the "Various" ones try to exercise different parts of the dtoa-routine.

[William Hesse, 2010-11-17 09:44:08]

LGTM.  Some further changes to comments suggested.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc
File src/bignum-dtoa.cc (right):

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode243
src/bignum-dtoa.cc:243: // The initial start values consist of:
How about:
Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator
and denominator. The functions GenerateShortestDigits and GenerateCountedDigits
will then convert this ratio to its decimal representation, d, with the required
accuracy, and then d * 10^estimated_power is the representation of v.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode246
src/bignum-dtoa.cc:246: //  optionally (depending on the flag
need_boundary_deltas):
Might as well say here: used by GenerateShortestDigits to decide if it has the
shortest decimal converting back to v.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode249
src/bignum-dtoa.cc:249: // The scaling consist of multiplying the numerator by
10^estimated_power, or
Not needed.  This will be obvious from the code, or commented there.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode252
src/bignum-dtoa.cc:252: // Note that the boundary-deltas are scaled too. If the
common denominator has
Not needed, except to say that v, m+, m-, and therefore v - m- and m+ - v all
share the same denominator.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode338
src/bignum-dtoa.cc:338: // when the generated digits yield a number that is
close enough. The number
yield the shortest decimal representation of v.  A decimal representation of v
is a number lying closer to v than to any other double, so it converts to v when
read.

This is true if d, the decimal representation, is between m- and m+, the upper
and lower boundaries.  d must be strictly between them if !is_even.
m+ = ...
m- = ...

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode455
src/bignum-dtoa.cc:455: // Let v = numerator / denominator.
// Let v = numerator / denominator < 10.
// Then we generate 'count' digits of d = x.xxxxxxx... from left to right. Once
'count' digits have
been produced we decide whether to round up or down. Remainders of exactly .5
round upwards.  Numbers such 9.99999 propagate a carry all the way, and change
the exponent, when rounding upwards.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode571
src/bignum-dtoa.cc:571: Bignum numerator;
As long as there is a header file, could the order of the functions be reversed,
putting the major functions first, and the helpers they call later?  It would be
easier to read.

Or even use forward declarations for the static functions, with a short
description of their function?

[Florian Loitsch, 2010-11-17 12:47:59]

Uploaded two patchsets. The first one addresses most of the comments. The second
one reorders the functions and adds forward declarations.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc
File src/bignum-dtoa.cc (right):

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode243
src/bignum-dtoa.cc:243: // The initial start values consist of:
On 2010/11/17 09:44:09, William Hesse wrote:
> How about:
> Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator
> and denominator. The functions GenerateShortestDigits and
GenerateCountedDigits
> will then convert this ratio to its decimal representation, d, with the
required
> accuracy, and then d * 10^estimated_power is the representation of v.

Done.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode246
src/bignum-dtoa.cc:246: //  optionally (depending on the flag
need_boundary_deltas):
On 2010/11/17 09:44:09, William Hesse wrote:
> Might as well say here: used by GenerateShortestDigits to decide if it has the
> shortest decimal converting back to v.

Done.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode249
src/bignum-dtoa.cc:249: // The scaling consist of multiplying the numerator by
10^estimated_power, or
On 2010/11/17 09:44:09, William Hesse wrote:
> Not needed.  This will be obvious from the code, or commented there.

Done.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode252
src/bignum-dtoa.cc:252: // Note that the boundary-deltas are scaled too. If the
common denominator has
On 2010/11/17 09:44:09, William Hesse wrote:
> Not needed, except to say that v, m+, m-, and therefore v - m- and m+ - v all
> share the same denominator.

Done.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode338
src/bignum-dtoa.cc:338: // when the generated digits yield a number that is
close enough. The number
On 2010/11/17 09:44:09, William Hesse wrote:
> yield the shortest decimal representation of v.  A decimal representation of v
> is a number lying closer to v than to any other double, so it converts to v
when
> read.
> 
> This is true if d, the decimal representation, is between m- and m+, the upper
> and lower boundaries.  d must be strictly between them if !is_even.
> m+ = ...
> m- = ...

Done.

http://codereview.chromium.org/3468003/diff/61001/src/bignum-dtoa.cc#newcode455
src/bignum-dtoa.cc:455: // Let v = numerator / denominator.
On 2010/11/17 09:44:09, William Hesse wrote:
> // Let v = numerator / denominator < 10.
> // Then we generate 'count' digits of d = x.xxxxxxx... from left to right.
Once
> 'count' digits have
> been produced we decide whether to round up or down. Remainders of exactly .5
> round upwards.  Numbers such 9.99999 propagate a carry all the way, and change
> the exponent, when rounding upwards.

Done.

[William Hesse, 2010-11-17 13:15:43]

LGTM.