1 // Copyright 2011 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/numbers/bignum-dtoa.h"
6
7 #include <cmath>
8
9 #include "src/base/logging.h"
10 #include "src/numbers/bignum.h"
11 #include "src/numbers/double.h"
12 #include "src/utils/utils.h"
13
14 namespace v8 {
15 namespace internal {
16
NormalizedExponent(uint64_t significand,int exponent)17 static int NormalizedExponent(uint64_t significand, int exponent) {
18 DCHECK_NE(significand, 0);
19 while ((significand & Double::kHiddenBit) == 0) {
20 significand = significand << 1;
21 exponent = exponent - 1;
22 }
23 return exponent;
24 }
25
26 // Forward declarations:
27 // Returns an estimation of k such that 10^(k-1) <= v < 10^k.
28 static int EstimatePower(int exponent);
29 // Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator
30 // and denominator.
31 static void InitialScaledStartValues(double v, int estimated_power,
32 bool need_boundary_deltas,
33 Bignum* numerator, Bignum* denominator,
34 Bignum* delta_minus, Bignum* delta_plus);
35 // Multiplies numerator/denominator so that its values lies in the range 1-10.
36 // Returns decimal_point s.t.
37 // v = numerator'/denominator' * 10^(decimal_point-1)
38 // where numerator' and denominator' are the values of numerator and
39 // denominator after the call to this function.
40 static void FixupMultiply10(int estimated_power, bool is_even,
41 int* decimal_point, Bignum* numerator,
42 Bignum* denominator, Bignum* delta_minus,
43 Bignum* delta_plus);
44 // Generates digits from the left to the right and stops when the generated
45 // digits yield the shortest decimal representation of v.
46 static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator,
47 Bignum* delta_minus, Bignum* delta_plus,
48 bool is_even, Vector<char> buffer,
49 int* length);
50 // Generates 'requested_digits' after the decimal point.
51 static void BignumToFixed(int requested_digits, int* decimal_point,
52 Bignum* numerator, Bignum* denominator,
53 Vector<char>(buffer), int* length);
54 // Generates 'count' digits of numerator/denominator.
55 // Once 'count' digits have been produced rounds the result depending on the
56 // remainder (remainders of exactly .5 round upwards). Might update the
57 // decimal_point when rounding up (for example for 0.9999).
58 static void GenerateCountedDigits(int count, int* decimal_point,
59 Bignum* numerator, Bignum* denominator,
60 Vector<char>(buffer), int* length);
61
BignumDtoa(double v,BignumDtoaMode mode,int requested_digits,Vector<char> buffer,int * length,int * decimal_point)62 void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits,
63 Vector<char> buffer, int* length, int* decimal_point) {
64 DCHECK_GT(v, 0);
65 DCHECK(!Double(v).IsSpecial());
66 uint64_t significand = Double(v).Significand();
67 bool is_even = (significand & 1) == 0;
68 int exponent = Double(v).Exponent();
69 int normalized_exponent = NormalizedExponent(significand, exponent);
70 // estimated_power might be too low by 1.
71 int estimated_power = EstimatePower(normalized_exponent);
72
73 // Shortcut for Fixed.
74 // The requested digits correspond to the digits after the point. If the
75 // number is much too small, then there is no need in trying to get any
76 // digits.
77 if (mode == BIGNUM_DTOA_FIXED && -estimated_power - 1 > requested_digits) {
78 buffer[0] = '\0';
79 *length = 0;
80 // Set decimal-point to -requested_digits. This is what Gay does.
81 // Note that it should not have any effect anyways since the string is
82 // empty.
83 *decimal_point = -requested_digits;
84 return;
85 }
86
87 Bignum numerator;
88 Bignum denominator;
89 Bignum delta_minus;
90 Bignum delta_plus;
91 // Make sure the bignum can grow large enough. The smallest double equals
92 // 4e-324. In this case the denominator needs fewer than 324*4 binary digits.
93 // The maximum double is 1.7976931348623157e308 which needs fewer than
94 // 308*4 binary digits.
95 DCHECK_GE(Bignum::kMaxSignificantBits, 324 * 4);
96 bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST);
97 InitialScaledStartValues(v, estimated_power, need_boundary_deltas, &numerator,
98 &denominator, &delta_minus, &delta_plus);
99 // We now have v = (numerator / denominator) * 10^estimated_power.
100 FixupMultiply10(estimated_power, is_even, decimal_point, &numerator,
101 &denominator, &delta_minus, &delta_plus);
102 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and
103 // 1 <= (numerator + delta_plus) / denominator < 10
104 switch (mode) {
105 case BIGNUM_DTOA_SHORTEST:
106 GenerateShortestDigits(&numerator, &denominator, &delta_minus,
107 &delta_plus, is_even, buffer, length);
108 break;
109 case BIGNUM_DTOA_FIXED:
110 BignumToFixed(requested_digits, decimal_point, &numerator, &denominator,
111 buffer, length);
112 break;
113 case BIGNUM_DTOA_PRECISION:
114 GenerateCountedDigits(requested_digits, decimal_point, &numerator,
115 &denominator, buffer, length);
116 break;
117 default:
118 UNREACHABLE();
119 }
120 buffer[*length] = '\0';
121 }
122
123 // The procedure starts generating digits from the left to the right and stops
124 // when the generated digits yield the shortest decimal representation of v. A
125 // decimal representation of v is a number lying closer to v than to any other
126 // double, so it converts to v when read.
127 //
128 // This is true if d, the decimal representation, is between m- and m+, the
129 // upper and lower boundaries. d must be strictly between them if !is_even.
130 // m- := (numerator - delta_minus) / denominator
131 // m+ := (numerator + delta_plus) / denominator
132 //
133 // Precondition: 0 <= (numerator+delta_plus) / denominator < 10.
134 // If 1 <= (numerator+delta_plus) / denominator < 10 then no leading 0 digit
135 // will be produced. This should be the standard precondition.
GenerateShortestDigits(Bignum * numerator,Bignum * denominator,Bignum * delta_minus,Bignum * delta_plus,bool is_even,Vector<char> buffer,int * length)136 static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator,
137 Bignum* delta_minus, Bignum* delta_plus,
138 bool is_even, Vector<char> buffer,
139 int* length) {
140 // Small optimization: if delta_minus and delta_plus are the same just reuse
141 // one of the two bignums.
142 if (Bignum::Equal(*delta_minus, *delta_plus)) {
143 delta_plus = delta_minus;
144 }
145 *length = 0;
146 while (true) {
147 uint16_t digit;
148 digit = numerator->DivideModuloIntBignum(*denominator);
149 DCHECK_LE(digit, 9); // digit is a uint16_t and therefore always positive.
150 // digit = numerator / denominator (integer division).
151 // numerator = numerator % denominator.
152 buffer[(*length)++] = digit + '0';
153
154 // Can we stop already?
155 // If the remainder of the division is less than the distance to the lower
156 // boundary we can stop. In this case we simply round down (discarding the
157 // remainder).
158 // Similarly we test if we can round up (using the upper boundary).
159 bool in_delta_room_minus;
160 bool in_delta_room_plus;
161 if (is_even) {
162 in_delta_room_minus = Bignum::LessEqual(*numerator, *delta_minus);
163 } else {
164 in_delta_room_minus = Bignum::Less(*numerator, *delta_minus);
165 }
166 if (is_even) {
167 in_delta_room_plus =
168 Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0;
169 } else {
170 in_delta_room_plus =
171 Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0;
172 }
173 if (!in_delta_room_minus && !in_delta_room_plus) {
174 // Prepare for next iteration.
175 numerator->Times10();
176 delta_minus->Times10();
177 // We optimized delta_plus to be equal to delta_minus (if they share the
178 // same value). So don't multiply delta_plus if they point to the same
179 // object.
180 if (delta_minus != delta_plus) {
181 delta_plus->Times10();
182 }
183 } else if (in_delta_room_minus && in_delta_room_plus) {
184 // Let's see if 2*numerator < denominator.
185 // If yes, then the next digit would be < 5 and we can round down.
186 int compare = Bignum::PlusCompare(*numerator, *numerator, *denominator);
187 if (compare < 0) {
188 // Remaining digits are less than .5. -> Round down (== do nothing).
189 } else if (compare > 0) {
190 // Remaining digits are more than .5 of denominator. -> Round up.
191 // Note that the last digit could not be a '9' as otherwise the whole
192 // loop would have stopped earlier.
193 // We still have an assert here in case the preconditions were not
194 // satisfied.
195 DCHECK_NE(buffer[(*length) - 1], '9');
196 buffer[(*length) - 1]++;
197 } else {
198 // Halfway case.
199 // TODO(floitsch): need a way to solve half-way cases.
200 // For now let's round towards even (since this is what Gay seems to
201 // do).
202
203 if ((buffer[(*length) - 1] - '0') % 2 == 0) {
204 // Round down => Do nothing.
205 } else {
206 DCHECK_NE(buffer[(*length) - 1], '9');
207 buffer[(*length) - 1]++;
208 }
209 }
210 return;
211 } else if (in_delta_room_minus) {
212 // Round down (== do nothing).
213 return;
214 } else { // in_delta_room_plus
215 // Round up.
216 // Note again that the last digit could not be '9' since this would have
217 // stopped the loop earlier.
218 // We still have an DCHECK here, in case the preconditions were not
219 // satisfied.
220 DCHECK_NE(buffer[(*length) - 1], '9');
221 buffer[(*length) - 1]++;
222 return;
223 }
224 }
225 }
226
227 // Let v = numerator / denominator < 10.
228 // Then we generate 'count' digits of d = x.xxxxx... (without the decimal point)
229 // from left to right. Once 'count' digits have been produced we decide wether
230 // to round up or down. Remainders of exactly .5 round upwards. Numbers such
231 // as 9.999999 propagate a carry all the way, and change the
232 // exponent (decimal_point), when rounding upwards.
GenerateCountedDigits(int count,int * decimal_point,Bignum * numerator,Bignum * denominator,Vector<char> (buffer),int * length)233 static void GenerateCountedDigits(int count, int* decimal_point,
234 Bignum* numerator, Bignum* denominator,
235 Vector<char>(buffer), int* length) {
236 DCHECK_GE(count, 0);
237 for (int i = 0; i < count - 1; ++i) {
238 uint16_t digit;
239 digit = numerator->DivideModuloIntBignum(*denominator);
240 DCHECK_LE(digit, 9); // digit is a uint16_t and therefore always positive.
241 // digit = numerator / denominator (integer division).
242 // numerator = numerator % denominator.
243 buffer[i] = digit + '0';
244 // Prepare for next iteration.
245 numerator->Times10();
246 }
247 // Generate the last digit.
248 uint16_t digit;
249 digit = numerator->DivideModuloIntBignum(*denominator);
250 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) {
251 digit++;
252 }
253 buffer[count - 1] = digit + '0';
254 // Correct bad digits (in case we had a sequence of '9's). Propagate the
255 // carry until we hat a non-'9' or til we reach the first digit.
256 for (int i = count - 1; i > 0; --i) {
257 if (buffer[i] != '0' + 10) break;
258 buffer[i] = '0';
259 buffer[i - 1]++;
260 }
261 if (buffer[0] == '0' + 10) {
262 // Propagate a carry past the top place.
263 buffer[0] = '1';
264 (*decimal_point)++;
265 }
266 *length = count;
267 }
268
269 // Generates 'requested_digits' after the decimal point. It might omit
270 // trailing '0's. If the input number is too small then no digits at all are
271 // generated (ex.: 2 fixed digits for 0.00001).
272 //
273 // Input verifies: 1 <= (numerator + delta) / denominator < 10.
BignumToFixed(int requested_digits,int * decimal_point,Bignum * numerator,Bignum * denominator,Vector<char> (buffer),int * length)274 static void BignumToFixed(int requested_digits, int* decimal_point,
275 Bignum* numerator, Bignum* denominator,
276 Vector<char>(buffer), int* length) {
277 // Note that we have to look at more than just the requested_digits, since
278 // a number could be rounded up. Example: v=0.5 with requested_digits=0.
279 // Even though the power of v equals 0 we can't just stop here.
280 if (-(*decimal_point) > requested_digits) {
281 // The number is definitively too small.
282 // Ex: 0.001 with requested_digits == 1.
283 // Set decimal-point to -requested_digits. This is what Gay does.
284 // Note that it should not have any effect anyways since the string is
285 // empty.
286 *decimal_point = -requested_digits;
287 *length = 0;
288 return;
289 } else if (-(*decimal_point) == requested_digits) {
290 // We only need to verify if the number rounds down or up.
291 // Ex: 0.04 and 0.06 with requested_digits == 1.
292 DCHECK(*decimal_point == -requested_digits);
293 // Initially the fraction lies in range (1, 10]. Multiply the denominator
294 // by 10 so that we can compare more easily.
295 denominator->Times10();
296 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) {
297 // If the fraction is >= 0.5 then we have to include the rounded
298 // digit.
299 buffer[0] = '1';
300 *length = 1;
301 (*decimal_point)++;
302 } else {
303 // Note that we caught most of similar cases earlier.
304 *length = 0;
305 }
306 return;
307 } else {
308 // The requested digits correspond to the digits after the point.
309 // The variable 'needed_digits' includes the digits before the point.
310 int needed_digits = (*decimal_point) + requested_digits;
311 GenerateCountedDigits(needed_digits, decimal_point, numerator, denominator,
312 buffer, length);
313 }
314 }
315
316 // Returns an estimation of k such that 10^(k-1) <= v < 10^k where
317 // v = f * 2^exponent and 2^52 <= f < 2^53.
318 // v is hence a normalized double with the given exponent. The output is an
319 // approximation for the exponent of the decimal approimation .digits * 10^k.
320 //
321 // The result might undershoot by 1 in which case 10^k <= v < 10^k+1.
322 // Note: this property holds for v's upper boundary m+ too.
323 // 10^k <= m+ < 10^k+1.
324 // (see explanation below).
325 //
326 // Examples:
327 // EstimatePower(0) => 16
328 // EstimatePower(-52) => 0
329 //
330 // Note: e >= 0 => EstimatedPower(e) > 0. No similar claim can be made for e<0.
EstimatePower(int exponent)331 static int EstimatePower(int exponent) {
332 // This function estimates log10 of v where v = f*2^e (with e == exponent).
333 // Note that 10^floor(log10(v)) <= v, but v <= 10^ceil(log10(v)).
334 // Note that f is bounded by its container size. Let p = 53 (the double's
335 // significand size). Then 2^(p-1) <= f < 2^p.
336 //
337 // Given that log10(v) == log2(v)/log2(10) and e+(len(f)-1) is quite close
338 // to log2(v) the function is simplified to (e+(len(f)-1)/log2(10)).
339 // The computed number undershoots by less than 0.631 (when we compute log3
340 // and not log10).
341 //
342 // Optimization: since we only need an approximated result this computation
343 // can be performed on 64 bit integers. On x86/x64 architecture the speedup is
344 // not really measurable, though.
345 //
346 // Since we want to avoid overshooting we decrement by 1e10 so that
347 // floating-point imprecisions don't affect us.
348 //
349 // Explanation for v's boundary m+: the computation takes advantage of
350 // the fact that 2^(p-1) <= f < 2^p. Boundaries still satisfy this requirement
351 // (even for denormals where the delta can be much more important).
352
353 const double k1Log10 = 0.30102999566398114; // 1/lg(10)
354
355 // For doubles len(f) == 53 (don't forget the hidden bit).
356 const int kSignificandSize = 53;
357 double estimate =
358 std::ceil((exponent + kSignificandSize - 1) * k1Log10 - 1e-10);
359 return static_cast<int>(estimate);
360 }
361
362 // See comments for InitialScaledStartValues.
InitialScaledStartValuesPositiveExponent(double v,int estimated_power,bool need_boundary_deltas,Bignum * numerator,Bignum * denominator,Bignum * delta_minus,Bignum * delta_plus)363 static void InitialScaledStartValuesPositiveExponent(
364 double v, int estimated_power, bool need_boundary_deltas, Bignum* numerator,
365 Bignum* denominator, Bignum* delta_minus, Bignum* delta_plus) {
366 // A positive exponent implies a positive power.
367 DCHECK_GE(estimated_power, 0);
368 // Since the estimated_power is positive we simply multiply the denominator
369 // by 10^estimated_power.
370
371 // numerator = v.
372 numerator->AssignUInt64(Double(v).Significand());
373 numerator->ShiftLeft(Double(v).Exponent());
374 // denominator = 10^estimated_power.
375 denominator->AssignPowerUInt16(10, estimated_power);
376
377 if (need_boundary_deltas) {
378 // Introduce a common denominator so that the deltas to the boundaries are
379 // integers.
380 denominator->ShiftLeft(1);
381 numerator->ShiftLeft(1);
382 // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common
383 // denominator (of 2) delta_plus equals 2^e.
384 delta_plus->AssignUInt16(1);
385 delta_plus->ShiftLeft(Double(v).Exponent());
386 // Same for delta_minus (with adjustments below if f == 2^p-1).
387 delta_minus->AssignUInt16(1);
388 delta_minus->ShiftLeft(Double(v).Exponent());
389
390 // If the significand (without the hidden bit) is 0, then the lower
391 // boundary is closer than just half a ulp (unit in the last place).
392 // There is only one exception: if the next lower number is a denormal then
393 // the distance is 1 ulp. This cannot be the case for exponent >= 0 (but we
394 // have to test it in the other function where exponent < 0).
395 uint64_t v_bits = Double(v).AsUint64();
396 if ((v_bits & Double::kSignificandMask) == 0) {
397 // The lower boundary is closer at half the distance of "normal" numbers.
398 // Increase the common denominator and adapt all but the delta_minus.
399 denominator->ShiftLeft(1); // *2
400 numerator->ShiftLeft(1); // *2
401 delta_plus->ShiftLeft(1); // *2
402 }
403 }
404 }
405
406 // See comments for InitialScaledStartValues
InitialScaledStartValuesNegativeExponentPositivePower(double v,int estimated_power,bool need_boundary_deltas,Bignum * numerator,Bignum * denominator,Bignum * delta_minus,Bignum * delta_plus)407 static void InitialScaledStartValuesNegativeExponentPositivePower(
408 double v, int estimated_power, bool need_boundary_deltas, Bignum* numerator,
409 Bignum* denominator, Bignum* delta_minus, Bignum* delta_plus) {
410 uint64_t significand = Double(v).Significand();
411 int exponent = Double(v).Exponent();
412 // v = f * 2^e with e < 0, and with estimated_power >= 0.
413 // This means that e is close to 0 (have a look at how estimated_power is
414 // computed).
415
416 // numerator = significand
417 // since v = significand * 2^exponent this is equivalent to
418 // numerator = v * / 2^-exponent
419 numerator->AssignUInt64(significand);
420 // denominator = 10^estimated_power * 2^-exponent (with exponent < 0)
421 denominator->AssignPowerUInt16(10, estimated_power);
422 denominator->ShiftLeft(-exponent);
423
424 if (need_boundary_deltas) {
425 // Introduce a common denominator so that the deltas to the boundaries are
426 // integers.
427 denominator->ShiftLeft(1);
428 numerator->ShiftLeft(1);
429 // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common
430 // denominator (of 2) delta_plus equals 2^e.
431 // Given that the denominator already includes v's exponent the distance
432 // to the boundaries is simply 1.
433 delta_plus->AssignUInt16(1);
434 // Same for delta_minus (with adjustments below if f == 2^p-1).
435 delta_minus->AssignUInt16(1);
436
437 // If the significand (without the hidden bit) is 0, then the lower
438 // boundary is closer than just one ulp (unit in the last place).
439 // There is only one exception: if the next lower number is a denormal
440 // then the distance is 1 ulp. Since the exponent is close to zero
441 // (otherwise estimated_power would have been negative) this cannot happen
442 // here either.
443 uint64_t v_bits = Double(v).AsUint64();
444 if ((v_bits & Double::kSignificandMask) == 0) {
445 // The lower boundary is closer at half the distance of "normal" numbers.
446 // Increase the denominator and adapt all but the delta_minus.
447 denominator->ShiftLeft(1); // *2
448 numerator->ShiftLeft(1); // *2
449 delta_plus->ShiftLeft(1); // *2
450 }
451 }
452 }
453
454 // See comments for InitialScaledStartValues
InitialScaledStartValuesNegativeExponentNegativePower(double v,int estimated_power,bool need_boundary_deltas,Bignum * numerator,Bignum * denominator,Bignum * delta_minus,Bignum * delta_plus)455 static void InitialScaledStartValuesNegativeExponentNegativePower(
456 double v, int estimated_power, bool need_boundary_deltas, Bignum* numerator,
457 Bignum* denominator, Bignum* delta_minus, Bignum* delta_plus) {
458 const uint64_t kMinimalNormalizedExponent = 0x0010'0000'0000'0000;
459 uint64_t significand = Double(v).Significand();
460 int exponent = Double(v).Exponent();
461 // Instead of multiplying the denominator with 10^estimated_power we
462 // multiply all values (numerator and deltas) by 10^-estimated_power.
463
464 // Use numerator as temporary container for power_ten.
465 Bignum* power_ten = numerator;
466 power_ten->AssignPowerUInt16(10, -estimated_power);
467
468 if (need_boundary_deltas) {
469 // Since power_ten == numerator we must make a copy of 10^estimated_power
470 // before we complete the computation of the numerator.
471 // delta_plus = delta_minus = 10^estimated_power
472 delta_plus->AssignBignum(*power_ten);
473 delta_minus->AssignBignum(*power_ten);
474 }
475
476 // numerator = significand * 2 * 10^-estimated_power
477 // since v = significand * 2^exponent this is equivalent to
478 // numerator = v * 10^-estimated_power * 2 * 2^-exponent.
479 // Remember: numerator has been abused as power_ten. So no need to assign it
480 // to itself.
481 DCHECK(numerator == power_ten);
482 numerator->MultiplyByUInt64(significand);
483
484 // denominator = 2 * 2^-exponent with exponent < 0.
485 denominator->AssignUInt16(1);
486 denominator->ShiftLeft(-exponent);
487
488 if (need_boundary_deltas) {
489 // Introduce a common denominator so that the deltas to the boundaries are
490 // integers.
491 numerator->ShiftLeft(1);
492 denominator->ShiftLeft(1);
493 // With this shift the boundaries have their correct value, since
494 // delta_plus = 10^-estimated_power, and
495 // delta_minus = 10^-estimated_power.
496 // These assignments have been done earlier.
497
498 // The special case where the lower boundary is twice as close.
499 // This time we have to look out for the exception too.
500 uint64_t v_bits = Double(v).AsUint64();
501 if ((v_bits & Double::kSignificandMask) == 0 &&
502 // The only exception where a significand == 0 has its boundaries at
503 // "normal" distances:
504 (v_bits & Double::kExponentMask) != kMinimalNormalizedExponent) {
505 numerator->ShiftLeft(1); // *2
506 denominator->ShiftLeft(1); // *2
507 delta_plus->ShiftLeft(1); // *2
508 }
509 }
510 }
511
512 // Let v = significand * 2^exponent.
513 // Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator
514 // and denominator. The functions GenerateShortestDigits and
515 // GenerateCountedDigits will then convert this ratio to its decimal
516 // representation d, with the required accuracy.
517 // Then d * 10^estimated_power is the representation of v.
518 // (Note: the fraction and the estimated_power might get adjusted before
519 // generating the decimal representation.)
520 //
521 // The initial start values consist of:
522 // - a scaled numerator: s.t. numerator/denominator == v / 10^estimated_power.
523 // - a scaled (common) denominator.
524 // optionally (used by GenerateShortestDigits to decide if it has the shortest
525 // decimal converting back to v):
526 // - v - m-: the distance to the lower boundary.
527 // - m+ - v: the distance to the upper boundary.
528 //
529 // v, m+, m-, and therefore v - m- and m+ - v all share the same denominator.
530 //
531 // Let ep == estimated_power, then the returned values will satisfy:
532 // v / 10^ep = numerator / denominator.
533 // v's boundarys m- and m+:
534 // m- / 10^ep == v / 10^ep - delta_minus / denominator
535 // m+ / 10^ep == v / 10^ep + delta_plus / denominator
536 // Or in other words:
537 // m- == v - delta_minus * 10^ep / denominator;
538 // m+ == v + delta_plus * 10^ep / denominator;
539 //
540 // Since 10^(k-1) <= v < 10^k (with k == estimated_power)
541 // or 10^k <= v < 10^(k+1)
542 // we then have 0.1 <= numerator/denominator < 1
543 // or 1 <= numerator/denominator < 10
544 //
545 // It is then easy to kickstart the digit-generation routine.
546 //
547 // The boundary-deltas are only filled if need_boundary_deltas is set.
InitialScaledStartValues(double v,int estimated_power,bool need_boundary_deltas,Bignum * numerator,Bignum * denominator,Bignum * delta_minus,Bignum * delta_plus)548 static void InitialScaledStartValues(double v, int estimated_power,
549 bool need_boundary_deltas,
550 Bignum* numerator, Bignum* denominator,
551 Bignum* delta_minus, Bignum* delta_plus) {
552 if (Double(v).Exponent() >= 0) {
553 InitialScaledStartValuesPositiveExponent(
554 v, estimated_power, need_boundary_deltas, numerator, denominator,
555 delta_minus, delta_plus);
556 } else if (estimated_power >= 0) {
557 InitialScaledStartValuesNegativeExponentPositivePower(
558 v, estimated_power, need_boundary_deltas, numerator, denominator,
559 delta_minus, delta_plus);
560 } else {
561 InitialScaledStartValuesNegativeExponentNegativePower(
562 v, estimated_power, need_boundary_deltas, numerator, denominator,
563 delta_minus, delta_plus);
564 }
565 }
566
567 // This routine multiplies numerator/denominator so that its values lies in the
568 // range 1-10. That is after a call to this function we have:
569 // 1 <= (numerator + delta_plus) /denominator < 10.
570 // Let numerator the input before modification and numerator' the argument
571 // after modification, then the output-parameter decimal_point is such that
572 // numerator / denominator * 10^estimated_power ==
573 // numerator' / denominator' * 10^(decimal_point - 1)
574 // In some cases estimated_power was too low, and this is already the case. We
575 // then simply adjust the power so that 10^(k-1) <= v < 10^k (with k ==
576 // estimated_power) but do not touch the numerator or denominator.
577 // Otherwise the routine multiplies the numerator and the deltas by 10.
FixupMultiply10(int estimated_power,bool is_even,int * decimal_point,Bignum * numerator,Bignum * denominator,Bignum * delta_minus,Bignum * delta_plus)578 static void FixupMultiply10(int estimated_power, bool is_even,
579 int* decimal_point, Bignum* numerator,
580 Bignum* denominator, Bignum* delta_minus,
581 Bignum* delta_plus) {
582 bool in_range;
583 if (is_even) {
584 // For IEEE doubles half-way cases (in decimal system numbers ending with 5)
585 // are rounded to the closest floating-point number with even significand.
586 in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0;
587 } else {
588 in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0;
589 }
590 if (in_range) {
591 // Since numerator + delta_plus >= denominator we already have
592 // 1 <= numerator/denominator < 10. Simply update the estimated_power.
593 *decimal_point = estimated_power + 1;
594 } else {
595 *decimal_point = estimated_power;
596 numerator->Times10();
597 if (Bignum::Equal(*delta_minus, *delta_plus)) {
598 delta_minus->Times10();
599 delta_plus->AssignBignum(*delta_minus);
600 } else {
601 delta_minus->Times10();
602 delta_plus->Times10();
603 }
604 }
605 }
606
607 } // namespace internal
608 } // namespace v8
609