dec.go

Documentation: gopkg.in/inf.v0

     1  // Package inf (type inf.Dec) implements "infinite-precision" decimal
     2  // arithmetic.
     3  // "Infinite precision" describes two characteristics: practically unlimited
     4  // precision for decimal number representation and no support for calculating
     5  // with any specific fixed precision.
     6  // (Although there is no practical limit on precision, inf.Dec can only
     7  // represent finite decimals.)
     8  //
     9  // This package is currently in experimental stage and the API may change.
    10  //
    11  // This package does NOT support:
    12  //  - rounding to specific precisions (as opposed to specific decimal positions)
    13  //  - the notion of context (each rounding must be explicit)
    14  //  - NaN and Inf values, and distinguishing between positive and negative zero
    15  //  - conversions to and from float32/64 types
    16  //
    17  // Features considered for possible addition:
    18  //  + formatting options
    19  //  + Exp method
    20  //  + combined operations such as AddRound/MulAdd etc
    21  //  + exchanging data in decimal32/64/128 formats
    22  //
    23  package inf // import "gopkg.in/inf.v0"
    24  
    25  // TODO:
    26  //  - avoid excessive deep copying (quo and rounders)
    27  
    28  import (
    29  	"fmt"
    30  	"io"
    31  	"math/big"
    32  	"strings"
    33  )
    34  
    35  // A Dec represents a signed arbitrary-precision decimal.
    36  // It is a combination of a sign, an arbitrary-precision integer coefficient
    37  // value, and a signed fixed-precision exponent value.
    38  // The sign and the coefficient value are handled together as a signed value
    39  // and referred to as the unscaled value.
    40  // (Positive and negative zero values are not distinguished.)
    41  // Since the exponent is most commonly non-positive, it is handled in negated
    42  // form and referred to as scale.
    43  //
    44  // The mathematical value of a Dec equals:
    45  //
    46  //  unscaled * 10**(-scale)
    47  //
    48  // Note that different Dec representations may have equal mathematical values.
    49  //
    50  //  unscaled  scale  String()
    51  //  -------------------------
    52  //         0      0    "0"
    53  //         0      2    "0.00"
    54  //         0     -2    "0"
    55  //         1      0    "1"
    56  //       100      2    "1.00"
    57  //        10      0   "10"
    58  //         1     -1   "10"
    59  //
    60  // The zero value for a Dec represents the value 0 with scale 0.
    61  //
    62  // Operations are typically performed through the *Dec type.
    63  // The semantics of the assignment operation "=" for "bare" Dec values is
    64  // undefined and should not be relied on.
    65  //
    66  // Methods are typically of the form:
    67  //
    68  //	func (z *Dec) Op(x, y *Dec) *Dec
    69  //
    70  // and implement operations z = x Op y with the result as receiver; if it
    71  // is one of the operands it may be overwritten (and its memory reused).
    72  // To enable chaining of operations, the result is also returned. Methods
    73  // returning a result other than *Dec take one of the operands as the receiver.
    74  //
    75  // A "bare" Quo method (quotient / division operation) is not provided, as the
    76  // result is not always a finite decimal and thus in general cannot be
    77  // represented as a Dec.
    78  // Instead, in the common case when rounding is (potentially) necessary,
    79  // QuoRound should be used with a Scale and a Rounder.
    80  // QuoExact or QuoRound with RoundExact can be used in the special cases when it
    81  // is known that the result is always a finite decimal.
    82  //
    83  type Dec struct {
    84  	unscaled big.Int
    85  	scale    Scale
    86  }
    87  
    88  // Scale represents the type used for the scale of a Dec.
    89  type Scale int32
    90  
    91  const scaleSize = 4 // bytes in a Scale value
    92  
    93  // Scaler represents a method for obtaining the scale to use for the result of
    94  // an operation on x and y.
    95  type scaler interface {
    96  	Scale(x *Dec, y *Dec) Scale
    97  }
    98  
    99  var bigInt = [...]*big.Int{
   100  	big.NewInt(0), big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(4),
   101  	big.NewInt(5), big.NewInt(6), big.NewInt(7), big.NewInt(8), big.NewInt(9),
   102  	big.NewInt(10),
   103  }
   104  
   105  var exp10cache [64]big.Int = func() [64]big.Int {
   106  	e10, e10i := [64]big.Int{}, bigInt[1]
   107  	for i := range e10 {
   108  		e10[i].Set(e10i)
   109  		e10i = new(big.Int).Mul(e10i, bigInt[10])
   110  	}
   111  	return e10
   112  }()
   113  
   114  // NewDec allocates and returns a new Dec set to the given int64 unscaled value
   115  // and scale.
   116  func NewDec(unscaled int64, scale Scale) *Dec {
   117  	return new(Dec).SetUnscaled(unscaled).SetScale(scale)
   118  }
   119  
   120  // NewDecBig allocates and returns a new Dec set to the given *big.Int unscaled
   121  // value and scale.
   122  func NewDecBig(unscaled *big.Int, scale Scale) *Dec {
   123  	return new(Dec).SetUnscaledBig(unscaled).SetScale(scale)
   124  }
   125  
   126  // Scale returns the scale of x.
   127  func (x *Dec) Scale() Scale {
   128  	return x.scale
   129  }
   130  
   131  // Unscaled returns the unscaled value of x for u and true for ok when the
   132  // unscaled value can be represented as int64; otherwise it returns an undefined
   133  // int64 value for u and false for ok. Use x.UnscaledBig().Int64() to avoid
   134  // checking the validity of the value when the check is known to be redundant.
   135  func (x *Dec) Unscaled() (u int64, ok bool) {
   136  	u = x.unscaled.Int64()
   137  	var i big.Int
   138  	ok = i.SetInt64(u).Cmp(&x.unscaled) == 0
   139  	return
   140  }
   141  
   142  // UnscaledBig returns the unscaled value of x as *big.Int.
   143  func (x *Dec) UnscaledBig() *big.Int {
   144  	return &x.unscaled
   145  }
   146  
   147  // SetScale sets the scale of z, with the unscaled value unchanged, and returns
   148  // z.
   149  // The mathematical value of the Dec changes as if it was multiplied by
   150  // 10**(oldscale-scale).
   151  func (z *Dec) SetScale(scale Scale) *Dec {
   152  	z.scale = scale
   153  	return z
   154  }
   155  
   156  // SetUnscaled sets the unscaled value of z, with the scale unchanged, and
   157  // returns z.
   158  func (z *Dec) SetUnscaled(unscaled int64) *Dec {
   159  	z.unscaled.SetInt64(unscaled)
   160  	return z
   161  }
   162  
   163  // SetUnscaledBig sets the unscaled value of z, with the scale unchanged, and
   164  // returns z.
   165  func (z *Dec) SetUnscaledBig(unscaled *big.Int) *Dec {
   166  	z.unscaled.Set(unscaled)
   167  	return z
   168  }
   169  
   170  // Set sets z to the value of x and returns z.
   171  // It does nothing if z == x.
   172  func (z *Dec) Set(x *Dec) *Dec {
   173  	if z != x {
   174  		z.SetUnscaledBig(x.UnscaledBig())
   175  		z.SetScale(x.Scale())
   176  	}
   177  	return z
   178  }
   179  
   180  // Sign returns:
   181  //
   182  //	-1 if x <  0
   183  //	 0 if x == 0
   184  //	+1 if x >  0
   185  //
   186  func (x *Dec) Sign() int {
   187  	return x.UnscaledBig().Sign()
   188  }
   189  
   190  // Neg sets z to -x and returns z.
   191  func (z *Dec) Neg(x *Dec) *Dec {
   192  	z.SetScale(x.Scale())
   193  	z.UnscaledBig().Neg(x.UnscaledBig())
   194  	return z
   195  }
   196  
   197  // Cmp compares x and y and returns:
   198  //
   199  //   -1 if x <  y
   200  //    0 if x == y
   201  //   +1 if x >  y
   202  //
   203  func (x *Dec) Cmp(y *Dec) int {
   204  	xx, yy := upscale(x, y)
   205  	return xx.UnscaledBig().Cmp(yy.UnscaledBig())
   206  }
   207  
   208  // Abs sets z to |x| (the absolute value of x) and returns z.
   209  func (z *Dec) Abs(x *Dec) *Dec {
   210  	z.SetScale(x.Scale())
   211  	z.UnscaledBig().Abs(x.UnscaledBig())
   212  	return z
   213  }
   214  
   215  // Add sets z to the sum x+y and returns z.
   216  // The scale of z is the greater of the scales of x and y.
   217  func (z *Dec) Add(x, y *Dec) *Dec {
   218  	xx, yy := upscale(x, y)
   219  	z.SetScale(xx.Scale())
   220  	z.UnscaledBig().Add(xx.UnscaledBig(), yy.UnscaledBig())
   221  	return z
   222  }
   223  
   224  // Sub sets z to the difference x-y and returns z.
   225  // The scale of z is the greater of the scales of x and y.
   226  func (z *Dec) Sub(x, y *Dec) *Dec {
   227  	xx, yy := upscale(x, y)
   228  	z.SetScale(xx.Scale())
   229  	z.UnscaledBig().Sub(xx.UnscaledBig(), yy.UnscaledBig())
   230  	return z
   231  }
   232  
   233  // Mul sets z to the product x*y and returns z.
   234  // The scale of z is the sum of the scales of x and y.
   235  func (z *Dec) Mul(x, y *Dec) *Dec {
   236  	z.SetScale(x.Scale() + y.Scale())
   237  	z.UnscaledBig().Mul(x.UnscaledBig(), y.UnscaledBig())
   238  	return z
   239  }
   240  
   241  // Round sets z to the value of x rounded to Scale s using Rounder r, and
   242  // returns z.
   243  func (z *Dec) Round(x *Dec, s Scale, r Rounder) *Dec {
   244  	return z.QuoRound(x, NewDec(1, 0), s, r)
   245  }
   246  
   247  // QuoRound sets z to the quotient x/y, rounded using the given Rounder to the
   248  // specified scale.
   249  //
   250  // If the rounder is RoundExact but the result can not be expressed exactly at
   251  // the specified scale, QuoRound returns nil, and the value of z is undefined.
   252  //
   253  // There is no corresponding Div method; the equivalent can be achieved through
   254  // the choice of Rounder used.
   255  //
   256  func (z *Dec) QuoRound(x, y *Dec, s Scale, r Rounder) *Dec {
   257  	return z.quo(x, y, sclr{s}, r)
   258  }
   259  
   260  func (z *Dec) quo(x, y *Dec, s scaler, r Rounder) *Dec {
   261  	scl := s.Scale(x, y)
   262  	var zzz *Dec
   263  	if r.UseRemainder() {
   264  		zz, rA, rB := new(Dec).quoRem(x, y, scl, true, new(big.Int), new(big.Int))
   265  		zzz = r.Round(new(Dec), zz, rA, rB)
   266  	} else {
   267  		zz, _, _ := new(Dec).quoRem(x, y, scl, false, nil, nil)
   268  		zzz = r.Round(new(Dec), zz, nil, nil)
   269  	}
   270  	if zzz == nil {
   271  		return nil
   272  	}
   273  	return z.Set(zzz)
   274  }
   275  
   276  // QuoExact sets z to the quotient x/y and returns z when x/y is a finite
   277  // decimal. Otherwise it returns nil and the value of z is undefined.
   278  //
   279  // The scale of a non-nil result is "x.Scale() - y.Scale()" or greater; it is
   280  // calculated so that the remainder will be zero whenever x/y is a finite
   281  // decimal.
   282  func (z *Dec) QuoExact(x, y *Dec) *Dec {
   283  	return z.quo(x, y, scaleQuoExact{}, RoundExact)
   284  }
   285  
   286  // quoRem sets z to the quotient x/y with the scale s, and if useRem is true,
   287  // it sets remNum and remDen to the numerator and denominator of the remainder.
   288  // It returns z, remNum and remDen.
   289  //
   290  // The remainder is normalized to the range -1 < r < 1 to simplify rounding;
   291  // that is, the results satisfy the following equation:
   292  //
   293  //  x / y = z + (remNum/remDen) * 10**(-z.Scale())
   294  //
   295  // See Rounder for more details about rounding.
   296  //
   297  func (z *Dec) quoRem(x, y *Dec, s Scale, useRem bool,
   298  	remNum, remDen *big.Int) (*Dec, *big.Int, *big.Int) {
   299  	// difference (required adjustment) compared to "canonical" result scale
   300  	shift := s - (x.Scale() - y.Scale())
   301  	// pointers to adjusted unscaled dividend and divisor
   302  	var ix, iy *big.Int
   303  	switch {
   304  	case shift > 0:
   305  		// increased scale: decimal-shift dividend left
   306  		ix = new(big.Int).Mul(x.UnscaledBig(), exp10(shift))
   307  		iy = y.UnscaledBig()
   308  	case shift < 0:
   309  		// decreased scale: decimal-shift divisor left
   310  		ix = x.UnscaledBig()
   311  		iy = new(big.Int).Mul(y.UnscaledBig(), exp10(-shift))
   312  	default:
   313  		ix = x.UnscaledBig()
   314  		iy = y.UnscaledBig()
   315  	}
   316  	// save a copy of iy in case it to be overwritten with the result
   317  	iy2 := iy
   318  	if iy == z.UnscaledBig() {
   319  		iy2 = new(big.Int).Set(iy)
   320  	}
   321  	// set scale
   322  	z.SetScale(s)
   323  	// set unscaled
   324  	if useRem {
   325  		// Int division
   326  		_, intr := z.UnscaledBig().QuoRem(ix, iy, new(big.Int))
   327  		// set remainder
   328  		remNum.Set(intr)
   329  		remDen.Set(iy2)
   330  	} else {
   331  		z.UnscaledBig().Quo(ix, iy)
   332  	}
   333  	return z, remNum, remDen
   334  }
   335  
   336  type sclr struct{ s Scale }
   337  
   338  func (s sclr) Scale(x, y *Dec) Scale {
   339  	return s.s
   340  }
   341  
   342  type scaleQuoExact struct{}
   343  
   344  func (sqe scaleQuoExact) Scale(x, y *Dec) Scale {
   345  	rem := new(big.Rat).SetFrac(x.UnscaledBig(), y.UnscaledBig())
   346  	f2, f5 := factor2(rem.Denom()), factor(rem.Denom(), bigInt[5])
   347  	var f10 Scale
   348  	if f2 > f5 {
   349  		f10 = Scale(f2)
   350  	} else {
   351  		f10 = Scale(f5)
   352  	}
   353  	return x.Scale() - y.Scale() + f10
   354  }
   355  
   356  func factor(n *big.Int, p *big.Int) int {
   357  	// could be improved for large factors
   358  	d, f := n, 0
   359  	for {
   360  		dd, dm := new(big.Int).DivMod(d, p, new(big.Int))
   361  		if dm.Sign() == 0 {
   362  			f++
   363  			d = dd
   364  		} else {
   365  			break
   366  		}
   367  	}
   368  	return f
   369  }
   370  
   371  func factor2(n *big.Int) int {
   372  	// could be improved for large factors
   373  	f := 0
   374  	for ; n.Bit(f) == 0; f++ {
   375  	}
   376  	return f
   377  }
   378  
   379  func upscale(a, b *Dec) (*Dec, *Dec) {
   380  	if a.Scale() == b.Scale() {
   381  		return a, b
   382  	}
   383  	if a.Scale() > b.Scale() {
   384  		bb := b.rescale(a.Scale())
   385  		return a, bb
   386  	}
   387  	aa := a.rescale(b.Scale())
   388  	return aa, b
   389  }
   390  
   391  func exp10(x Scale) *big.Int {
   392  	if int(x) < len(exp10cache) {
   393  		return &exp10cache[int(x)]
   394  	}
   395  	return new(big.Int).Exp(bigInt[10], big.NewInt(int64(x)), nil)
   396  }
   397  
   398  func (x *Dec) rescale(newScale Scale) *Dec {
   399  	shift := newScale - x.Scale()
   400  	switch {
   401  	case shift < 0:
   402  		e := exp10(-shift)
   403  		return NewDecBig(new(big.Int).Quo(x.UnscaledBig(), e), newScale)
   404  	case shift > 0:
   405  		e := exp10(shift)
   406  		return NewDecBig(new(big.Int).Mul(x.UnscaledBig(), e), newScale)
   407  	}
   408  	return x
   409  }
   410  
   411  var zeros = []byte("00000000000000000000000000000000" +
   412  	"00000000000000000000000000000000")
   413  var lzeros = Scale(len(zeros))
   414  
   415  func appendZeros(s []byte, n Scale) []byte {
   416  	for i := Scale(0); i < n; i += lzeros {
   417  		if n > i+lzeros {
   418  			s = append(s, zeros...)
   419  		} else {
   420  			s = append(s, zeros[0:n-i]...)
   421  		}
   422  	}
   423  	return s
   424  }
   425  
   426  func (x *Dec) String() string {
   427  	if x == nil {
   428  		return "<nil>"
   429  	}
   430  	scale := x.Scale()
   431  	s := []byte(x.UnscaledBig().String())
   432  	if scale <= 0 {
   433  		if scale != 0 && x.unscaled.Sign() != 0 {
   434  			s = appendZeros(s, -scale)
   435  		}
   436  		return string(s)
   437  	}
   438  	negbit := Scale(-((x.Sign() - 1) / 2))
   439  	// scale > 0
   440  	lens := Scale(len(s))
   441  	if lens-negbit <= scale {
   442  		ss := make([]byte, 0, scale+2)
   443  		if negbit == 1 {
   444  			ss = append(ss, '-')
   445  		}
   446  		ss = append(ss, '0', '.')
   447  		ss = appendZeros(ss, scale-lens+negbit)
   448  		ss = append(ss, s[negbit:]...)
   449  		return string(ss)
   450  	}
   451  	// lens > scale
   452  	ss := make([]byte, 0, lens+1)
   453  	ss = append(ss, s[:lens-scale]...)
   454  	ss = append(ss, '.')
   455  	ss = append(ss, s[lens-scale:]...)
   456  	return string(ss)
   457  }
   458  
   459  // Format is a support routine for fmt.Formatter. It accepts the decimal
   460  // formats 'd' and 'f', and handles both equivalently.
   461  // Width, precision, flags and bases 2, 8, 16 are not supported.
   462  func (x *Dec) Format(s fmt.State, ch rune) {
   463  	if ch != 'd' && ch != 'f' && ch != 'v' && ch != 's' {
   464  		fmt.Fprintf(s, "%%!%c(dec.Dec=%s)", ch, x.String())
   465  		return
   466  	}
   467  	fmt.Fprintf(s, x.String())
   468  }
   469  
   470  func (z *Dec) scan(r io.RuneScanner) (*Dec, error) {
   471  	unscaled := make([]byte, 0, 256) // collects chars of unscaled as bytes
   472  	dp, dg := -1, -1                 // indexes of decimal point, first digit
   473  loop:
   474  	for {
   475  		ch, _, err := r.ReadRune()
   476  		if err == io.EOF {
   477  			break loop
   478  		}
   479  		if err != nil {
   480  			return nil, err
   481  		}
   482  		switch {
   483  		case ch == '+' || ch == '-':
   484  			if len(unscaled) > 0 || dp >= 0 { // must be first character
   485  				r.UnreadRune()
   486  				break loop
   487  			}
   488  		case ch == '.':
   489  			if dp >= 0 {
   490  				r.UnreadRune()
   491  				break loop
   492  			}
   493  			dp = len(unscaled)
   494  			continue // don't add to unscaled
   495  		case ch >= '0' && ch <= '9':
   496  			if dg == -1 {
   497  				dg = len(unscaled)
   498  			}
   499  		default:
   500  			r.UnreadRune()
   501  			break loop
   502  		}
   503  		unscaled = append(unscaled, byte(ch))
   504  	}
   505  	if dg == -1 {
   506  		return nil, fmt.Errorf("no digits read")
   507  	}
   508  	if dp >= 0 {
   509  		z.SetScale(Scale(len(unscaled) - dp))
   510  	} else {
   511  		z.SetScale(0)
   512  	}
   513  	_, ok := z.UnscaledBig().SetString(string(unscaled), 10)
   514  	if !ok {
   515  		return nil, fmt.Errorf("invalid decimal: %s", string(unscaled))
   516  	}
   517  	return z, nil
   518  }
   519  
   520  // SetString sets z to the value of s, interpreted as a decimal (base 10),
   521  // and returns z and a boolean indicating success. The scale of z is the
   522  // number of digits after the decimal point (including any trailing 0s),
   523  // or 0 if there is no decimal point. If SetString fails, the value of z
   524  // is undefined but the returned value is nil.
   525  func (z *Dec) SetString(s string) (*Dec, bool) {
   526  	r := strings.NewReader(s)
   527  	_, err := z.scan(r)
   528  	if err != nil {
   529  		return nil, false
   530  	}
   531  	_, _, err = r.ReadRune()
   532  	if err != io.EOF {
   533  		return nil, false
   534  	}
   535  	// err == io.EOF => scan consumed all of s
   536  	return z, true
   537  }
   538  
   539  // Scan is a support routine for fmt.Scanner; it sets z to the value of
   540  // the scanned number. It accepts the decimal formats 'd' and 'f', and
   541  // handles both equivalently. Bases 2, 8, 16 are not supported.
   542  // The scale of z is the number of digits after the decimal point
   543  // (including any trailing 0s), or 0 if there is no decimal point.
   544  func (z *Dec) Scan(s fmt.ScanState, ch rune) error {
   545  	if ch != 'd' && ch != 'f' && ch != 's' && ch != 'v' {
   546  		return fmt.Errorf("Dec.Scan: invalid verb '%c'", ch)
   547  	}
   548  	s.SkipSpace()
   549  	_, err := z.scan(s)
   550  	return err
   551  }
   552  
   553  // Gob encoding version
   554  const decGobVersion byte = 1
   555  
   556  func scaleBytes(s Scale) []byte {
   557  	buf := make([]byte, scaleSize)
   558  	i := scaleSize
   559  	for j := 0; j < scaleSize; j++ {
   560  		i--
   561  		buf[i] = byte(s)
   562  		s >>= 8
   563  	}
   564  	return buf
   565  }
   566  
   567  func scale(b []byte) (s Scale) {
   568  	for j := 0; j < scaleSize; j++ {
   569  		s <<= 8
   570  		s |= Scale(b[j])
   571  	}
   572  	return
   573  }
   574  
   575  // GobEncode implements the gob.GobEncoder interface.
   576  func (x *Dec) GobEncode() ([]byte, error) {
   577  	buf, err := x.UnscaledBig().GobEncode()
   578  	if err != nil {
   579  		return nil, err
   580  	}
   581  	buf = append(append(buf, scaleBytes(x.Scale())...), decGobVersion)
   582  	return buf, nil
   583  }
   584  
   585  // GobDecode implements the gob.GobDecoder interface.
   586  func (z *Dec) GobDecode(buf []byte) error {
   587  	if len(buf) == 0 {
   588  		return fmt.Errorf("Dec.GobDecode: no data")
   589  	}
   590  	b := buf[len(buf)-1]
   591  	if b != decGobVersion {
   592  		return fmt.Errorf("Dec.GobDecode: encoding version %d not supported", b)
   593  	}
   594  	l := len(buf) - scaleSize - 1
   595  	err := z.UnscaledBig().GobDecode(buf[:l])
   596  	if err != nil {
   597  		return err
   598  	}
   599  	z.SetScale(scale(buf[l : l+scaleSize]))
   600  	return nil
   601  }
   602  
   603  // MarshalText implements the encoding.TextMarshaler interface.
   604  func (x *Dec) MarshalText() ([]byte, error) {
   605  	return []byte(x.String()), nil
   606  }
   607  
   608  // UnmarshalText implements the encoding.TextUnmarshaler interface.
   609  func (z *Dec) UnmarshalText(data []byte) error {
   610  	_, ok := z.SetString(string(data))
   611  	if !ok {
   612  		return fmt.Errorf("invalid inf.Dec")
   613  	}
   614  	return nil
   615  }
   616
View as plain text