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 = append(buf, "0."...) 170 buf = appendZeros(buf, -x.exp) 171 buf = append(buf, x.mant...) 172 173 case /* 0 < */ x.exp < len(x.mant): 174 // dd.ddd 175 buf = append(buf, x.mant[:x.exp]...) 176 buf = append(buf, '.') 177 buf = append(buf, x.mant[x.exp:]...) 178 179 default: // len(x.mant) <= x.exp 180 // ddd00 181 buf = append(buf, x.mant...) 182 buf = appendZeros(buf, x.exp-len(x.mant)) 183 } 184 185 return string(buf) 186 } 187 188 // appendZeros appends n 0 digits to buf and returns buf. 189 func appendZeros(buf []byte, n int) []byte { 190 for ; n > 0; n-- { 191 buf = append(buf, '0') 192 } 193 return buf 194 } 195 196 // shouldRoundUp reports if x should be rounded up 197 // if shortened to n digits. n must be a valid index 198 // for x.mant. 199 func shouldRoundUp(x *decimal, n int) bool { 200 if x.mant[n] == '5' && n+1 == len(x.mant) { 201 // exactly halfway - round to even 202 return n > 0 && (x.mant[n-1]-'0')&1 != 0 203 } 204 // not halfway - digit tells all (x.mant has no trailing zeros) 205 return x.mant[n] >= '5' 206 } 207 208 // round sets x to (at most) n mantissa digits by rounding it 209 // to the nearest even value with n (or fever) mantissa digits. 210 // If n < 0, x remains unchanged. 211 func (x *decimal) round(n int) { 212 if n < 0 || n >= len(x.mant) { 213 return // nothing to do 214 } 215 216 if shouldRoundUp(x, n) { 217 x.roundUp(n) 218 } else { 219 x.roundDown(n) 220 } 221 } 222 223 func (x *decimal) roundUp(n int) { 224 if n < 0 || n >= len(x.mant) { 225 return // nothing to do 226 } 227 // 0 <= n < len(x.mant) 228 229 // find first digit < '9' 230 for n > 0 && x.mant[n-1] >= '9' { 231 n-- 232 } 233 234 if n == 0 { 235 // all digits are '9's => round up to '1' and update exponent 236 x.mant[0] = '1' // ok since len(x.mant) > n 237 x.mant = x.mant[:1] 238 x.exp++ 239 return 240 } 241 242 // n > 0 && x.mant[n-1] < '9' 243 x.mant[n-1]++ 244 x.mant = x.mant[:n] 245 // x already trimmed 246 } 247 248 func (x *decimal) roundDown(n int) { 249 if n < 0 || n >= len(x.mant) { 250 return // nothing to do 251 } 252 x.mant = x.mant[:n] 253 trim(x) 254 } 255 256 // trim cuts off any trailing zeros from x's mantissa; 257 // they are meaningless for the value of x. 258 func trim(x *decimal) { 259 i := len(x.mant) 260 for i > 0 && x.mant[i-1] == '0' { 261 i-- 262 } 263 x.mant = x.mant[:i] 264 if i == 0 { 265 x.exp = 0 266 } 267 } 268