15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Copyright 2010 the V8 project authors. All rights reserved. 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Redistribution and use in source and binary forms, with or without 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// modification, are permitted provided that the following conditions are 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// met: 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Redistributions of source code must retain the above copyright 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// notice, this list of conditions and the following disclaimer. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Redistributions in binary form must reproduce the above 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// copyright notice, this list of conditions and the following 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// disclaimer in the documentation and/or other materials provided 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// contributors may be used to endorse or promote products derived 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// from this software without specific prior written permission. 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <math.h> 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "bignum-dtoa.h" 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "bignum.h" 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "double.h" 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace double_conversion { 40fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int NormalizedExponent(uint64_t significand, int exponent) { 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(significand != 0); 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while ((significand & Double::kHiddenBit) == 0) { 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) significand = significand << 1; 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent = exponent - 1; 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return exponent; 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 49fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 50fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Forward declarations: 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns an estimation of k such that 10^(k-1) <= v < 10^k. 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int EstimatePower(int exponent); 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and denominator. 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void InitialScaledStartValues(double v, 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int estimated_power, 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool need_boundary_deltas, 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* denominator, 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_plus); 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Multiplies numerator/denominator so that its values lies in the range 1-10. 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns decimal_point s.t. 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v = numerator'/denominator' * 10^(decimal_point-1) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // where numerator' and denominator' are the values of numerator and 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // denominator after the call to this function. 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void FixupMultiply10(int estimated_power, bool is_even, 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int* decimal_point, 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus); 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Generates digits from the left to the right and stops when the generated 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // digits yield the shortest decimal representation of v. 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator, 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus, 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool is_even, 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char> buffer, int* length); 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Generates 'requested_digits' after the decimal point. 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void BignumToFixed(int requested_digits, int* decimal_point, 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char>(buffer), int* length); 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Generates 'count' digits of numerator/denominator. 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Once 'count' digits have been produced rounds the result depending on the 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // remainder (remainders of exactly .5 round upwards). Might update the 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // decimal_point when rounding up (for example for 0.9999). 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void GenerateCountedDigits(int count, int* decimal_point, 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char>(buffer), int* length); 89fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 90fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits, 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char> buffer, int* length, int* decimal_point) { 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(v > 0); 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!Double(v).IsSpecial()); 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t significand = Double(v).Significand(); 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool is_even = (significand & 1) == 0; 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int exponent = Double(v).Exponent(); 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int normalized_exponent = NormalizedExponent(significand, exponent); 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // estimated_power might be too low by 1. 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int estimated_power = EstimatePower(normalized_exponent); 101fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Shortcut for Fixed. 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The requested digits correspond to the digits after the point. If the 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // number is much too small, then there is no need in trying to get any 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // digits. 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (mode == BIGNUM_DTOA_FIXED && -estimated_power - 1 > requested_digits) { 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[0] = '\0'; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *length = 0; 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Set decimal-point to -requested_digits. This is what Gay does. 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that it should not have any effect anyways since the string is 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // empty. 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *decimal_point = -requested_digits; 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 115fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum numerator; 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum denominator; 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum delta_minus; 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum delta_plus; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Make sure the bignum can grow large enough. The smallest double equals 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 4e-324. In this case the denominator needs fewer than 324*4 binary digits. 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The maximum double is 1.7976931348623157e308 which needs fewer than 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 308*4 binary digits. 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(Bignum::kMaxSignificantBits >= 324*4); 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST); 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) InitialScaledStartValues(v, estimated_power, need_boundary_deltas, 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &numerator, &denominator, 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &delta_minus, &delta_plus); 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We now have v = (numerator / denominator) * 10^estimated_power. 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) FixupMultiply10(estimated_power, is_even, decimal_point, 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &numerator, &denominator, 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &delta_minus, &delta_plus); 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We now have v = (numerator / denominator) * 10^(decimal_point-1), and 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1 <= (numerator + delta_plus) / denominator < 10 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) switch (mode) { 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case BIGNUM_DTOA_SHORTEST: 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) GenerateShortestDigits(&numerator, &denominator, 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &delta_minus, &delta_plus, 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) is_even, buffer, length); 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case BIGNUM_DTOA_FIXED: 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BignumToFixed(requested_digits, decimal_point, 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &numerator, &denominator, 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer, length); 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case BIGNUM_DTOA_PRECISION: 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) GenerateCountedDigits(requested_digits, decimal_point, 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) &numerator, &denominator, 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer, length); 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) break; 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) default: 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UNREACHABLE(); 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[*length] = '\0'; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 156fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 157fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The procedure starts generating digits from the left to the right and stops 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // when the generated digits yield the shortest decimal representation of v. A 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // decimal representation of v is a number lying closer to v than to any other 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // double, so it converts to v when read. 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This is true if d, the decimal representation, is between m- and m+, the 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // upper and lower boundaries. d must be strictly between them if !is_even. 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // m- := (numerator - delta_minus) / denominator 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // m+ := (numerator + delta_plus) / denominator 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Precondition: 0 <= (numerator+delta_plus) / denominator < 10. 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If 1 <= (numerator+delta_plus) / denominator < 10 then no leading 0 digit 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // will be produced. This should be the standard precondition. 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator, 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus, 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool is_even, 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char> buffer, int* length) { 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Small optimization: if delta_minus and delta_plus are the same just reuse 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // one of the two bignums. 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Bignum::Equal(*delta_minus, *delta_plus)) { 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus = delta_minus; 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *length = 0; 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (true) { 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint16_t digit; 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) digit = numerator->DivideModuloIntBignum(*denominator); 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(digit <= 9); // digit is a uint16_t and therefore always positive. 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // digit = numerator / denominator (integer division). 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = numerator % denominator. 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[(*length)++] = digit + '0'; 188fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Can we stop already? 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If the remainder of the division is less than the distance to the lower 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // boundary we can stop. In this case we simply round down (discarding the 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // remainder). 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Similarly we test if we can round up (using the upper boundary). 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool in_delta_room_minus; 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool in_delta_room_plus; 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (is_even) { 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) in_delta_room_minus = Bignum::LessEqual(*numerator, *delta_minus); 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) in_delta_room_minus = Bignum::Less(*numerator, *delta_minus); 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (is_even) { 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) in_delta_room_plus = 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0; 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) in_delta_room_plus = 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0; 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!in_delta_room_minus && !in_delta_room_plus) { 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Prepare for next iteration. 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->Times10(); 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->Times10(); 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We optimized delta_plus to be equal to delta_minus (if they share the 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // same value). So don't multiply delta_plus if they point to the same 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // object. 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (delta_minus != delta_plus) { 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->Times10(); 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (in_delta_room_minus && in_delta_room_plus) { 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let's see if 2*numerator < denominator. 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If yes, then the next digit would be < 5 and we can round down. 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int compare = Bignum::PlusCompare(*numerator, *numerator, *denominator); 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (compare < 0) { 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Remaining digits are less than .5. -> Round down (== do nothing). 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (compare > 0) { 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Remaining digits are more than .5 of denominator. -> Round up. 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that the last digit could not be a '9' as otherwise the whole 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // loop would have stopped earlier. 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We still have an assert here in case the preconditions were not 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // satisfied. 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(buffer[(*length) - 1] != '9'); 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[(*length) - 1]++; 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Halfway case. 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // TODO(floitsch): need a way to solve half-way cases. 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // For now let's round towards even (since this is what Gay seems to 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // do). 237fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((buffer[(*length) - 1] - '0') % 2 == 0) { 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Round down => Do nothing. 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(buffer[(*length) - 1] != '9'); 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[(*length) - 1]++; 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (in_delta_room_minus) { 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Round down (== do nothing). 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { // in_delta_room_plus 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Round up. 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note again that the last digit could not be '9' since this would have 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // stopped the loop earlier. 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We still have an ASSERT here, in case the preconditions were not 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // satisfied. 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(buffer[(*length) -1] != '9'); 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[(*length) - 1]++; 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 261fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 262fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let v = numerator / denominator < 10. 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Then we generate 'count' digits of d = x.xxxxx... (without the decimal point) 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // from left to right. Once 'count' digits have been produced we decide wether 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // to round up or down. Remainders of exactly .5 round upwards. Numbers such 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // as 9.999999 propagate a carry all the way, and change the 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // exponent (decimal_point), when rounding upwards. 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void GenerateCountedDigits(int count, int* decimal_point, 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char>(buffer), int* length) { 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(count >= 0); 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < count - 1; ++i) { 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint16_t digit; 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) digit = numerator->DivideModuloIntBignum(*denominator); 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(digit <= 9); // digit is a uint16_t and therefore always positive. 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // digit = numerator / denominator (integer division). 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = numerator % denominator. 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[i] = digit + '0'; 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Prepare for next iteration. 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->Times10(); 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Generate the last digit. 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint16_t digit; 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) digit = numerator->DivideModuloIntBignum(*denominator); 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) digit++; 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[count - 1] = digit + '0'; 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Correct bad digits (in case we had a sequence of '9's). Propagate the 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // carry until we hat a non-'9' or til we reach the first digit. 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = count - 1; i > 0; --i) { 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (buffer[i] != '0' + 10) break; 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[i] = '0'; 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[i - 1]++; 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (buffer[0] == '0' + 10) { 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Propagate a carry past the top place. 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[0] = '1'; 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) (*decimal_point)++; 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *length = count; 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 304fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 305fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Generates 'requested_digits' after the decimal point. It might omit 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // trailing '0's. If the input number is too small then no digits at all are 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // generated (ex.: 2 fixed digits for 0.00001). 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Input verifies: 1 <= (numerator + delta) / denominator < 10. 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void BignumToFixed(int requested_digits, int* decimal_point, 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<char>(buffer), int* length) { 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that we have to look at more than just the requested_digits, since 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // a number could be rounded up. Example: v=0.5 with requested_digits=0. 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Even though the power of v equals 0 we can't just stop here. 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (-(*decimal_point) > requested_digits) { 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The number is definitively too small. 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Ex: 0.001 with requested_digits == 1. 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Set decimal-point to -requested_digits. This is what Gay does. 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that it should not have any effect anyways since the string is 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // empty. 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *decimal_point = -requested_digits; 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *length = 0; 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (-(*decimal_point) == requested_digits) { 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We only need to verify if the number rounds down or up. 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Ex: 0.04 and 0.06 with requested_digits == 1. 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(*decimal_point == -requested_digits); 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Initially the fraction lies in range (1, 10]. Multiply the denominator 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // by 10 so that we can compare more easily. 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->Times10(); 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If the fraction is >= 0.5 then we have to include the rounded 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // digit. 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[0] = '1'; 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *length = 1; 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) (*decimal_point)++; 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that we caught most of similar cases earlier. 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *length = 0; 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The requested digits correspond to the digits after the point. 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The variable 'needed_digits' includes the digits before the point. 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int needed_digits = (*decimal_point) + requested_digits; 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) GenerateCountedDigits(needed_digits, decimal_point, 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator, denominator, 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer, length); 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 353fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 354fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns an estimation of k such that 10^(k-1) <= v < 10^k where 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v = f * 2^exponent and 2^52 <= f < 2^53. 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v is hence a normalized double with the given exponent. The output is an 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // approximation for the exponent of the decimal approimation .digits * 10^k. 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The result might undershoot by 1 in which case 10^k <= v < 10^k+1. 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note: this property holds for v's upper boundary m+ too. 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 10^k <= m+ < 10^k+1. 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // (see explanation below). 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Examples: 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // EstimatePower(0) => 16 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // EstimatePower(-52) => 0 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note: e >= 0 => EstimatedPower(e) > 0. No similar claim can be made for e<0. 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int EstimatePower(int exponent) { 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This function estimates log10 of v where v = f*2^e (with e == exponent). 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that 10^floor(log10(v)) <= v, but v <= 10^ceil(log10(v)). 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note that f is bounded by its container size. Let p = 53 (the double's 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // significand size). Then 2^(p-1) <= f < 2^p. 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Given that log10(v) == log2(v)/log2(10) and e+(len(f)-1) is quite close 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // to log2(v) the function is simplified to (e+(len(f)-1)/log2(10)). 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The computed number undershoots by less than 0.631 (when we compute log3 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and not log10). 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Optimization: since we only need an approximated result this computation 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // can be performed on 64 bit integers. On x86/x64 architecture the speedup is 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // not really measurable, though. 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since we want to avoid overshooting we decrement by 1e10 so that 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // floating-point imprecisions don't affect us. 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Explanation for v's boundary m+: the computation takes advantage of 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the fact that 2^(p-1) <= f < 2^p. Boundaries still satisfy this requirement 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // (even for denormals where the delta can be much more important). 391fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const double k1Log10 = 0.30102999566398114; // 1/lg(10) 393fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // For doubles len(f) == 53 (don't forget the hidden bit). 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const int kSignificandSize = 53; 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double estimate = ceil((exponent + kSignificandSize - 1) * k1Log10 - 1e-10); 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return static_cast<int>(estimate); 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 399fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 400fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // See comments for InitialScaledStartValues. 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void InitialScaledStartValuesPositiveExponent( 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double v, int estimated_power, bool need_boundary_deltas, 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus) { 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // A positive exponent implies a positive power. 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(estimated_power >= 0); 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since the estimated_power is positive we simply multiply the denominator 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // by 10^estimated_power. 410fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = v. 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->AssignUInt64(Double(v).Significand()); 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(Double(v).Exponent()); 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // denominator = 10^estimated_power. 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->AssignPowerUInt16(10, estimated_power); 416fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (need_boundary_deltas) { 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Introduce a common denominator so that the deltas to the boundaries are 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // integers. 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(1); 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(1); 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // denominator (of 2) delta_plus equals 2^e. 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->AssignUInt16(1); 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->ShiftLeft(Double(v).Exponent()); 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Same for delta_minus (with adjustments below if f == 2^p-1). 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->AssignUInt16(1); 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->ShiftLeft(Double(v).Exponent()); 429fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If the significand (without the hidden bit) is 0, then the lower 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // boundary is closer than just half a ulp (unit in the last place). 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // There is only one exception: if the next lower number is a denormal then 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the distance is 1 ulp. This cannot be the case for exponent >= 0 (but we 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // have to test it in the other function where exponent < 0). 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t v_bits = Double(v).AsUint64(); 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((v_bits & Double::kSignificandMask) == 0) { 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The lower boundary is closer at half the distance of "normal" numbers. 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Increase the common denominator and adapt all but the delta_minus. 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(1); // *2 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(1); // *2 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->ShiftLeft(1); // *2 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 445fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 446fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // See comments for InitialScaledStartValues 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void InitialScaledStartValuesNegativeExponentPositivePower( 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double v, int estimated_power, bool need_boundary_deltas, 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus) { 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t significand = Double(v).Significand(); 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int exponent = Double(v).Exponent(); 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v = f * 2^e with e < 0, and with estimated_power >= 0. 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This means that e is close to 0 (have a look at how estimated_power is 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // computed). 457fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = significand 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // since v = significand * 2^exponent this is equivalent to 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = v * / 2^-exponent 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->AssignUInt64(significand); 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // denominator = 10^estimated_power * 2^-exponent (with exponent < 0) 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->AssignPowerUInt16(10, estimated_power); 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(-exponent); 465fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (need_boundary_deltas) { 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Introduce a common denominator so that the deltas to the boundaries are 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // integers. 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(1); 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(1); 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // denominator (of 2) delta_plus equals 2^e. 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Given that the denominator already includes v's exponent the distance 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // to the boundaries is simply 1. 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->AssignUInt16(1); 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Same for delta_minus (with adjustments below if f == 2^p-1). 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->AssignUInt16(1); 478fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If the significand (without the hidden bit) is 0, then the lower 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // boundary is closer than just one ulp (unit in the last place). 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // There is only one exception: if the next lower number is a denormal 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // then the distance is 1 ulp. Since the exponent is close to zero 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // (otherwise estimated_power would have been negative) this cannot happen 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // here either. 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t v_bits = Double(v).AsUint64(); 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((v_bits & Double::kSignificandMask) == 0) { 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The lower boundary is closer at half the distance of "normal" numbers. 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Increase the denominator and adapt all but the delta_minus. 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(1); // *2 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(1); // *2 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->ShiftLeft(1); // *2 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 495fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 496fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // See comments for InitialScaledStartValues 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void InitialScaledStartValuesNegativeExponentNegativePower( 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) double v, int estimated_power, bool need_boundary_deltas, 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus) { 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint64_t kMinimalNormalizedExponent = 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UINT64_2PART_C(0x00100000, 00000000); 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t significand = Double(v).Significand(); 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int exponent = Double(v).Exponent(); 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Instead of multiplying the denominator with 10^estimated_power we 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // multiply all values (numerator and deltas) by 10^-estimated_power. 508fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Use numerator as temporary container for power_ten. 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* power_ten = numerator; 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) power_ten->AssignPowerUInt16(10, -estimated_power); 512fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (need_boundary_deltas) { 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since power_ten == numerator we must make a copy of 10^estimated_power 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // before we complete the computation of the numerator. 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // delta_plus = delta_minus = 10^estimated_power 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->AssignBignum(*power_ten); 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->AssignBignum(*power_ten); 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 520fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = significand * 2 * 10^-estimated_power 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // since v = significand * 2^exponent this is equivalent to 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator = v * 10^-estimated_power * 2 * 2^-exponent. 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Remember: numerator has been abused as power_ten. So no need to assign it 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // to itself. 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(numerator == power_ten); 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->MultiplyByUInt64(significand); 528fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // denominator = 2 * 2^-exponent with exponent < 0. 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->AssignUInt16(1); 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(-exponent); 532fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (need_boundary_deltas) { 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Introduce a common denominator so that the deltas to the boundaries are 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // integers. 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(1); 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(1); 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // With this shift the boundaries have their correct value, since 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // delta_plus = 10^-estimated_power, and 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // delta_minus = 10^-estimated_power. 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These assignments have been done earlier. 542fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The special case where the lower boundary is twice as close. 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This time we have to look out for the exception too. 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t v_bits = Double(v).AsUint64(); 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((v_bits & Double::kSignificandMask) == 0 && 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The only exception where a significand == 0 has its boundaries at 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // "normal" distances: 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) (v_bits & Double::kExponentMask) != kMinimalNormalizedExponent) { 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->ShiftLeft(1); // *2 5515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) denominator->ShiftLeft(1); // *2 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->ShiftLeft(1); // *2 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 556fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 557fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let v = significand * 2^exponent. 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and denominator. The functions GenerateShortestDigits and 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // GenerateCountedDigits will then convert this ratio to its decimal 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // representation d, with the required accuracy. 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Then d * 10^estimated_power is the representation of v. 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // (Note: the fraction and the estimated_power might get adjusted before 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // generating the decimal representation.) 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The initial start values consist of: 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // - a scaled numerator: s.t. numerator/denominator == v / 10^estimated_power. 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // - a scaled (common) denominator. 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // optionally (used by GenerateShortestDigits to decide if it has the shortest 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // decimal converting back to v): 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // - v - m-: the distance to the lower boundary. 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // - m+ - v: the distance to the upper boundary. 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v, m+, m-, and therefore v - m- and m+ - v all share the same denominator. 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let ep == estimated_power, then the returned values will satisfy: 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v / 10^ep = numerator / denominator. 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // v's boundarys m- and m+: 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // m- / 10^ep == v / 10^ep - delta_minus / denominator 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // m+ / 10^ep == v / 10^ep + delta_plus / denominator 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Or in other words: 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // m- == v - delta_minus * 10^ep / denominator; 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // m+ == v + delta_plus * 10^ep / denominator; 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since 10^(k-1) <= v < 10^k (with k == estimated_power) 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // or 10^k <= v < 10^(k+1) 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // we then have 0.1 <= numerator/denominator < 1 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // or 1 <= numerator/denominator < 10 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // It is then easy to kickstart the digit-generation routine. 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The boundary-deltas are only filled if need_boundary_deltas is set. 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void InitialScaledStartValues(double v, 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int estimated_power, 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool need_boundary_deltas, 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* denominator, 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_plus) { 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Double(v).Exponent() >= 0) { 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) InitialScaledStartValuesPositiveExponent( 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) v, estimated_power, need_boundary_deltas, 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator, denominator, delta_minus, delta_plus); 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else if (estimated_power >= 0) { 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) InitialScaledStartValuesNegativeExponentPositivePower( 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) v, estimated_power, need_boundary_deltas, 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator, denominator, delta_minus, delta_plus); 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) InitialScaledStartValuesNegativeExponentNegativePower( 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) v, estimated_power, need_boundary_deltas, 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator, denominator, delta_minus, delta_plus); 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 615fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 616fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This routine multiplies numerator/denominator so that its values lies in the 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // range 1-10. That is after a call to this function we have: 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1 <= (numerator + delta_plus) /denominator < 10. 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let numerator the input before modification and numerator' the argument 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // after modification, then the output-parameter decimal_point is such that 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator / denominator * 10^estimated_power == 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // numerator' / denominator' * 10^(decimal_point - 1) 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // In some cases estimated_power was too low, and this is already the case. We 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // then simply adjust the power so that 10^(k-1) <= v < 10^k (with k == 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // estimated_power) but do not touch the numerator or denominator. 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Otherwise the routine multiplies the numerator and the deltas by 10. 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static void FixupMultiply10(int estimated_power, bool is_even, 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int* decimal_point, 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* numerator, Bignum* denominator, 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum* delta_minus, Bignum* delta_plus) { 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool in_range; 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (is_even) { 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // For IEEE doubles half-way cases (in decimal system numbers ending with 5) 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // are rounded to the closest floating-point number with even significand. 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0; 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0; 6395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (in_range) { 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since numerator + delta_plus >= denominator we already have 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1 <= numerator/denominator < 10. Simply update the estimated_power. 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *decimal_point = estimated_power + 1; 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *decimal_point = estimated_power; 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) numerator->Times10(); 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Bignum::Equal(*delta_minus, *delta_plus)) { 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->Times10(); 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->AssignBignum(*delta_minus); 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_minus->Times10(); 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delta_plus->Times10(); 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 656fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace double_conversion 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 660