1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Multiprecision decimal numbers. 6 // For floating-point formatting only; not general purpose. 7 // Only operations are assign and (binary) left/right shift. 8 // Can do binary floating point in multiprecision decimal precisely 9 // because 2 divides 10; cannot do decimal floating point 10 // in multiprecision binary precisely. 11 12 package decimal 13 14 type floatInfo struct { 15 mantbits uint 16 expbits uint 17 bias int 18 } 19 20 var float32info = floatInfo{23, 8, -127} 21 var float64info = floatInfo{52, 11, -1023} 22 23 // roundShortest rounds d (= mant * 2^exp) to the shortest number of digits 24 // that will let the original floating point value be precisely reconstructed. 25 func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) { 26 // If mantissa is zero, the number is zero; stop now. 27 if mant == 0 { 28 d.nd = 0 29 return 30 } 31 32 // Compute upper and lower such that any decimal number 33 // between upper and lower (possibly inclusive) 34 // will round to the original floating point number. 35 36 // We may see at once that the number is already shortest. 37 // 38 // Suppose d is not denormal, so that 2^exp <= d < 10^dp. 39 // The closest shorter number is at least 10^(dp-nd) away. 40 // The lower/upper bounds computed below are at distance 41 // at most 2^(exp-mantbits). 42 // 43 // So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits), 44 // or equivalently log2(10)*(dp-nd) > exp-mantbits. 45 // It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32). 46 minexp := flt.bias + 1 // minimum possible exponent 47 if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) { 48 // The number is already shortest. 49 return 50 } 51 52 // d = mant << (exp - mantbits) 53 // Next highest floating point number is mant+1 << exp-mantbits. 54 // Our upper bound is halfway between, mant*2+1 << exp-mantbits-1. 55 upper := new(decimal) 56 upper.Assign(mant*2 + 1) 57 upper.Shift(exp - int(flt.mantbits) - 1) 58 59 // d = mant << (exp - mantbits) 60 // Next lowest floating point number is mant-1 << exp-mantbits, 61 // unless mant-1 drops the significant bit and exp is not the minimum exp, 62 // in which case the next lowest is mant*2-1 << exp-mantbits-1. 63 // Either way, call it mantlo << explo-mantbits. 64 // Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1. 65 var mantlo uint64 66 var explo int 67 if mant > 1<<flt.mantbits || exp == minexp { 68 mantlo = mant - 1 69 explo = exp 70 } else { 71 mantlo = mant*2 - 1 72 explo = exp - 1 73 } 74 lower := new(decimal) 75 lower.Assign(mantlo*2 + 1) 76 lower.Shift(explo - int(flt.mantbits) - 1) 77 78 // The upper and lower bounds are possible outputs only if 79 // the original mantissa is even, so that IEEE round-to-even 80 // would round to the original mantissa and not the neighbors. 81 inclusive := mant%2 == 0 82 83 // As we walk the digits we want to know whether rounding up would fall 84 // within the upper bound. This is tracked by upperdelta: 85 // 86 // If upperdelta == 0, the digits of d and upper are the same so far. 87 // 88 // If upperdelta == 1, we saw a difference of 1 between d and upper on a 89 // previous digit and subsequently only 9s for d and 0s for upper. 90 // (Thus rounding up may fall outside the bound, if it is exclusive.) 91 // 92 // If upperdelta == 2, then the difference is greater than 1 93 // and we know that rounding up falls within the bound. 94 var upperdelta uint8 95 96 // Now we can figure out the minimum number of digits required. 97 // Walk along until d has distinguished itself from upper and lower. 98 for ui := 0; ; ui++ { 99 // lower, d, and upper may have the decimal points at different 100 // places. In this case upper is the longest, so we iterate from 101 // ui==0 and start li and mi at (possibly) -1. 102 mi := ui - upper.dp + d.dp 103 if mi >= d.nd { 104 break 105 } 106 li := ui - upper.dp + lower.dp 107 l := byte('0') // lower digit 108 if li >= 0 && li < lower.nd { 109 l = lower.d[li] 110 } 111 m := byte('0') // middle digit 112 if mi >= 0 { 113 m = d.d[mi] 114 } 115 u := byte('0') // upper digit 116 if ui < upper.nd { 117 u = upper.d[ui] 118 } 119 120 // Okay to round down (truncate) if lower has a different digit 121 // or if lower is inclusive and is exactly the result of rounding 122 // down (i.e., and we have reached the final digit of lower). 123 okdown := l != m || inclusive && li+1 == lower.nd 124 125 switch { 126 case upperdelta == 0 && m+1 < u: 127 // Example: 128 // m = 12345xxx 129 // u = 12347xxx 130 upperdelta = 2 131 case upperdelta == 0 && m != u: 132 // Example: 133 // m = 12345xxx 134 // u = 12346xxx 135 upperdelta = 1 136 case upperdelta == 1 && (m != '9' || u != '0'): 137 // Example: 138 // m = 1234598x 139 // u = 1234600x 140 upperdelta = 2 141 } 142 // Okay to round up if upper has a different digit and either upper 143 // is inclusive or upper is bigger than the result of rounding up. 144 okup := upperdelta > 0 && (inclusive || upperdelta > 1 || ui+1 < upper.nd) 145 146 // If it's okay to do either, then round to the nearest one. 147 // If it's okay to do only one, do it. 148 switch { 149 case okdown && okup: 150 d.Round(mi + 1) 151 return 152 case okdown: 153 d.RoundDown(mi + 1) 154 return 155 case okup: 156 d.RoundUp(mi + 1) 157 return 158 } 159 } 160 } 161