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