1 // Copyright 2015 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 // This file implements multi-precision decimal numbers.
6 // The implementation is for float to decimal conversion only;
7 // not general purpose use.
8 // The only operations are precise conversion from binary to
9 // decimal and rounding.
10 //
11 // The key observation and some code (shr) is borrowed from
12 // strconv/decimal.go: conversion of binary fractional values can be done
13 // precisely in multi-precision decimal because 2 divides 10 (required for
14 // >> of mantissa); but conversion of decimal floating-point values cannot
15 // be done precisely in binary representation.
16 //
17 // In contrast to strconv/decimal.go, only right shift is implemented in
18 // decimal format - left shift can be done precisely in binary format.
19 20 package big
21 22 // A decimal represents an unsigned floating-point number in decimal representation.
23 // The value of a non-zero decimal d is d.mant * 10**d.exp with 0.1 <= d.mant < 1,
24 // with the most-significant mantissa digit at index 0. For the zero decimal, the
25 // mantissa length and exponent are 0.
26 // The zero value for decimal represents a ready-to-use 0.0.
27 type decimal struct {
28 mant []byte // mantissa ASCII digits, big-endian
29 exp int // exponent
30 }
31 32 // at returns the i'th mantissa digit, starting with the most significant digit at 0.
33 func (d *decimal) at(i int) byte {
34 if 0 <= i && i < len(d.mant) {
35 return d.mant[i]
36 }
37 return '0'
38 }
39 40 // Maximum shift amount that can be done in one pass without overflow.
41 // A Word has _W bits and (1<<maxShift - 1)*10 + 9 must fit into Word.
42 const maxShift = _W - 4
43 44 // TODO(gri) Since we know the desired decimal precision when converting
45 // a floating-point number, we may be able to limit the number of decimal
46 // digits that need to be computed by init by providing an additional
47 // precision argument and keeping track of when a number was truncated early
48 // (equivalent of "sticky bit" in binary rounding).
49 50 // TODO(gri) Along the same lines, enforce some limit to shift magnitudes
51 // to avoid "infinitely" long running conversions (until we run out of space).
52 53 // Init initializes x to the decimal representation of m << shift (for
54 // shift >= 0), or m >> -shift (for shift < 0).
55 func (x *decimal) init(m nat, shift int) {
56 // special case 0
57 if len(m) == 0 {
58 x.mant = x.mant[:0]
59 x.exp = 0
60 return
61 }
62 63 // Optimization: If we need to shift right, first remove any trailing
64 // zero bits from m to reduce shift amount that needs to be done in
65 // decimal format (since that is likely slower).
66 if shift < 0 {
67 ntz := m.trailingZeroBits()
68 s := uint(-shift)
69 if s >= ntz {
70 s = ntz // shift at most ntz bits
71 }
72 m = nat(nil).rsh(m, s)
73 shift += int(s)
74 }
75 76 // Do any shift left in binary representation.
77 if shift > 0 {
78 m = nat(nil).lsh(m, uint(shift))
79 shift = 0
80 }
81 82 // Convert mantissa into decimal representation.
83 s := m.utoa(10)
84 n := len(s)
85 x.exp = n
86 // Trim trailing zeros; instead the exponent is tracking
87 // the decimal point independent of the number of digits.
88 for n > 0 && s[n-1] == '0' {
89 n--
90 }
91 x.mant = append(x.mant[:0], s[:n]...)
92 93 // Do any (remaining) shift right in decimal representation.
94 if shift < 0 {
95 for shift < -maxShift {
96 rsh(x, maxShift)
97 shift += maxShift
98 }
99 rsh(x, uint(-shift))
100 }
101 }
102 103 // rsh implements x >> s, for s <= maxShift.
104 func rsh(x *decimal, s uint) {
105 // Division by 1<<s using shift-and-subtract algorithm.
106 107 // pick up enough leading digits to cover first shift
108 r := 0 // read index
109 var n Word
110 for n>>s == 0 && r < len(x.mant) {
111 ch := Word(x.mant[r])
112 r++
113 n = n*10 + ch - '0'
114 }
115 if n == 0 {
116 // x == 0; shouldn't get here, but handle anyway
117 x.mant = x.mant[:0]
118 return
119 }
120 for n>>s == 0 {
121 r++
122 n *= 10
123 }
124 x.exp += 1 - r
125 126 // read a digit, write a digit
127 w := 0 // write index
128 mask := Word(1)<<s - 1
129 for r < len(x.mant) {
130 ch := Word(x.mant[r])
131 r++
132 d := n >> s
133 n &= mask // n -= d << s
134 x.mant[w] = byte(d + '0')
135 w++
136 n = n*10 + ch - '0'
137 }
138 139 // write extra digits that still fit
140 for n > 0 && w < len(x.mant) {
141 d := n >> s
142 n &= mask
143 x.mant[w] = byte(d + '0')
144 w++
145 n = n * 10
146 }
147 x.mant = x.mant[:w] // the number may be shorter (e.g. 1024 >> 10)
148 149 // append additional digits that didn't fit
150 for n > 0 {
151 d := n >> s
152 n &= mask
153 x.mant = append(x.mant, byte(d+'0'))
154 n = n * 10
155 }
156 157 trim(x)
158 }
159 160 func (x *decimal) String() string {
161 if len(x.mant) == 0 {
162 return "0"
163 }
164 165 var buf []byte
166 switch {
167 case x.exp <= 0:
168 // 0.00ddd
169 buf = []byte{:0:2+(-x.exp)+len(x.mant)}
170 buf = append(buf, "0."...)
171 buf = appendZeros(buf, -x.exp)
172 buf = append(buf, x.mant...)
173 174 case /* 0 < */ x.exp < len(x.mant):
175 // dd.ddd
176 buf = []byte{:0:1+len(x.mant)}
177 buf = append(buf, x.mant[:x.exp]...)
178 buf = append(buf, '.')
179 buf = append(buf, x.mant[x.exp:]...)
180 181 default: // len(x.mant) <= x.exp
182 // ddd00
183 buf = []byte{:0:x.exp}
184 buf = append(buf, x.mant...)
185 buf = appendZeros(buf, x.exp-len(x.mant))
186 }
187 188 return string(buf)
189 }
190 191 // appendZeros appends n 0 digits to buf and returns buf.
192 func appendZeros(buf []byte, n int) []byte {
193 for ; n > 0; n-- {
194 buf = append(buf, '0')
195 }
196 return buf
197 }
198 199 // shouldRoundUp reports if x should be rounded up
200 // if shortened to n digits. n must be a valid index
201 // for x.mant.
202 func shouldRoundUp(x *decimal, n int) bool {
203 if x.mant[n] == '5' && n+1 == len(x.mant) {
204 // exactly halfway - round to even
205 return n > 0 && (x.mant[n-1]-'0')&1 != 0
206 }
207 // not halfway - digit tells all (x.mant has no trailing zeros)
208 return x.mant[n] >= '5'
209 }
210 211 // round sets x to (at most) n mantissa digits by rounding it
212 // to the nearest even value with n (or fever) mantissa digits.
213 // If n < 0, x remains unchanged.
214 func (x *decimal) round(n int) {
215 if n < 0 || n >= len(x.mant) {
216 return // nothing to do
217 }
218 219 if shouldRoundUp(x, n) {
220 x.roundUp(n)
221 } else {
222 x.roundDown(n)
223 }
224 }
225 226 func (x *decimal) roundUp(n int) {
227 if n < 0 || n >= len(x.mant) {
228 return // nothing to do
229 }
230 // 0 <= n < len(x.mant)
231 232 // find first digit < '9'
233 for n > 0 && x.mant[n-1] >= '9' {
234 n--
235 }
236 237 if n == 0 {
238 // all digits are '9's => round up to '1' and update exponent
239 x.mant[0] = '1' // ok since len(x.mant) > n
240 x.mant = x.mant[:1]
241 x.exp++
242 return
243 }
244 245 // n > 0 && x.mant[n-1] < '9'
246 x.mant[n-1]++
247 x.mant = x.mant[:n]
248 // x already trimmed
249 }
250 251 func (x *decimal) roundDown(n int) {
252 if n < 0 || n >= len(x.mant) {
253 return // nothing to do
254 }
255 x.mant = x.mant[:n]
256 trim(x)
257 }
258 259 // trim cuts off any trailing zeros from x's mantissa;
260 // they are meaningless for the value of x.
261 func trim(x *decimal) {
262 i := len(x.mant)
263 for i > 0 && x.mant[i-1] == '0' {
264 i--
265 }
266 x.mant = x.mant[:i]
267 if i == 0 {
268 x.exp = 0
269 }
270 }
271