Added precision mode to fast-dtoa.

Added precision mode to fast-dtoa.

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

[William Hesse, 2010-07-30 09:34:35]

Reviewed up to, but not including, DigitGenCounted in fast-dtoa.cc.

http://codereview.chromium.org/2000004/diff/19001/14002
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/2000004/diff/19001/14002#newcode78
src/fast-dtoa.cc:78: // ]w_low; w_low[ (often written as "(w_low; w_low)")
(w_low, w_high)

http://codereview.chromium.org/2000004/diff/19001/14002#newcode126
src/fast-dtoa.cc:126: // the buffer. If we have two potential representations we
need to make sure
when finding the closest representation of 'w'.  If we have two potential
representations, and one is closer to both w_low and w_high, then we know it is
closer to the actual value v.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode146
src/fast-dtoa.cc:146: buffer[length - 1]--;
Comment that all these tests are necessary in this order to detect overflow and
underflow of uint64 values.  ASSERT(rest <= unsafe_interval).

http://codereview.chromium.org/2000004/diff/19001/14002#newcode169
src/fast-dtoa.cc:169: // Rounds the buffer according to rest for the counted
digit generation method.
Rounds the buffer upwards, if the result is closer to v, by possibly adding 1 to
the buffer.  If the precision of the calculation is not sufficient to round
correctly, return false.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode192
src/fast-dtoa.cc:192: // over/underflow.)
Comment that these tests are designed to avoid overflow, and will work correctly
for any uint64 values of rest < ten_kappa and unit.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode210
src/fast-dtoa.cc:210: // the power (the kappa) is increased.
This is slightly weird because the calling function will need to update
ten_kappa, but also needs to update rest with the old value of ten_kappa.  Does
this function have the right interface, or could it be simplified by doing more
or less?

http://codereview.chromium.org/2000004/diff/19001/14002#newcode232
src/fast-dtoa.cc:232: // Precondition: (1 << number_bits) <= number < (1 <<
(number_bits + 1)).
Because we always test, in the switch statement, the first inequality of the
precondition is not actually necessary.
Should you avoid the testing in the switch statement (for example, if
number_bits = 31, you know number > kTen9)?

http://codereview.chromium.org/2000004/diff/19001/25001
File src/fast-dtoa.h (right):

http://codereview.chromium.org/2000004/diff/19001/25001#newcode35
src/fast-dtoa.h:35: // 0.9999999999999999 becomes 0.1
I don't understand this comment.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode59
src/fast-dtoa.h:59: //     0.099999999999 instead of 0.1.
If 0.099999999999 and 0.1 represent the same double value, "1" is returned with
point = 0.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode65
src/fast-dtoa.h:65: //     the difference v - (buffer * 10^(point-length)) is
the smallest for all
is the closest to zero
has the smallest absolute value

if two values are equally close, we round to an even last digit.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode66
src/fast-dtoa.h:66: //     possible decimal numbers of requested_digits digits.
for all decimal integers "buffer" with requested_digits digits.

I don't like quotes though.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode67
src/fast-dtoa.h:67: // For both modes the buffer must be big enough to hold the
result.
must be large enough

[William Hesse, 2010-07-30 13:30:37]

LGTM.

http://codereview.chromium.org/2000004/diff/19001/14002
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/2000004/diff/19001/14002#newcode490
src/fast-dtoa.cc:490: //  * w is correct up to 1 ulp (unit in the last place).
That
What does this mean?  w is the input.  Isn't it exact?   What is "they" - w is a
single number.

Do you mean w represents a range of numbers between w - ulp and w + ulp?

http://codereview.chromium.org/2000004/diff/19001/14002#newcode498
src/fast-dtoa.cc:498: //       digit is rounded according to the rest.
According to the rest of what?  Why not "is rounded correctly"

http://codereview.chromium.org/2000004/diff/19001/14002#newcode500
src/fast-dtoa.cc:500: //
Isn't |eps| < 10^kappa / 2?

