1 files changed, 205 insertions, 0 deletions
diff --git a/src/pkg/exp/bignum/rational.go b/src/pkg/exp/bignum/rational.go
new file mode 100644
index 000000000..378585e5f
--- /dev/null
+++ b/src/pkg/exp/bignum/rational.go
@@ -0,0 +1,205 @@
+// 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
+}