1 files changed, 500 insertions, 0 deletions
diff --git a/src/pkg/bignum/integer.go b/src/pkg/bignum/integer.go
new file mode 100644
index 000000000..f3c111d0b
--- /dev/null
+++ b/src/pkg/bignum/integer.go
@@ -0,0 +1,500 @@
+// 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.
+
+// Integer numbers
+//
+// Integers are normalized if the mantissa is normalized and the sign is
+// false for mant == 0. Use MakeInt to create normalized Integers.
+
+package bignum
+
+import "bignum"
+import "fmt"
+
+
+// Integer represents a signed integer value of arbitrary precision.
+//
+type Integer struct {
+	sign bool;
+	mant Natural;
+}
+
+
+// MakeInt makes an integer given a sign and a mantissa.
+// The number is positive (>= 0) if sign is false or the
+// mantissa is zero; it is negative otherwise.
+//
+func MakeInt(sign bool, mant Natural) *Integer {
+	if mant.IsZero() {
+		sign = false;  // normalize
+	}
+	return &Integer{sign, mant};
+}
+
+
+// Int creates a small integer with value x.
+//
+func Int(x int64) *Integer {
+	var ux uint64;
+	if x < 0 {
+		// For the most negative x, -x == x, and
+		// the bit pattern has the correct value.
+		ux = uint64(-x);
+	} else {
+		ux = uint64(x);
+	}
+	return MakeInt(x < 0, Nat(ux));
+}
+
+
+// Value returns the value of x, if x fits into an int64;
+// otherwise the result is undefined.
+//
+func (x *Integer) Value() int64 {
+	z := int64(x.mant.Value());
+	if x.sign {
+		z = -z;
+	}
+	return z;
+}
+
+
+// Abs returns the absolute value of x.
+//
+func (x *Integer) Abs() Natural {
+	return x.mant;
+}
+
+
+// Predicates
+
+// IsEven returns true iff x is divisible by 2.
+//
+func (x *Integer) IsEven() bool {
+	return x.mant.IsEven();
+}
+
+
+// IsOdd returns true iff x is not divisible by 2.
+//
+func (x *Integer) IsOdd() bool {
+	return x.mant.IsOdd();
+}
+
+
+// IsZero returns true iff x == 0.
+//
+func (x *Integer) IsZero() bool {
+	return x.mant.IsZero();
+}
+
+
+// IsNeg returns true iff x < 0.
+//
+func (x *Integer) IsNeg() bool {
+	return x.sign && !x.mant.IsZero()
+}
+
+
+// IsPos returns true iff x >= 0.
+//
+func (x *Integer) IsPos() bool {
+	return !x.sign && !x.mant.IsZero()
+}
+
+
+// Operations
+
+// Neg returns the negated value of x.
+//
+func (x *Integer) Neg() *Integer {
+	return MakeInt(!x.sign, x.mant);
+}
+
+
+// Add returns the sum x + y.
+//
+func (x *Integer) Add(y *Integer) *Integer {
+	var z *Integer;
+	if x.sign == y.sign {
+		// x + y == x + y
+		// (-x) + (-y) == -(x + y)
+		z = MakeInt(x.sign, x.mant.Add(y.mant));
+	} else {
+		// x + (-y) == x - y == -(y - x)
+		// (-x) + y == y - x == -(x - y)
+		if x.mant.Cmp(y.mant) >= 0 {
+			z = MakeInt(false, x.mant.Sub(y.mant));
+		} else {
+			z = MakeInt(true, y.mant.Sub(x.mant));
+		}
+	}
+	if x.sign {
+		z.sign = !z.sign;
+	}
+	return z;
+}
+
+
+// Sub returns the difference x - y.
+//
+func (x *Integer) Sub(y *Integer) *Integer {
+	var z *Integer;
+	if x.sign != y.sign {
+		// x - (-y) == x + y
+		// (-x) - y == -(x + y)
+		z = MakeInt(false, x.mant.Add(y.mant));
+	} else {
+		// x - y == x - y == -(y - x)
+		// (-x) - (-y) == y - x == -(x - y)
+		if x.mant.Cmp(y.mant) >= 0 {
+			z = MakeInt(false, x.mant.Sub(y.mant));
+		} else {
+			z = MakeInt(true, y.mant.Sub(x.mant));
+		}
+	}
+	if x.sign {
+		z.sign = !z.sign;
+	}
+	return z;
+}
+
+
+// Mul returns the product x * y.
+//
+func (x *Integer) Mul(y *Integer) *Integer {
+	// x * y == x * y
+	// x * (-y) == -(x * y)
+	// (-x) * y == -(x * y)
+	// (-x) * (-y) == x * y
+	return MakeInt(x.sign != y.sign, x.mant.Mul(y.mant));
+}
+
+
+// MulNat returns the product x * y, where y is a (unsigned) natural number.
+//
+func (x *Integer) MulNat(y Natural) *Integer {
+	// x * y == x * y
+	// (-x) * y == -(x * y)
+	return MakeInt(x.sign, x.mant.Mul(y));
+}
+
+
+// Quo returns the quotient q = x / y for y != 0.
+// If y == 0, a division-by-zero run-time error occurs.
+//
+// Quo and Rem implement T-division and modulus (like C99):
+//
+//   q = x.Quo(y) = trunc(x/y)  (truncation towards zero)
+//   r = x.Rem(y) = x - y*q
+//
+// (Daan Leijen, ``Division and Modulus for Computer Scientists''.)
+//
+func (x *Integer) Quo(y *Integer) *Integer {
+	// x / y == x / y
+	// x / (-y) == -(x / y)
+	// (-x) / y == -(x / y)
+	// (-x) / (-y) == x / y
+	return MakeInt(x.sign != y.sign, x.mant.Div(y.mant));
+}
+
+
+// Rem returns the remainder r of the division x / y for y != 0,
+// with r = x - y*x.Quo(y). Unless r is zero, its sign corresponds
+// to the sign of x.
+// If y == 0, a division-by-zero run-time error occurs.
+//
+func (x *Integer) Rem(y *Integer) *Integer {
+	// x % y == x % y
+	// x % (-y) == x % y
+	// (-x) % y == -(x % y)
+	// (-x) % (-y) == -(x % y)
+	return MakeInt(x.sign, x.mant.Mod(y.mant));
+}
+
+
+// QuoRem returns the pair (x.Quo(y), x.Rem(y)) for y != 0.
+// If y == 0, a division-by-zero run-time error occurs.
+//
+func (x *Integer) QuoRem(y *Integer) (*Integer, *Integer) {
+	q, r := x.mant.DivMod(y.mant);
+	return MakeInt(x.sign != y.sign, q), MakeInt(x.sign, r);
+}
+
+
+// Div returns the quotient q = x / y for y != 0.
+// If y == 0, a division-by-zero run-time error occurs.
+//
+// Div and Mod implement Euclidian division and modulus:
+//
+//   q = x.Div(y)
+//   r = x.Mod(y) with: 0 <= r < |q| and: y = x*q + r
+//
+// (Raymond T. Boute, ``The Euclidian definition of the functions
+// div and mod''. ACM Transactions on Programming Languages and
+// Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
+// ACM press.)
+//
+func (x *Integer) Div(y *Integer) *Integer {
+	q, r := x.QuoRem(y);
+	if r.IsNeg() {
+		if y.IsPos() {
+			q = q.Sub(Int(1));
+		} else {
+			q = q.Add(Int(1));
+		}
+	}
+	return q;
+}
+
+
+// Mod returns the modulus r of the division x / y for y != 0,
+// with r = x - y*x.Div(y). r is always positive.
+// If y == 0, a division-by-zero run-time error occurs.
+//
+func (x *Integer) Mod(y *Integer) *Integer {
+	r := x.Rem(y);
+	if r.IsNeg() {
+		if y.IsPos() {
+			r = r.Add(y);
+		} else {
+			r = r.Sub(y);
+		}
+	}
+	return r;
+}
+
+
+// DivMod returns the pair (x.Div(y), x.Mod(y)).
+//
+func (x *Integer) DivMod(y *Integer) (*Integer, *Integer) {
+	q, r := x.QuoRem(y);
+	if r.IsNeg() {
+		if y.IsPos() {
+			q = q.Sub(Int(1));
+			r = r.Add(y);
+		} else {
+			q = q.Add(Int(1));
+			r = r.Sub(y);
+		}
+	}
+	return q, r;
+}
+
+
+// Shl implements ``shift left'' x << s. It returns x * 2^s.
+//
+func (x *Integer) Shl(s uint) *Integer {
+	return MakeInt(x.sign, x.mant.Shl(s));
+}
+
+
+// The bitwise operations on integers are defined on the 2's-complement
+// representation of integers. From
+//
+//   -x == ^x + 1  (1)  2's complement representation
+//
+// follows:
+//
+//   -(x) == ^(x) + 1
+//   -(-x) == ^(-x) + 1
+//   x-1 == ^(-x)
+//   ^(x-1) == -x  (2)
+//
+// Using (1) and (2), operations on negative integers of the form -x are
+// converted to operations on negated positive integers of the form ~(x-1).
+
+
+// Shr implements ``shift right'' x >> s. It returns x / 2^s.
+//
+func (x *Integer) Shr(s uint) *Integer {
+	if x.sign {
+		// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
+		return MakeInt(true, x.mant.Sub(nat[1]).Shr(s).Add(nat[1]));
+	}
+	
+	return MakeInt(false, x.mant.Shr(s));
+}
+
+
+// Not returns the ``bitwise not'' ^x for the 2's-complement representation of x.
+func (x *Integer) Not() *Integer {
+	if x.sign {
+		// ^(-x) == ^(^(x-1)) == x-1
+		return MakeInt(false, x.mant.Sub(nat[1]));
+	}
+
+	// ^x == -x-1 == -(x+1)
+	return MakeInt(true, x.mant.Add(nat[1]));
+}
+
+
+// And returns the ``bitwise and'' x & y for the 2's-complement representation of x and y.
+//
+func (x *Integer) And(y *Integer) *Integer {
+	if x.sign == y.sign {
+		if x.sign {
+			// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
+			return MakeInt(true, x.mant.Sub(nat[1]).Or(y.mant.Sub(nat[1])).Add(nat[1]));
+		}
+
+		// x & y == x & y
+		return MakeInt(false, x.mant.And(y.mant));
+	}
+
+	// x.sign != y.sign
+	if x.sign {
+		x, y = y, x;  // & is symmetric
+	}
+
+	// x & (-y) == x & ^(y-1) == x &^ (y-1)
+	return MakeInt(false, x.mant.AndNot(y.mant.Sub(nat[1])));
+}
+
+
+// AndNot returns the ``bitwise clear'' x &^ y for the 2's-complement representation of x and y.
+//
+func (x *Integer) AndNot(y *Integer) *Integer {
+	if x.sign == y.sign {
+		if x.sign {
+			// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
+			return MakeInt(false, y.mant.Sub(nat[1]).AndNot(x.mant.Sub(nat[1])));
+		}
+
+		// x &^ y == x &^ y
+		return MakeInt(false, x.mant.AndNot(y.mant));
+	}
+
+	if x.sign {
+		// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
+		return MakeInt(true, x.mant.Sub(nat[1]).Or(y.mant).Add(nat[1]));
+	}
+
+	// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
+	return MakeInt(false, x.mant.And(y.mant.Sub(nat[1])));
+}
+
+
+// Or returns the ``bitwise or'' x | y for the 2's-complement representation of x and y.
+//
+func (x *Integer) Or(y *Integer) *Integer {
+	if x.sign == y.sign {
+		if x.sign {
+			// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
+			return MakeInt(true, x.mant.Sub(nat[1]).And(y.mant.Sub(nat[1])).Add(nat[1]));
+		}
+
+		// x | y == x | y
+		return MakeInt(false, x.mant.Or(y.mant));
+	}
+
+	// x.sign != y.sign
+	if x.sign {
+		x, y = y, x;  // | or symmetric
+	}
+
+	// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
+	return MakeInt(true, y.mant.Sub(nat[1]).AndNot(x.mant).Add(nat[1]));
+}
+
+
+// Xor returns the ``bitwise xor'' x | y for the 2's-complement representation of x and y.
+//
+func (x *Integer) Xor(y *Integer) *Integer {
+	if x.sign == y.sign {
+		if x.sign {
+			// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
+			return MakeInt(false, x.mant.Sub(nat[1]).Xor(y.mant.Sub(nat[1])));
+		}
+
+		// x ^ y == x ^ y
+		return MakeInt(false, x.mant.Xor(y.mant));
+	}
+
+	// x.sign != y.sign
+	if x.sign {
+		x, y = y, x;  // ^ is symmetric
+	}
+
+	// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
+	return MakeInt(true, x.mant.Xor(y.mant.Sub(nat[1])).Add(nat[1]));
+}
+
+
+// Cmp compares x and y. The result is an int value that is
+//
+//   <  0 if x <  y
+//   == 0 if x == y
+//   >  0 if x >  y
+//
+func (x *Integer) Cmp(y *Integer) int {
+	// x cmp y == x cmp y
+	// x cmp (-y) == x
+	// (-x) cmp y == y
+	// (-x) cmp (-y) == -(x cmp y)
+	var r int;
+	switch {
+	case x.sign == y.sign:
+		r = x.mant.Cmp(y.mant);
+		if x.sign {
+			r = -r;
+		}
+	case x.sign: r = -1;
+	case y.sign: r = 1;
+	}
+	return r;
+}
+
+
+// ToString converts x to a string for a given base, with 2 <= base <= 16.
+//
+func (x *Integer) ToString(base uint) string {
+	if x.mant.IsZero() {
+		return "0";
+	}
+	var s string;
+	if x.sign {
+		s = "-";
+	}
+	return s + x.mant.ToString(base);
+}
+
+
+// String converts x to its decimal string representation.
+// x.String() is the same as x.ToString(10).
+//
+func (x *Integer) 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 *Integer) Format(h fmt.State, c int) {
+	fmt.Fprintf(h, "%s", x.ToString(fmtbase(c)));
+}
+
+
+// IntFromString returns the integer corresponding to the
+// longest possible prefix of s representing an integer in a
+// given conversion base, the actual conversion base used, and
+// the prefix length. The syntax of integers follows the syntax
+// of signed integer literals in Go.
+//
+// If the base argument is 0, the string prefix determines the actual
+// conversion base. A prefix of ``0x'' or ``0X'' selects base 16; the
+// ``0'' prefix selects base 8. Otherwise the selected base is 10.
+//
+func IntFromString(s string, base uint) (*Integer, uint, int) {
+	// skip sign, if any
+	i0 := 0;
+	if len(s) > 0 && (s[0] == '-' || s[0] == '+') {
+		i0 = 1;
+	}
+
+	mant, base, slen := NatFromString(s[i0 : len(s)], base);
+
+	return MakeInt(i0 > 0 && s[0] == '-', mant), base, i0 + slen;
+}