| // Copyright 2010 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 rational numbers. |
| |
| package big |
| |
| import ( |
| "encoding/binary" |
| "fmt" |
| "os" |
| "strings" |
| ) |
| |
| // A Rat represents a quotient a/b of arbitrary precision. |
| // The zero value for a Rat represents the value 0. |
| type Rat struct { |
| a Int |
| b nat // len(b) == 0 acts like b == 1 |
| } |
| |
| // NewRat creates a new Rat with numerator a and denominator b. |
| func NewRat(a, b int64) *Rat { |
| return new(Rat).SetFrac64(a, b) |
| } |
| |
| // SetFrac sets z to a/b and returns z. |
| func (z *Rat) SetFrac(a, b *Int) *Rat { |
| z.a.neg = a.neg != b.neg |
| babs := b.abs |
| if len(babs) == 0 { |
| panic("division by zero") |
| } |
| if &z.a == b || alias(z.a.abs, babs) { |
| babs = nat{}.set(babs) // make a copy |
| } |
| z.a.abs = z.a.abs.set(a.abs) |
| z.b = z.b.set(babs) |
| return z.norm() |
| } |
| |
| // SetFrac64 sets z to a/b and returns z. |
| func (z *Rat) SetFrac64(a, b int64) *Rat { |
| z.a.SetInt64(a) |
| if b == 0 { |
| panic("division by zero") |
| } |
| if b < 0 { |
| b = -b |
| z.a.neg = !z.a.neg |
| } |
| z.b = z.b.setUint64(uint64(b)) |
| return z.norm() |
| } |
| |
| // SetInt sets z to x (by making a copy of x) and returns z. |
| func (z *Rat) SetInt(x *Int) *Rat { |
| z.a.Set(x) |
| z.b = z.b.make(0) |
| return z |
| } |
| |
| // SetInt64 sets z to x and returns z. |
| func (z *Rat) SetInt64(x int64) *Rat { |
| z.a.SetInt64(x) |
| z.b = z.b.make(0) |
| return z |
| } |
| |
| // Set sets z to x (by making a copy of x) and returns z. |
| func (z *Rat) Set(x *Rat) *Rat { |
| if z != x { |
| z.a.Set(&x.a) |
| z.b = z.b.set(x.b) |
| } |
| return z |
| } |
| |
| // Abs sets z to |x| (the absolute value of x) and returns z. |
| func (z *Rat) Abs(x *Rat) *Rat { |
| z.Set(x) |
| z.a.neg = false |
| return z |
| } |
| |
| // Neg sets z to -x and returns z. |
| func (z *Rat) Neg(x *Rat) *Rat { |
| z.Set(x) |
| z.a.neg = len(z.a.abs) > 0 && !z.a.neg // 0 has no sign |
| return z |
| } |
| |
| // Inv sets z to 1/x and returns z. |
| func (z *Rat) Inv(x *Rat) *Rat { |
| if len(x.a.abs) == 0 { |
| panic("division by zero") |
| } |
| z.Set(x) |
| a := z.b |
| if len(a) == 0 { |
| a = a.setWord(1) // materialize numerator |
| } |
| b := z.a.abs |
| if b.cmp(natOne) == 0 { |
| b = b.make(0) // normalize denominator |
| } |
| z.a.abs, z.b = a, b // sign doesn't change |
| return z |
| } |
| |
| // Sign returns: |
| // |
| // -1 if x < 0 |
| // 0 if x == 0 |
| // +1 if x > 0 |
| // |
| func (x *Rat) Sign() int { |
| return x.a.Sign() |
| } |
| |
| // IsInt returns true if the denominator of x is 1. |
| func (x *Rat) IsInt() bool { |
| return len(x.b) == 0 || x.b.cmp(natOne) == 0 |
| } |
| |
| // Num returns the numerator of x; it may be <= 0. |
| // The result is a reference to x's numerator; it |
| // may change if a new value is assigned to x. |
| func (x *Rat) Num() *Int { |
| return &x.a |
| } |
| |
| // Denom returns the denominator of x; it is always > 0. |
| // The result is a reference to x's denominator; it |
| // may change if a new value is assigned to x. |
| func (x *Rat) Denom() *Int { |
| if len(x.b) == 0 { |
| return &Int{abs: nat{1}} |
| } |
| return &Int{abs: x.b} |
| } |
| |
| func gcd(x, y nat) nat { |
| // Euclidean algorithm. |
| var a, b nat |
| a = a.set(x) |
| b = b.set(y) |
| for len(b) != 0 { |
| var q, r nat |
| _, r = q.div(r, a, b) |
| a = b |
| b = r |
| } |
| return a |
| } |
| |
| func (z *Rat) norm() *Rat { |
| switch { |
| case len(z.a.abs) == 0: |
| // z == 0 - normalize sign and denominator |
| z.a.neg = false |
| z.b = z.b.make(0) |
| case len(z.b) == 0: |
| // z is normalized int - nothing to do |
| case z.b.cmp(natOne) == 0: |
| // z is int - normalize denominator |
| z.b = z.b.make(0) |
| default: |
| if f := gcd(z.a.abs, z.b); f.cmp(natOne) != 0 { |
| z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f) |
| z.b, _ = z.b.div(nil, z.b, f) |
| } |
| } |
| return z |
| } |
| |
| // mulDenom sets z to the denominator product x*y (by taking into |
| // account that 0 values for x or y must be interpreted as 1) and |
| // returns z. |
| func mulDenom(z, x, y nat) nat { |
| switch { |
| case len(x) == 0: |
| return z.set(y) |
| case len(y) == 0: |
| return z.set(x) |
| } |
| return z.mul(x, y) |
| } |
| |
| // scaleDenom computes x*f. |
| // If f == 0 (zero value of denominator), the result is (a copy of) x. |
| func scaleDenom(x *Int, f nat) *Int { |
| var z Int |
| if len(f) == 0 { |
| return z.Set(x) |
| } |
| z.abs = z.abs.mul(x.abs, f) |
| z.neg = x.neg |
| return &z |
| } |
| |
| // Cmp compares x and y and returns: |
| // |
| // -1 if x < y |
| // 0 if x == y |
| // +1 if x > y |
| // |
| func (x *Rat) Cmp(y *Rat) int { |
| return scaleDenom(&x.a, y.b).Cmp(scaleDenom(&y.a, x.b)) |
| } |
| |
| // Add sets z to the sum x+y and returns z. |
| func (z *Rat) Add(x, y *Rat) *Rat { |
| a1 := scaleDenom(&x.a, y.b) |
| a2 := scaleDenom(&y.a, x.b) |
| z.a.Add(a1, a2) |
| z.b = mulDenom(z.b, x.b, y.b) |
| return z.norm() |
| } |
| |
| // Sub sets z to the difference x-y and returns z. |
| func (z *Rat) Sub(x, y *Rat) *Rat { |
| a1 := scaleDenom(&x.a, y.b) |
| a2 := scaleDenom(&y.a, x.b) |
| z.a.Sub(a1, a2) |
| z.b = mulDenom(z.b, x.b, y.b) |
| return z.norm() |
| } |
| |
| // Mul sets z to the product x*y and returns z. |
| func (z *Rat) Mul(x, y *Rat) *Rat { |
| z.a.Mul(&x.a, &y.a) |
| z.b = mulDenom(z.b, x.b, y.b) |
| return z.norm() |
| } |
| |
| // Quo sets z to the quotient x/y and returns z. |
| // If y == 0, a division-by-zero run-time panic occurs. |
| func (z *Rat) Quo(x, y *Rat) *Rat { |
| if len(y.a.abs) == 0 { |
| panic("division by zero") |
| } |
| a := scaleDenom(&x.a, y.b) |
| b := scaleDenom(&y.a, x.b) |
| z.a.abs = a.abs |
| z.b = b.abs |
| z.a.neg = a.neg != b.neg |
| return z.norm() |
| } |
| |
| func ratTok(ch rune) bool { |
| return strings.IndexRune("+-/0123456789.eE", ch) >= 0 |
| } |
| |
| // Scan is a support routine for fmt.Scanner. It accepts the formats |
| // 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent. |
| func (z *Rat) Scan(s fmt.ScanState, ch rune) os.Error { |
| tok, err := s.Token(true, ratTok) |
| if err != nil { |
| return err |
| } |
| if strings.IndexRune("efgEFGv", ch) < 0 { |
| return os.NewError("Rat.Scan: invalid verb") |
| } |
| if _, ok := z.SetString(string(tok)); !ok { |
| return os.NewError("Rat.Scan: invalid syntax") |
| } |
| return nil |
| } |
| |
| // SetString sets z to the value of s and returns z and a boolean indicating |
| // success. s can be given as a fraction "a/b" or as a floating-point number |
| // optionally followed by an exponent. If the operation failed, the value of |
| // z is undefined but the returned value is nil. |
| func (z *Rat) SetString(s string) (*Rat, bool) { |
| if len(s) == 0 { |
| return nil, false |
| } |
| |
| // check for a quotient |
| sep := strings.Index(s, "/") |
| if sep >= 0 { |
| if _, ok := z.a.SetString(s[0:sep], 10); !ok { |
| return nil, false |
| } |
| s = s[sep+1:] |
| var err os.Error |
| if z.b, _, err = z.b.scan(strings.NewReader(s), 10); err != nil { |
| return nil, false |
| } |
| return z.norm(), true |
| } |
| |
| // check for a decimal point |
| sep = strings.Index(s, ".") |
| // check for an exponent |
| e := strings.IndexAny(s, "eE") |
| var exp Int |
| if e >= 0 { |
| if e < sep { |
| // The E must come after the decimal point. |
| return nil, false |
| } |
| if _, ok := exp.SetString(s[e+1:], 10); !ok { |
| return nil, false |
| } |
| s = s[0:e] |
| } |
| if sep >= 0 { |
| s = s[0:sep] + s[sep+1:] |
| exp.Sub(&exp, NewInt(int64(len(s)-sep))) |
| } |
| |
| if _, ok := z.a.SetString(s, 10); !ok { |
| return nil, false |
| } |
| powTen := nat{}.expNN(natTen, exp.abs, nil) |
| if exp.neg { |
| z.b = powTen |
| z.norm() |
| } else { |
| z.a.abs = z.a.abs.mul(z.a.abs, powTen) |
| z.b = z.b.make(0) |
| } |
| |
| return z, true |
| } |
| |
| // String returns a string representation of z in the form "a/b" (even if b == 1). |
| func (z *Rat) String() string { |
| s := "/1" |
| if len(z.b) != 0 { |
| s = "/" + z.b.decimalString() |
| } |
| return z.a.String() + s |
| } |
| |
| // RatString returns a string representation of z in the form "a/b" if b != 1, |
| // and in the form "a" if b == 1. |
| func (z *Rat) RatString() string { |
| if z.IsInt() { |
| return z.a.String() |
| } |
| return z.String() |
| } |
| |
| // FloatString returns a string representation of z in decimal form with prec |
| // digits of precision after the decimal point and the last digit rounded. |
| func (z *Rat) FloatString(prec int) string { |
| if z.IsInt() { |
| s := z.a.String() |
| if prec > 0 { |
| s += "." + strings.Repeat("0", prec) |
| } |
| return s |
| } |
| // z.b != 0 |
| |
| q, r := nat{}.div(nat{}, z.a.abs, z.b) |
| |
| p := natOne |
| if prec > 0 { |
| p = nat{}.expNN(natTen, nat{}.setUint64(uint64(prec)), nil) |
| } |
| |
| r = r.mul(r, p) |
| r, r2 := r.div(nat{}, r, z.b) |
| |
| // see if we need to round up |
| r2 = r2.add(r2, r2) |
| if z.b.cmp(r2) <= 0 { |
| r = r.add(r, natOne) |
| if r.cmp(p) >= 0 { |
| q = nat{}.add(q, natOne) |
| r = nat{}.sub(r, p) |
| } |
| } |
| |
| s := q.decimalString() |
| if z.a.neg { |
| s = "-" + s |
| } |
| |
| if prec > 0 { |
| rs := r.decimalString() |
| leadingZeros := prec - len(rs) |
| s += "." + strings.Repeat("0", leadingZeros) + rs |
| } |
| |
| return s |
| } |
| |
| // Gob codec version. Permits backward-compatible changes to the encoding. |
| const ratGobVersion byte = 1 |
| |
| // GobEncode implements the gob.GobEncoder interface. |
| func (z *Rat) GobEncode() ([]byte, os.Error) { |
| buf := make([]byte, 1+4+(len(z.a.abs)+len(z.b))*_S) // extra bytes for version and sign bit (1), and numerator length (4) |
| i := z.b.bytes(buf) |
| j := z.a.abs.bytes(buf[0:i]) |
| n := i - j |
| if int(uint32(n)) != n { |
| // this should never happen |
| return nil, os.NewError("Rat.GobEncode: numerator too large") |
| } |
| binary.BigEndian.PutUint32(buf[j-4:j], uint32(n)) |
| j -= 1 + 4 |
| b := ratGobVersion << 1 // make space for sign bit |
| if z.a.neg { |
| b |= 1 |
| } |
| buf[j] = b |
| return buf[j:], nil |
| } |
| |
| // GobDecode implements the gob.GobDecoder interface. |
| func (z *Rat) GobDecode(buf []byte) os.Error { |
| if len(buf) == 0 { |
| return os.NewError("Rat.GobDecode: no data") |
| } |
| b := buf[0] |
| if b>>1 != ratGobVersion { |
| return os.NewError(fmt.Sprintf("Rat.GobDecode: encoding version %d not supported", b>>1)) |
| } |
| const j = 1 + 4 |
| i := j + binary.BigEndian.Uint32(buf[j-4:j]) |
| z.a.neg = b&1 != 0 |
| z.a.abs = z.a.abs.setBytes(buf[j:i]) |
| z.b = z.b.setBytes(buf[i:]) |
| return nil |
| } |