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