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).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. 104 func 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 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 = 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. 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