decimal.go

     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
View as plain text