| // Copyright 2015 The Go Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style | |
| // license that can be found in the LICENSE file. | |
| // This file implements multi-precision decimal numbers. | |
| // The implementation is for float to decimal conversion only; | |
| // not general purpose use. | |
| // The only operations are precise conversion from binary to | |
| // decimal and rounding. | |
| // | |
| // The key observation and some code (shr) is borrowed from | |
| // strconv/decimal.go: conversion of binary fractional values can be done | |
| // precisely in multi-precision decimal because 2 divides 10 (required for | |
| // >> of mantissa); but conversion of decimal floating-point values cannot | |
| // be done precisely in binary representation. | |
| // | |
| // In contrast to strconv/decimal.go, only right shift is implemented in | |
| // decimal format - left shift can be done precisely in binary format. | |
| package big | |
| // A decimal represents an unsigned floating-point number in decimal representation. | |
| // The value of a non-zero decimal d is d.mant * 10**d.exp with 0.1 <= d.mant < 1, | |
| // with the most-significant mantissa digit at index 0. For the zero decimal, the | |
| // mantissa length and exponent are 0. | |
| // The zero value for decimal represents a ready-to-use 0.0. | |
| type decimal struct { | |
| mant []byte // mantissa ASCII digits, big-endian | |
| exp int // exponent | |
| } | |
| // at returns the i'th mantissa digit, starting with the most significant digit at 0. | |
| func (d *decimal) at(i int) byte { | |
| if 0 <= i && i < len(d.mant) { | |
| return d.mant[i] | |
| } | |
| return '0' | |
| } | |
| // Maximum shift amount that can be done in one pass without overflow. | |
| // A Word has _W bits and (1<<maxShift - 1)*10 + 9 must fit into Word. | |
| const maxShift = _W - 4 | |
| // TODO(gri) Since we know the desired decimal precision when converting | |
| // a floating-point number, we may be able to limit the number of decimal | |
| // digits that need to be computed by init by providing an additional | |
| // precision argument and keeping track of when a number was truncated early | |
| // (equivalent of "sticky bit" in binary rounding). | |
| // TODO(gri) Along the same lines, enforce some limit to shift magnitudes | |
| // to avoid "infinitely" long running conversions (until we run out of space). | |
| // Init initializes x to the decimal representation of m << shift (for | |
| // shift >= 0), or m >> -shift (for shift < 0). | |
| func (x *decimal) init(m nat, shift int) { | |
| // special case 0 | |
| if len(m) == 0 { | |
| x.mant = x.mant[:0] | |
| x.exp = 0 | |
| return | |
| } | |
| // Optimization: If we need to shift right, first remove any trailing | |
| // zero bits from m to reduce shift amount that needs to be done in | |
| // decimal format (since that is likely slower). | |
| if shift < 0 { | |
| ntz := m.trailingZeroBits() | |
| s := uint(-shift) | |
| if s >= ntz { | |
| s = ntz // shift at most ntz bits | |
| } | |
| m = nat(nil).rsh(m, s) | |
| shift += int(s) | |
| } | |
| // Do any shift left in binary representation. | |
| if shift > 0 { | |
| m = nat(nil).lsh(m, uint(shift)) | |
| shift = 0 | |
| } | |
| // Convert mantissa into decimal representation. | |
| s := m.utoa(10) | |
| n := len(s) | |
| x.exp = n | |
| // Trim trailing zeros; instead the exponent is tracking | |
| // the decimal point independent of the number of digits. | |
| for n > 0 && s[n-1] == '0' { | |
| n-- | |
| } | |
| x.mant = append(x.mant[:0], s[:n]...) | |
| // Do any (remaining) shift right in decimal representation. | |
| if shift < 0 { | |
| for shift < -maxShift { | |
| rsh(x, maxShift) | |
| shift += maxShift | |
| } | |
| rsh(x, uint(-shift)) | |
| } | |
| } | |
| // rsh implements x >> s, for s <= maxShift. | |
| func rsh(x *decimal, s uint) { | |
| // Division by 1<<s using shift-and-subtract algorithm. | |
| // pick up enough leading digits to cover first shift | |
| r := 0 // read index | |
| var n Word | |
| for n>>s == 0 && r < len(x.mant) { | |
| ch := Word(x.mant[r]) | |
| r++ | |
| n = n*10 + ch - '0' | |
| } | |
| if n == 0 { | |
| // x == 0; shouldn't get here, but handle anyway | |
| x.mant = x.mant[:0] | |
| return | |
| } | |
| for n>>s == 0 { | |
| r++ | |
| n *= 10 | |
| } | |
| x.exp += 1 - r | |
| // read a digit, write a digit | |
| w := 0 // write index | |
| mask := Word(1)<<s - 1 | |
| for r < len(x.mant) { | |
| ch := Word(x.mant[r]) | |
| r++ | |
| d := n >> s | |
| n &= mask // n -= d << s | |
| x.mant[w] = byte(d + '0') | |
| w++ | |
| n = n*10 + ch - '0' | |
| } | |
| // write extra digits that still fit | |
| for n > 0 && w < len(x.mant) { | |
| d := n >> s | |
| n &= mask | |
| x.mant[w] = byte(d + '0') | |
| w++ | |
| n = n * 10 | |
| } | |
| x.mant = x.mant[:w] // the number may be shorter (e.g. 1024 >> 10) | |
| // append additional digits that didn't fit | |
| for n > 0 { | |
| d := n >> s | |
| n &= mask | |
| x.mant = append(x.mant, byte(d+'0')) | |
| n = n * 10 | |
| } | |
| trim(x) | |
| } | |
| func (x *decimal) String() string { | |
| if len(x.mant) == 0 { | |
| return "0" | |
| } | |
| var buf []byte | |
| switch { | |
| case x.exp <= 0: | |
| // 0.00ddd | |
| buf = make([]byte, 0, 2+(-x.exp)+len(x.mant)) | |
| buf = append(buf, "0."...) | |
| buf = appendZeros(buf, -x.exp) | |
| buf = append(buf, x.mant...) | |
| case /* 0 < */ x.exp < len(x.mant): | |
| // dd.ddd | |
| buf = make([]byte, 0, 1+len(x.mant)) | |
| buf = append(buf, x.mant[:x.exp]...) | |
| buf = append(buf, '.') | |
| buf = append(buf, x.mant[x.exp:]...) | |
| default: // len(x.mant) <= x.exp | |
| // ddd00 | |
| buf = make([]byte, 0, x.exp) | |
| buf = append(buf, x.mant...) | |
| buf = appendZeros(buf, x.exp-len(x.mant)) | |
| } | |
| return string(buf) | |
| } | |
| // appendZeros appends n 0 digits to buf and returns buf. | |
| func appendZeros(buf []byte, n int) []byte { | |
| for ; n > 0; n-- { | |
| buf = append(buf, '0') | |
| } | |
| return buf | |
| } | |
| // shouldRoundUp reports if x should be rounded up | |
| // if shortened to n digits. n must be a valid index | |
| // for x.mant. | |
| func shouldRoundUp(x *decimal, n int) bool { | |
| if x.mant[n] == '5' && n+1 == len(x.mant) { | |
| // exactly halfway - round to even | |
| return n > 0 && (x.mant[n-1]-'0')&1 != 0 | |
| } | |
| // not halfway - digit tells all (x.mant has no trailing zeros) | |
| return x.mant[n] >= '5' | |
| } | |
| // round sets x to (at most) n mantissa digits by rounding it | |
| // to the nearest even value with n (or fever) mantissa digits. | |
| // If n < 0, x remains unchanged. | |
| func (x *decimal) round(n int) { | |
| if n < 0 || n >= len(x.mant) { | |
| return // nothing to do | |
| } | |
| if shouldRoundUp(x, n) { | |
| x.roundUp(n) | |
| } else { | |
| x.roundDown(n) | |
| } | |
| } | |
| func (x *decimal) roundUp(n int) { | |
| if n < 0 || n >= len(x.mant) { | |
| return // nothing to do | |
| } | |
| // 0 <= n < len(x.mant) | |
| // find first digit < '9' | |
| for n > 0 && x.mant[n-1] >= '9' { | |
| n-- | |
| } | |
| if n == 0 { | |
| // all digits are '9's => round up to '1' and update exponent | |
| x.mant[0] = '1' // ok since len(x.mant) > n | |
| x.mant = x.mant[:1] | |
| x.exp++ | |
| return | |
| } | |
| // n > 0 && x.mant[n-1] < '9' | |
| x.mant[n-1]++ | |
| x.mant = x.mant[:n] | |
| // x already trimmed | |
| } | |
| func (x *decimal) roundDown(n int) { | |
| if n < 0 || n >= len(x.mant) { | |
| return // nothing to do | |
| } | |
| x.mant = x.mant[:n] | |
| trim(x) | |
| } | |
| // trim cuts off any trailing zeros from x's mantissa; | |
| // they are meaningless for the value of x. | |
| func trim(x *decimal) { | |
| i := len(x.mant) | |
| for i > 0 && x.mant[i-1] == '0' { | |
| i-- | |
| } | |
| x.mant = x.mant[:i] | |
| if i == 0 { | |
| x.exp = 0 | |
| } | |
| } | |