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
20package 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.
27type 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.
33func (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.
42const 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).
55func (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).shr(m, s)
73		shift += int(s)
74	}
75
76	// Do any shift left in binary representation.
77	if shift > 0 {
78		m = nat(nil).shl(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			shr(x, maxShift)
97			shift += maxShift
98		}
99		shr(x, uint(-shift))
100	}
101}
102
103// shr implements x >> s, for s <= maxShift.
104func shr(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
160func (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 = make([]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 = make([]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 = make([]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.
192func 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.
202func 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.
214func (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
226func (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
251func (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.
261func 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