Source file src/pkg/math/big/rat.go

     1	// Copyright 2010 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 rational numbers.
     6	
     7	package big
     8	
     9	import (
    10		"encoding/binary"
    11		"errors"
    12		"fmt"
    13		"strings"
    14	)
    15	
    16	// A Rat represents a quotient a/b of arbitrary precision.
    17	// The zero value for a Rat represents the value 0.
    18	type Rat struct {
    19		a Int
    20		b nat // len(b) == 0 acts like b == 1
    21	}
    22	
    23	// NewRat creates a new Rat with numerator a and denominator b.
    24	func NewRat(a, b int64) *Rat {
    25		return new(Rat).SetFrac64(a, b)
    26	}
    27	
    28	// SetFrac sets z to a/b and returns z.
    29	func (z *Rat) SetFrac(a, b *Int) *Rat {
    30		z.a.neg = a.neg != b.neg
    31		babs := b.abs
    32		if len(babs) == 0 {
    33			panic("division by zero")
    34		}
    35		if &z.a == b || alias(z.a.abs, babs) {
    36			babs = nat(nil).set(babs) // make a copy
    37		}
    38		z.a.abs = z.a.abs.set(a.abs)
    39		z.b = z.b.set(babs)
    40		return z.norm()
    41	}
    42	
    43	// SetFrac64 sets z to a/b and returns z.
    44	func (z *Rat) SetFrac64(a, b int64) *Rat {
    45		z.a.SetInt64(a)
    46		if b == 0 {
    47			panic("division by zero")
    48		}
    49		if b < 0 {
    50			b = -b
    51			z.a.neg = !z.a.neg
    52		}
    53		z.b = z.b.setUint64(uint64(b))
    54		return z.norm()
    55	}
    56	
    57	// SetInt sets z to x (by making a copy of x) and returns z.
    58	func (z *Rat) SetInt(x *Int) *Rat {
    59		z.a.Set(x)
    60		z.b = z.b.make(0)
    61		return z
    62	}
    63	
    64	// SetInt64 sets z to x and returns z.
    65	func (z *Rat) SetInt64(x int64) *Rat {
    66		z.a.SetInt64(x)
    67		z.b = z.b.make(0)
    68		return z
    69	}
    70	
    71	// Set sets z to x (by making a copy of x) and returns z.
    72	func (z *Rat) Set(x *Rat) *Rat {
    73		if z != x {
    74			z.a.Set(&x.a)
    75			z.b = z.b.set(x.b)
    76		}
    77		return z
    78	}
    79	
    80	// Abs sets z to |x| (the absolute value of x) and returns z.
    81	func (z *Rat) Abs(x *Rat) *Rat {
    82		z.Set(x)
    83		z.a.neg = false
    84		return z
    85	}
    86	
    87	// Neg sets z to -x and returns z.
    88	func (z *Rat) Neg(x *Rat) *Rat {
    89		z.Set(x)
    90		z.a.neg = len(z.a.abs) > 0 && !z.a.neg // 0 has no sign
    91		return z
    92	}
    93	
    94	// Inv sets z to 1/x and returns z.
    95	func (z *Rat) Inv(x *Rat) *Rat {
    96		if len(x.a.abs) == 0 {
    97			panic("division by zero")
    98		}
    99		z.Set(x)
   100		a := z.b
   101		if len(a) == 0 {
   102			a = a.setWord(1) // materialize numerator
   103		}
   104		b := z.a.abs
   105		if b.cmp(natOne) == 0 {
   106			b = b.make(0) // normalize denominator
   107		}
   108		z.a.abs, z.b = a, b // sign doesn't change
   109		return z
   110	}
   111	
   112	// Sign returns:
   113	//
   114	//	-1 if x <  0
   115	//	 0 if x == 0
   116	//	+1 if x >  0
   117	//
   118	func (x *Rat) Sign() int {
   119		return x.a.Sign()
   120	}
   121	
   122	// IsInt returns true if the denominator of x is 1.
   123	func (x *Rat) IsInt() bool {
   124		return len(x.b) == 0 || x.b.cmp(natOne) == 0
   125	}
   126	
   127	// Num returns the numerator of x; it may be <= 0.
   128	// The result is a reference to x's numerator; it
   129	// may change if a new value is assigned to x.
   130	func (x *Rat) Num() *Int {
   131		return &x.a
   132	}
   133	
   134	// Denom returns the denominator of x; it is always > 0.
   135	// The result is a reference to x's denominator; it
   136	// may change if a new value is assigned to x.
   137	func (x *Rat) Denom() *Int {
   138		if len(x.b) == 0 {
   139			return &Int{abs: nat{1}}
   140		}
   141		return &Int{abs: x.b}
   142	}
   143	
   144	func gcd(x, y nat) nat {
   145		// Euclidean algorithm.
   146		var a, b nat
   147		a = a.set(x)
   148		b = b.set(y)
   149		for len(b) != 0 {
   150			var q, r nat
   151			_, r = q.div(r, a, b)
   152			a = b
   153			b = r
   154		}
   155		return a
   156	}
   157	
   158	func (z *Rat) norm() *Rat {
   159		switch {
   160		case len(z.a.abs) == 0:
   161			// z == 0 - normalize sign and denominator
   162			z.a.neg = false
   163			z.b = z.b.make(0)
   164		case len(z.b) == 0:
   165			// z is normalized int - nothing to do
   166		case z.b.cmp(natOne) == 0:
   167			// z is int - normalize denominator
   168			z.b = z.b.make(0)
   169		default:
   170			if f := gcd(z.a.abs, z.b); f.cmp(natOne) != 0 {
   171				z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f)
   172				z.b, _ = z.b.div(nil, z.b, f)
   173			}
   174		}
   175		return z
   176	}
   177	
   178	// mulDenom sets z to the denominator product x*y (by taking into
   179	// account that 0 values for x or y must be interpreted as 1) and
   180	// returns z.
   181	func mulDenom(z, x, y nat) nat {
   182		switch {
   183		case len(x) == 0:
   184			return z.set(y)
   185		case len(y) == 0:
   186			return z.set(x)
   187		}
   188		return z.mul(x, y)
   189	}
   190	
   191	// scaleDenom computes x*f.
   192	// If f == 0 (zero value of denominator), the result is (a copy of) x.
   193	func scaleDenom(x *Int, f nat) *Int {
   194		var z Int
   195		if len(f) == 0 {
   196			return z.Set(x)
   197		}
   198		z.abs = z.abs.mul(x.abs, f)
   199		z.neg = x.neg
   200		return &z
   201	}
   202	
   203	// Cmp compares x and y and returns:
   204	//
   205	//   -1 if x <  y
   206	//    0 if x == y
   207	//   +1 if x >  y
   208	//
   209	func (x *Rat) Cmp(y *Rat) int {
   210		return scaleDenom(&x.a, y.b).Cmp(scaleDenom(&y.a, x.b))
   211	}
   212	
   213	// Add sets z to the sum x+y and returns z.
   214	func (z *Rat) Add(x, y *Rat) *Rat {
   215		a1 := scaleDenom(&x.a, y.b)
   216		a2 := scaleDenom(&y.a, x.b)
   217		z.a.Add(a1, a2)
   218		z.b = mulDenom(z.b, x.b, y.b)
   219		return z.norm()
   220	}
   221	
   222	// Sub sets z to the difference x-y and returns z.
   223	func (z *Rat) Sub(x, y *Rat) *Rat {
   224		a1 := scaleDenom(&x.a, y.b)
   225		a2 := scaleDenom(&y.a, x.b)
   226		z.a.Sub(a1, a2)
   227		z.b = mulDenom(z.b, x.b, y.b)
   228		return z.norm()
   229	}
   230	
   231	// Mul sets z to the product x*y and returns z.
   232	func (z *Rat) Mul(x, y *Rat) *Rat {
   233		z.a.Mul(&x.a, &y.a)
   234		z.b = mulDenom(z.b, x.b, y.b)
   235		return z.norm()
   236	}
   237	
   238	// Quo sets z to the quotient x/y and returns z.
   239	// If y == 0, a division-by-zero run-time panic occurs.
   240	func (z *Rat) Quo(x, y *Rat) *Rat {
   241		if len(y.a.abs) == 0 {
   242			panic("division by zero")
   243		}
   244		a := scaleDenom(&x.a, y.b)
   245		b := scaleDenom(&y.a, x.b)
   246		z.a.abs = a.abs
   247		z.b = b.abs
   248		z.a.neg = a.neg != b.neg
   249		return z.norm()
   250	}
   251	
   252	func ratTok(ch rune) bool {
   253		return strings.IndexRune("+-/0123456789.eE", ch) >= 0
   254	}
   255	
   256	// Scan is a support routine for fmt.Scanner. It accepts the formats
   257	// 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent.
   258	func (z *Rat) Scan(s fmt.ScanState, ch rune) error {
   259		tok, err := s.Token(true, ratTok)
   260		if err != nil {
   261			return err
   262		}
   263		if strings.IndexRune("efgEFGv", ch) < 0 {
   264			return errors.New("Rat.Scan: invalid verb")
   265		}
   266		if _, ok := z.SetString(string(tok)); !ok {
   267			return errors.New("Rat.Scan: invalid syntax")
   268		}
   269		return nil
   270	}
   271	
   272	// SetString sets z to the value of s and returns z and a boolean indicating
   273	// success. s can be given as a fraction "a/b" or as a floating-point number
   274	// optionally followed by an exponent. If the operation failed, the value of
   275	// z is undefined but the returned value is nil.
   276	func (z *Rat) SetString(s string) (*Rat, bool) {
   277		if len(s) == 0 {
   278			return nil, false
   279		}
   280	
   281		// check for a quotient
   282		sep := strings.Index(s, "/")
   283		if sep >= 0 {
   284			if _, ok := z.a.SetString(s[0:sep], 10); !ok {
   285				return nil, false
   286			}
   287			s = s[sep+1:]
   288			var err error
   289			if z.b, _, err = z.b.scan(strings.NewReader(s), 10); err != nil {
   290				return nil, false
   291			}
   292			return z.norm(), true
   293		}
   294	
   295		// check for a decimal point
   296		sep = strings.Index(s, ".")
   297		// check for an exponent
   298		e := strings.IndexAny(s, "eE")
   299		var exp Int
   300		if e >= 0 {
   301			if e < sep {
   302				// The E must come after the decimal point.
   303				return nil, false
   304			}
   305			if _, ok := exp.SetString(s[e+1:], 10); !ok {
   306				return nil, false
   307			}
   308			s = s[0:e]
   309		}
   310		if sep >= 0 {
   311			s = s[0:sep] + s[sep+1:]
   312			exp.Sub(&exp, NewInt(int64(len(s)-sep)))
   313		}
   314	
   315		if _, ok := z.a.SetString(s, 10); !ok {
   316			return nil, false
   317		}
   318		powTen := nat(nil).expNN(natTen, exp.abs, nil)
   319		if exp.neg {
   320			z.b = powTen
   321			z.norm()
   322		} else {
   323			z.a.abs = z.a.abs.mul(z.a.abs, powTen)
   324			z.b = z.b.make(0)
   325		}
   326	
   327		return z, true
   328	}
   329	
   330	// String returns a string representation of z in the form "a/b" (even if b == 1).
   331	func (x *Rat) String() string {
   332		s := "/1"
   333		if len(x.b) != 0 {
   334			s = "/" + x.b.decimalString()
   335		}
   336		return x.a.String() + s
   337	}
   338	
   339	// RatString returns a string representation of z in the form "a/b" if b != 1,
   340	// and in the form "a" if b == 1.
   341	func (x *Rat) RatString() string {
   342		if x.IsInt() {
   343			return x.a.String()
   344		}
   345		return x.String()
   346	}
   347	
   348	// FloatString returns a string representation of z in decimal form with prec
   349	// digits of precision after the decimal point and the last digit rounded.
   350	func (x *Rat) FloatString(prec int) string {
   351		if x.IsInt() {
   352			s := x.a.String()
   353			if prec > 0 {
   354				s += "." + strings.Repeat("0", prec)
   355			}
   356			return s
   357		}
   358		// x.b != 0
   359	
   360		q, r := nat(nil).div(nat(nil), x.a.abs, x.b)
   361	
   362		p := natOne
   363		if prec > 0 {
   364			p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil)
   365		}
   366	
   367		r = r.mul(r, p)
   368		r, r2 := r.div(nat(nil), r, x.b)
   369	
   370		// see if we need to round up
   371		r2 = r2.add(r2, r2)
   372		if x.b.cmp(r2) <= 0 {
   373			r = r.add(r, natOne)
   374			if r.cmp(p) >= 0 {
   375				q = nat(nil).add(q, natOne)
   376				r = nat(nil).sub(r, p)
   377			}
   378		}
   379	
   380		s := q.decimalString()
   381		if x.a.neg {
   382			s = "-" + s
   383		}
   384	
   385		if prec > 0 {
   386			rs := r.decimalString()
   387			leadingZeros := prec - len(rs)
   388			s += "." + strings.Repeat("0", leadingZeros) + rs
   389		}
   390	
   391		return s
   392	}
   393	
   394	// Gob codec version. Permits backward-compatible changes to the encoding.
   395	const ratGobVersion byte = 1
   396	
   397	// GobEncode implements the gob.GobEncoder interface.
   398	func (x *Rat) GobEncode() ([]byte, error) {
   399		buf := make([]byte, 1+4+(len(x.a.abs)+len(x.b))*_S) // extra bytes for version and sign bit (1), and numerator length (4)
   400		i := x.b.bytes(buf)
   401		j := x.a.abs.bytes(buf[0:i])
   402		n := i - j
   403		if int(uint32(n)) != n {
   404			// this should never happen
   405			return nil, errors.New("Rat.GobEncode: numerator too large")
   406		}
   407		binary.BigEndian.PutUint32(buf[j-4:j], uint32(n))
   408		j -= 1 + 4
   409		b := ratGobVersion << 1 // make space for sign bit
   410		if x.a.neg {
   411			b |= 1
   412		}
   413		buf[j] = b
   414		return buf[j:], nil
   415	}
   416	
   417	// GobDecode implements the gob.GobDecoder interface.
   418	func (z *Rat) GobDecode(buf []byte) error {
   419		if len(buf) == 0 {
   420			return errors.New("Rat.GobDecode: no data")
   421		}
   422		b := buf[0]
   423		if b>>1 != ratGobVersion {
   424			return errors.New(fmt.Sprintf("Rat.GobDecode: encoding version %d not supported", b>>1))
   425		}
   426		const j = 1 + 4
   427		i := j + binary.BigEndian.Uint32(buf[j-4:j])
   428		z.a.neg = b&1 != 0
   429		z.a.abs = z.a.abs.setBytes(buf[j:i])
   430		z.b = z.b.setBytes(buf[i:])
   431		return nil
   432	}