blob: 26548b63cef476f5cf604a97e6e0b21f460c6d85 [file] [log] [blame]
Matthias Andreas Benkard832a54e2019-01-29 09:27:38 +01001// 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//
23package inf // import "gopkg.in/inf.v0"
24
25// TODO:
26// - avoid excessive deep copying (quo and rounders)
27
28import (
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//
83type Dec struct {
84 unscaled big.Int
85 scale Scale
86}
87
88// Scale represents the type used for the scale of a Dec.
89type Scale int32
90
91const 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.
95type scaler interface {
96 Scale(x *Dec, y *Dec) Scale
97}
98
99var 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
105var 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.
116func 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.
122func NewDecBig(unscaled *big.Int, scale Scale) *Dec {
123 return new(Dec).SetUnscaledBig(unscaled).SetScale(scale)
124}
125
126// Scale returns the scale of x.
127func (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.
135func (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.
143func (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).
151func (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.
158func (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.
165func (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.
172func (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//
186func (x *Dec) Sign() int {
187 return x.UnscaledBig().Sign()
188}
189
190// Neg sets z to -x and returns z.
191func (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//
203func (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.
209func (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.
217func (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.
226func (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.
235func (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.
243func (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//
256func (z *Dec) QuoRound(x, y *Dec, s Scale, r Rounder) *Dec {
257 return z.quo(x, y, sclr{s}, r)
258}
259
260func (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.
282func (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//
297func (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
336type sclr struct{ s Scale }
337
338func (s sclr) Scale(x, y *Dec) Scale {
339 return s.s
340}
341
342type scaleQuoExact struct{}
343
344func (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
356func 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
371func 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
379func 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
391func 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
398func (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
411var zeros = []byte("00000000000000000000000000000000" +
412 "00000000000000000000000000000000")
413var lzeros = Scale(len(zeros))
414
415func 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
426func (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.
462func (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
470func (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
473loop:
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.
525func (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.
544func (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
554const decGobVersion byte = 1
555
556func 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
567func 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.
576func (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.
586func (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.
604func (x *Dec) MarshalText() ([]byte, error) {
605 return []byte(x.String()), nil
606}
607
608// UnmarshalText implements the encoding.TextUnmarshaler interface.
609func (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}