| // Copyright 2009 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. |
| |
| // Rational numbers |
| |
| package bignum |
| |
| import "fmt" |
| |
| |
| // Rational represents a quotient a/b of arbitrary precision. |
| // |
| type Rational struct { |
| a *Integer // numerator |
| b Natural // denominator |
| } |
| |
| |
| // MakeRat makes a rational number given a numerator a and a denominator b. |
| // |
| func MakeRat(a *Integer, b Natural) *Rational { |
| f := a.mant.Gcd(b) // f > 0 |
| if f.Cmp(Nat(1)) != 0 { |
| a = MakeInt(a.sign, a.mant.Div(f)) |
| b = b.Div(f) |
| } |
| return &Rational{a, b} |
| } |
| |
| |
| // Rat creates a small rational number with value a0/b0. |
| // |
| func Rat(a0 int64, b0 int64) *Rational { |
| a, b := Int(a0), Int(b0) |
| if b.sign { |
| a = a.Neg() |
| } |
| return MakeRat(a, b.mant) |
| } |
| |
| |
| // Value returns the numerator and denominator of x. |
| // |
| func (x *Rational) Value() (numerator *Integer, denominator Natural) { |
| return x.a, x.b |
| } |
| |
| |
| // Predicates |
| |
| // IsZero returns true iff x == 0. |
| // |
| func (x *Rational) IsZero() bool { return x.a.IsZero() } |
| |
| |
| // IsNeg returns true iff x < 0. |
| // |
| func (x *Rational) IsNeg() bool { return x.a.IsNeg() } |
| |
| |
| // IsPos returns true iff x > 0. |
| // |
| func (x *Rational) IsPos() bool { return x.a.IsPos() } |
| |
| |
| // IsInt returns true iff x can be written with a denominator 1 |
| // in the form x == x'/1; i.e., if x is an integer value. |
| // |
| func (x *Rational) IsInt() bool { return x.b.Cmp(Nat(1)) == 0 } |
| |
| |
| // Operations |
| |
| // Neg returns the negated value of x. |
| // |
| func (x *Rational) Neg() *Rational { return MakeRat(x.a.Neg(), x.b) } |
| |
| |
| // Add returns the sum x + y. |
| // |
| func (x *Rational) Add(y *Rational) *Rational { |
| return MakeRat((x.a.MulNat(y.b)).Add(y.a.MulNat(x.b)), x.b.Mul(y.b)) |
| } |
| |
| |
| // Sub returns the difference x - y. |
| // |
| func (x *Rational) Sub(y *Rational) *Rational { |
| return MakeRat((x.a.MulNat(y.b)).Sub(y.a.MulNat(x.b)), x.b.Mul(y.b)) |
| } |
| |
| |
| // Mul returns the product x * y. |
| // |
| func (x *Rational) Mul(y *Rational) *Rational { return MakeRat(x.a.Mul(y.a), x.b.Mul(y.b)) } |
| |
| |
| // Quo returns the quotient x / y for y != 0. |
| // If y == 0, a division-by-zero run-time error occurs. |
| // |
| func (x *Rational) Quo(y *Rational) *Rational { |
| a := x.a.MulNat(y.b) |
| b := y.a.MulNat(x.b) |
| if b.IsNeg() { |
| a = a.Neg() |
| } |
| return MakeRat(a, b.mant) |
| } |
| |
| |
| // Cmp compares x and y. The result is an int value |
| // |
| // < 0 if x < y |
| // == 0 if x == y |
| // > 0 if x > y |
| // |
| func (x *Rational) Cmp(y *Rational) int { return (x.a.MulNat(y.b)).Cmp(y.a.MulNat(x.b)) } |
| |
| |
| // ToString converts x to a string for a given base, with 2 <= base <= 16. |
| // The string representation is of the form "n" if x is an integer; otherwise |
| // it is of form "n/d". |
| // |
| func (x *Rational) ToString(base uint) string { |
| s := x.a.ToString(base) |
| if !x.IsInt() { |
| s += "/" + x.b.ToString(base) |
| } |
| return s |
| } |
| |
| |
| // String converts x to its decimal string representation. |
| // x.String() is the same as x.ToString(10). |
| // |
| func (x *Rational) String() string { return x.ToString(10) } |
| |
| |
| // Format is a support routine for fmt.Formatter. It accepts |
| // the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal). |
| // |
| func (x *Rational) Format(h fmt.State, c int) { fmt.Fprintf(h, "%s", x.ToString(fmtbase(c))) } |
| |
| |
| // RatFromString returns the rational number corresponding to the |
| // longest possible prefix of s representing a rational number in a |
| // given conversion base, the actual conversion base used, and the |
| // prefix length. The syntax of a rational number is: |
| // |
| // rational = mantissa [exponent] . |
| // mantissa = integer ('/' natural | '.' natural) . |
| // exponent = ('e'|'E') integer . |
| // |
| // If the base argument is 0, the string prefix determines the actual |
| // conversion base for the mantissa. A prefix of ``0x'' or ``0X'' selects |
| // base 16; the ``0'' prefix selects base 8. Otherwise the selected base is 10. |
| // If the mantissa is represented via a division, both the numerator and |
| // denominator may have different base prefixes; in that case the base of |
| // of the numerator is returned. If the mantissa contains a decimal point, |
| // the base for the fractional part is the same as for the part before the |
| // decimal point and the fractional part does not accept a base prefix. |
| // The base for the exponent is always 10. |
| // |
| func RatFromString(s string, base uint) (*Rational, uint, int) { |
| // read numerator |
| a, abase, alen := IntFromString(s, base) |
| b := Nat(1) |
| |
| // read denominator or fraction, if any |
| var blen int |
| if alen < len(s) { |
| ch := s[alen] |
| if ch == '/' { |
| alen++ |
| b, base, blen = NatFromString(s[alen:], base) |
| } else if ch == '.' { |
| alen++ |
| b, base, blen = NatFromString(s[alen:], abase) |
| assert(base == abase) |
| f := Nat(uint64(base)).Pow(uint(blen)) |
| a = MakeInt(a.sign, a.mant.Mul(f).Add(b)) |
| b = f |
| } |
| } |
| |
| // read exponent, if any |
| rlen := alen + blen |
| if rlen < len(s) { |
| ch := s[rlen] |
| if ch == 'e' || ch == 'E' { |
| rlen++ |
| e, _, elen := IntFromString(s[rlen:], 10) |
| rlen += elen |
| m := Nat(10).Pow(uint(e.mant.Value())) |
| if e.sign { |
| b = b.Mul(m) |
| } else { |
| a = a.MulNat(m) |
| } |
| } |
| } |
| |
| return MakeRat(a, b), base, rlen |
| } |