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