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 12package decimal 13 14type floatInfo struct { 15 mantbits uint 16 expbits uint 17 bias int 18} 19 20var float32info = floatInfo{23, 8, -127} 21var 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. 25func 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 // Now we can figure out the minimum number of digits required. 84 // Walk along until d has distinguished itself from upper and lower. 85 for i := 0; i < d.nd; i++ { 86 l := byte('0') // lower digit 87 if i < lower.nd { 88 l = lower.d[i] 89 } 90 m := d.d[i] // middle digit 91 u := byte('0') // upper digit 92 if i < upper.nd { 93 u = upper.d[i] 94 } 95 96 // Okay to round down (truncate) if lower has a different digit 97 // or if lower is inclusive and is exactly the result of rounding 98 // down (i.e., and we have reached the final digit of lower). 99 okdown := l != m || inclusive && i+1 == lower.nd 100 101 // Okay to round up if upper has a different digit and either upper 102 // is inclusive or upper is bigger than the result of rounding up. 103 okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd) 104 105 // If it's okay to do either, then round to the nearest one. 106 // If it's okay to do only one, do it. 107 switch { 108 case okdown && okup: 109 d.Round(i + 1) 110 return 111 case okdown: 112 d.RoundDown(i + 1) 113 return 114 case okup: 115 d.RoundUp(i + 1) 116 return 117 } 118 } 119} 120