http://codereview.chromium.org/2000004/diff/19001/14002#newcode524
src/fast-dtoa.cc:524: uint32_t divider;
divisor, rather than divider.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode553
src/fast-dtoa.cc:553: kappa);
Why do we need to cut off a trailing 0 and reduce kappa by one in this case? 
Isn't it ok to leave it since we know we want that many digits?

http://codereview.chromium.org/2000004/diff/19001/14002#newcode560
src/fast-dtoa.cc:560: // Instead of multiplying by 10 we multiply by 5 (cheaper
operation) and
Is it really a saving to multiply by 5 rather than 10 in this case?  If we
don't, then we don't have to manipulate the exponent.

[Florian Loitsch, 2010-09-17 12:58:42]

Please have another look.

http://codereview.chromium.org/2000004/diff/19001/14002
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/2000004/diff/19001/14002#newcode78
src/fast-dtoa.cc:78: // ]w_low; w_low[ (often written as "(w_low; w_low)")
On 2010/07/30 09:34:36, William Hesse wrote:
> (w_low, w_high)

Done.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode126
src/fast-dtoa.cc:126: // the buffer. If we have two potential representations we
need to make sure
On 2010/07/30 09:34:36, William Hesse wrote:
> when finding the closest representation of 'w'.  If we have two potential
> representations, and one is closer to both w_low and w_high, then we know it
is
> closer to the actual value v.

Done.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode146
src/fast-dtoa.cc:146: buffer[length - 1]--;
On 2010/07/30 09:34:36, William Hesse wrote:
> Comment that all these tests are necessary in this order to detect overflow
and
> underflow of uint64 values.  ASSERT(rest <= unsafe_interval).

Done.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode169
src/fast-dtoa.cc:169: // Rounds the buffer according to rest for the counted
digit generation method.
On 2010/07/30 09:34:36, William Hesse wrote:
> Rounds the buffer upwards, if the result is closer to v, by possibly adding 1
to
> the buffer.  If the precision of the calculation is not sufficient to round
> correctly, return false.

Done.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode192
src/fast-dtoa.cc:192: // over/underflow.)
On 2010/07/30 09:34:36, William Hesse wrote:
> Comment that these tests are designed to avoid overflow, and will work
correctly
> for any uint64 values of rest < ten_kappa and unit.

Done.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode210
src/fast-dtoa.cc:210: // the power (the kappa) is increased.
On 2010/07/30 09:34:36, William Hesse wrote:
> This is slightly weird because the calling function will need to update
> ten_kappa, but also needs to update rest with the old value of ten_kappa. 
Does
> this function have the right interface, or could it be simplified by doing
more
> or less?
The caller basically says: here is my result. Round it if needed. And rounding
includes adjusting the kappa. So the caller doesn't need to do anything. The
callers actually do a tail-call: return RoundWeed(...).
But if you think I should change the interface we can discuss this.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode232
src/fast-dtoa.cc:232: // Precondition: (1 << number_bits) <= number < (1 <<
(number_bits + 1)).
On 2010/07/30 09:34:36, William Hesse wrote:
> Because we always test, in the switch statement, the first inequality of the
> precondition is not actually necessary.
> Should you avoid the testing in the switch statement (for example, if
> number_bits = 31, you know number > kTen9)?
Removed first part of precondition.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode490
src/fast-dtoa.cc:490: //  * w is correct up to 1 ulp (unit in the last place).
That
On 2010/07/30 13:30:37, William Hesse wrote:
> What does this mean?  w is the input.  Isn't it exact?   What is "they" - w is
a
> single number.
> 
> Do you mean w represents a range of numbers between w - ulp and w + ulp?
bad copy paste from DigitGen.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode498
src/fast-dtoa.cc:498: //       digit is rounded according to the rest.
On 2010/07/30 13:30:37, William Hesse wrote:
> According to the rest of what?  Why not "is rounded correctly"
Reworded.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode500
src/fast-dtoa.cc:500: //
On 2010/07/30 13:30:37, William Hesse wrote:
> Isn't |eps| < 10^kappa / 2?
> 
good catch.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode524
src/fast-dtoa.cc:524: uint32_t divider;
On 2010/07/30 13:30:37, William Hesse wrote:
> divisor, rather than divider.

