libgo/go/strconv/decimal.go

   1 // Copyright 2009 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 // Multiprecision decimal numbers.
   6 // For floating-point formatting only; not general purpose.
   7 // Only operations are assign and (binary) left/right shift.
   8 // Can do binary floating point in multiprecision decimal precisely
   9 // because 2 divides 10; cannot do decimal floating point
  10 // in multiprecision binary precisely.
  11
  12 package strconv
  13
  14 type decimal struct {
  15         d     [800]byte // digits
  16         nd    int       // number of digits used
  17         dp    int       // decimal point
  18         neg   bool
  19         trunc bool // discarded nonzero digits beyond d[:nd]
  20 }
  21
  22 func (a *decimal) String() string {
  23         n := 10 + a.nd
  24         if a.dp > 0 {
  25                 n += a.dp
  26         }
  27         if a.dp < 0 {
  28                 n += -a.dp
  29         }
  30
  31         buf := make([]byte, n)
  32         w := 0
  33         switch {
  34         case a.nd == 0:
  35                 return "0"
  36
  37         case a.dp <= 0:
  38                 // zeros fill space between decimal point and digits
  39                 buf[w] = '0'
  40                 w++
  41                 buf[w] = '.'
  42                 w++
  43                 w += digitZero(buf[w : w+-a.dp])
  44                 w += copy(buf[w:], a.d[0:a.nd])
  45
  46         case a.dp < a.nd:
  47                 // decimal point in middle of digits
  48                 w += copy(buf[w:], a.d[0:a.dp])
  49                 buf[w] = '.'
  50                 w++
  51                 w += copy(buf[w:], a.d[a.dp:a.nd])
  52
  53         default:
  54                 // zeros fill space between digits and decimal point
  55                 w += copy(buf[w:], a.d[0:a.nd])
  56                 w += digitZero(buf[w : w+a.dp-a.nd])
  57         }
  58         return string(buf[0:w])
  59 }
  60
  61 func digitZero(dst []byte) int {
  62         for i := range dst {
  63                 dst[i] = '0'
  64         }
  65         return len(dst)
  66 }
  67
  68 // trim trailing zeros from number.
  69 // (They are meaningless; the decimal point is tracked
  70 // independent of the number of digits.)
  71 func trim(a *decimal) {
  72         for a.nd > 0 && a.d[a.nd-1] == '0' {
  73                 a.nd--
  74         }
  75         if a.nd == 0 {
  76                 a.dp = 0
  77         }
  78 }
  79
  80 // Assign v to a.
  81 func (a *decimal) Assign(v uint64) {
  82         var buf [24]byte
  83
  84         // Write reversed decimal in buf.
  85         n := 0
  86         for v > 0 {
  87                 v1 := v / 10
  88                 v -= 10 * v1
  89                 buf[n] = byte(v + '0')
  90                 n++
  91                 v = v1
  92         }
  93
  94         // Reverse again to produce forward decimal in a.d.
  95         a.nd = 0
  96         for n--; n >= 0; n-- {
  97                 a.d[a.nd] = buf[n]
  98                 a.nd++
  99         }
 100         a.dp = a.nd
 101         trim(a)
 102 }
 103
 104 // Maximum shift that we can do in one pass without overflow.
 105 // Signed int has 31 bits, and we have to be able to accommodate 9<<k.
 106 const maxShift = 27
 107
 108 // Binary shift right (* 2) by k bits.  k <= maxShift to avoid overflow.
 109 func rightShift(a *decimal, k uint) {
 110         r := 0 // read pointer
 111         w := 0 // write pointer
 112
 113         // Pick up enough leading digits to cover first shift.
 114         n := 0
 115         for ; n>>k == 0; r++ {
 116                 if r >= a.nd {
 117                         if n == 0 {
 118                                 // a == 0; shouldn't get here, but handle anyway.
 119                                 a.nd = 0
 120                                 return
 121                         }
 122                         for n>>k == 0 {
 123                                 n = n * 10
 124                                 r++
 125                         }
 126                         break
 127                 }
 128                 c := int(a.d[r])
 129                 n = n*10 + c - '0'
 130         }
 131         a.dp -= r - 1
 132
 133         // Pick up a digit, put down a digit.
 134         for ; r < a.nd; r++ {
 135                 c := int(a.d[r])
 136                 dig := n >> k
 137                 n -= dig << k
 138                 a.d[w] = byte(dig + '0')
 139                 w++
 140                 n = n*10 + c - '0'
 141         }
 142
 143         // Put down extra digits.
 144         for n > 0 {
 145                 dig := n >> k
 146                 n -= dig << k
 147                 if w < len(a.d) {
 148                         a.d[w] = byte(dig + '0')
 149                         w++
 150                 } else if dig > 0 {
 151                         a.trunc = true
 152                 }
 153                 n = n * 10
 154         }
 155
 156         a.nd = w
 157         trim(a)
 158 }
 159
 160 // Cheat sheet for left shift: table indexed by shift count giving
 161 // number of new digits that will be introduced by that shift.
 162 //
 163 // For example, leftcheats[4] = {2, "625"}.  That means that
 164 // if we are shifting by 4 (multiplying by 16), it will add 2 digits
 165 // when the string prefix is "625" through "999", and one fewer digit
 166 // if the string prefix is "000" through "624".
 167 //
 168 // Credit for this trick goes to Ken.
 169
 170 type leftCheat struct {
 171         delta  int    // number of new digits
 172         cutoff string //   minus one digit if original < a.
 173 }
 174
 175 var leftcheats = []leftCheat{
 176         // Leading digits of 1/2^i = 5^i.
 177         // 5^23 is not an exact 64-bit floating point number,
 178         // so have to use bc for the math.
 179         /*
 180                 seq 27 | sed 's/^/5^/' | bc |
 181                 awk 'BEGIN{ print "\tleftCheat{ 0, \"\" }," }
 182                 {
 183                         log2 = log(2)/log(10)
 184                         printf("\tleftCheat{ %d, \"%s\" },\t// * %d\n",
 185                                 int(log2*NR+1), $0, 2**NR)
 186                 }'
 187         */
 188         {0, ""},
 189         {1, "5"},                   // * 2
 190         {1, "25"},                  // * 4
 191         {1, "125"},                 // * 8
 192         {2, "625"},                 // * 16
 193         {2, "3125"},                // * 32
 194         {2, "15625"},               // * 64
 195         {3, "78125"},               // * 128
 196         {3, "390625"},              // * 256
 197         {3, "1953125"},             // * 512
 198         {4, "9765625"},             // * 1024
 199         {4, "48828125"},            // * 2048
 200         {4, "244140625"},           // * 4096
 201         {4, "1220703125"},          // * 8192
 202         {5, "6103515625"},          // * 16384
 203         {5, "30517578125"},         // * 32768
 204         {5, "152587890625"},        // * 65536
 205         {6, "762939453125"},        // * 131072
 206         {6, "3814697265625"},       // * 262144
 207         {6, "19073486328125"},      // * 524288
 208         {7, "95367431640625"},      // * 1048576
 209         {7, "476837158203125"},     // * 2097152
 210         {7, "2384185791015625"},    // * 4194304
 211         {7, "11920928955078125"},   // * 8388608
 212         {8, "59604644775390625"},   // * 16777216
 213         {8, "298023223876953125"},  // * 33554432
 214         {8, "1490116119384765625"}, // * 67108864
 215         {9, "7450580596923828125"}, // * 134217728
 216 }
 217
 218 // Is the leading prefix of b lexicographically less than s?
 219 func prefixIsLessThan(b []byte, s string) bool {
 220         for i := 0; i < len(s); i++ {
 221                 if i >= len(b) {
 222                         return true
 223                 }
 224                 if b[i] != s[i] {
 225                         return b[i] < s[i]
 226                 }
 227         }
 228         return false
 229 }
 230
 231 // Binary shift left (/ 2) by k bits.  k <= maxShift to avoid overflow.
 232 func leftShift(a *decimal, k uint) {
 233         delta := leftcheats[k].delta
 234         if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) {
 235                 delta--
 236         }
 237
 238         r := a.nd         // read index
 239         w := a.nd + delta // write index
 240         n := 0
 241
 242         // Pick up a digit, put down a digit.
 243         for r--; r >= 0; r-- {
 244                 n += (int(a.d[r]) - '0') << k
 245                 quo := n / 10
 246                 rem := n - 10*quo
 247                 w--
 248                 if w < len(a.d) {
 249                         a.d[w] = byte(rem + '0')
 250                 } else if rem != 0 {
 251                         a.trunc = true
 252                 }
 253                 n = quo
 254         }
 255
 256         // Put down extra digits.
 257         for n > 0 {
 258                 quo := n / 10
 259                 rem := n - 10*quo
 260                 w--
 261                 if w < len(a.d) {
 262                         a.d[w] = byte(rem + '0')
 263                 } else if rem != 0 {
 264                         a.trunc = true
 265                 }
 266                 n = quo
 267         }
 268
 269         a.nd += delta
 270         if a.nd >= len(a.d) {
 271                 a.nd = len(a.d)
 272         }
 273         a.dp += delta
 274         trim(a)
 275 }
 276
 277 // Binary shift left (k > 0) or right (k < 0).
 278 func (a *decimal) Shift(k int) {
 279         switch {
 280         case a.nd == 0:
 281                 // nothing to do: a == 0
 282         case k > 0:
 283                 for k > maxShift {
 284                         leftShift(a, maxShift)
 285                         k -= maxShift
 286                 }
 287                 leftShift(a, uint(k))
 288         case k < 0:
 289                 for k < -maxShift {
 290                         rightShift(a, maxShift)
 291                         k += maxShift
 292                 }
 293                 rightShift(a, uint(-k))
 294         }
 295 }
 296
 297 // If we chop a at nd digits, should we round up?
 298 func shouldRoundUp(a *decimal, nd int) bool {
 299         if nd < 0 || nd >= a.nd {
 300                 return false
 301         }
 302         if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even
 303                 // if we truncated, a little higher than what's recorded - always round up
 304                 if a.trunc {
 305                         return true
 306                 }
 307                 return nd > 0 && (a.d[nd-1]-'0')%2 != 0
 308         }
 309         // not halfway - digit tells all
 310         return a.d[nd] >= '5'
 311 }
 312
 313 // Round a to nd digits (or fewer).
 314 // If nd is zero, it means we're rounding
 315 // just to the left of the digits, as in
 316 // 0.09 -> 0.1.
 317 func (a *decimal) Round(nd int) {
 318         if nd < 0 || nd >= a.nd {
 319                 return
 320         }
 321         if shouldRoundUp(a, nd) {
 322                 a.RoundUp(nd)
 323         } else {
 324                 a.RoundDown(nd)
 325         }
 326 }
 327
 328 // Round a down to nd digits (or fewer).
 329 func (a *decimal) RoundDown(nd int) {
 330         if nd < 0 || nd >= a.nd {
 331                 return
 332         }
 333         a.nd = nd
 334         trim(a)
 335 }
 336
 337 // Round a up to nd digits (or fewer).
 338 func (a *decimal) RoundUp(nd int) {
 339         if nd < 0 || nd >= a.nd {
 340                 return
 341         }
 342
 343         // round up
 344         for i := nd - 1; i >= 0; i-- {
 345                 c := a.d[i]
 346                 if c < '9' { // can stop after this digit
 347                         a.d[i]++
 348                         a.nd = i + 1
 349                         return
 350                 }
 351         }
 352
 353         // Number is all 9s.
 354         // Change to single 1 with adjusted decimal point.
 355         a.d[0] = '1'
 356         a.nd = 1
 357         a.dp++
 358 }
 359
 360 // Extract integer part, rounded appropriately.
 361 // No guarantees about overflow.
 362 func (a *decimal) RoundedInteger() uint64 {
 363         if a.dp > 20 {
 364                 return 0xFFFFFFFFFFFFFFFF
 365         }
 366         var i int
 367         n := uint64(0)
 368         for i = 0; i < a.dp && i < a.nd; i++ {
 369                 n = n*10 + uint64(a.d[i]-'0')
 370         }
 371         for ; i < a.dp; i++ {
 372                 n *= 10
 373         }
 374         if shouldRoundUp(a, a.dp) {
 375                 n++
 376         }
 377         return n
 378 }