Done.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode553
src/fast-dtoa.cc:553: kappa);
On 2010/07/30 13:30:37, William Hesse wrote:
> Why do we need to cut off a trailing 0 and reduce kappa by one in this case? 
> Isn't it ok to leave it since we know we want that many digits?
I don't understand your question.
At this point we have requested_digits, and simply need to round the number
upwards, if the rest is greater than .5.

http://codereview.chromium.org/2000004/diff/19001/14002#newcode560
src/fast-dtoa.cc:560: // Instead of multiplying by 10 we multiply by 5 (cheaper
operation) and
On 2010/07/30 13:30:37, William Hesse wrote:
> Is it really a saving to multiply by 5 rather than 10 in this case?  If we
> don't, then we don't have to manipulate the exponent.
changed to *10.

http://codereview.chromium.org/2000004/diff/19001/25001
File src/fast-dtoa.h (right):

http://codereview.chromium.org/2000004/diff/19001/25001#newcode35
src/fast-dtoa.h:35: // 0.9999999999999999 becomes 0.1
On 2010/07/30 09:34:36, William Hesse wrote:
> I don't understand this comment.

Done.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode59
src/fast-dtoa.h:59: //     0.099999999999 instead of 0.1.
On 2010/07/30 09:34:36, William Hesse wrote:
> If 0.099999999999 and 0.1 represent the same double value, "1" is returned
with
> point = 0.

Done.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode65
src/fast-dtoa.h:65: //     the difference v - (buffer * 10^(point-length)) is
the smallest for all
On 2010/07/30 09:34:36, William Hesse wrote:
> is the closest to zero
> has the smallest absolute value
> 
> if two values are equally close, we round to an even last digit.

FastDtoa will always return false if two values are equally close.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode66
src/fast-dtoa.h:66: //     possible decimal numbers of requested_digits digits.
On 2010/07/30 09:34:36, William Hesse wrote:
> for all decimal integers "buffer" with requested_digits digits.
> 
> I don't like quotes though.

Done.

http://codereview.chromium.org/2000004/diff/19001/25001#newcode67
src/fast-dtoa.h:67: // For both modes the buffer must be big enough to hold the
result.
On 2010/07/30 09:34:36, William Hesse wrote:
> must be large enough

Done.

[William Hesse, 2010-09-20 06:58:16]

LGTM.  Comments seem clearer.

http://codereview.chromium.org/2000004/diff/52001/56001
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/2000004/diff/52001/56001#newcode216
src/fast-dtoa.cc:216: // exception of the first digit all digits are now '0'.
Simply switch the
OK, My earlier comment was a misunderstanding - I thought we were reacting to
every carry in the last place, not just a carry that propagated all the way to
overflow the most significant digit.

http://codereview.chromium.org/2000004/diff/52001/56001#newcode518
src/fast-dtoa.cc:518: uint64_t unit = 1;
Could this be called precision, or precision_unit, so it is not as easy to
confuse with one?

"The precision of w, which starts at 1 ulp and scales as we scale w to extract
the digits."

[Florian Loitsch, 2010-09-20 09:06:19]

http://codereview.chromium.org/2000004/diff/52001/56001
File src/fast-dtoa.cc (right):

http://codereview.chromium.org/2000004/diff/52001/56001#newcode518
src/fast-dtoa.cc:518: uint64_t unit = 1;
On 2010/09/20 06:58:16, William Hesse wrote:
> Could this be called precision, or precision_unit, so it is not as easy to
> confuse with one?
> 
> "The precision of w, which starts at 1 ulp and scales as we scale w to extract
> the digits."
> 

renamed to w_error. and updated comment.