diff options
Diffstat (limited to 'src/pkg/exp/bignum/integer.go')
| -rw-r--r-- | src/pkg/exp/bignum/integer.go | 520 |
1 files changed, 0 insertions, 520 deletions
diff --git a/src/pkg/exp/bignum/integer.go b/src/pkg/exp/bignum/integer.go deleted file mode 100644 index a8d26829d..000000000 --- a/src/pkg/exp/bignum/integer.go +++ /dev/null @@ -1,520 +0,0 @@ -// 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 ( - "fmt" -) - -// TODO(gri) Complete the set of in-place operations. - -// 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) } - - -// Iadd sets z to the sum x + y. -// z must exist and may be x or y. -// -func Iadd(z, x, y *Integer) { - if x.sign == y.sign { - // x + y == x + y - // (-x) + (-y) == -(x + y) - z.sign = x.sign - Nadd(&z.mant, x.mant, y.mant) - } else { - // x + (-y) == x - y == -(y - x) - // (-x) + y == y - x == -(x - y) - if x.mant.Cmp(y.mant) >= 0 { - z.sign = x.sign - Nsub(&z.mant, x.mant, y.mant) - } else { - z.sign = !x.sign - Nsub(&z.mant, y.mant, x.mant) - } - } -} - - -// Add returns the sum x + y. -// -func (x *Integer) Add(y *Integer) *Integer { - var z Integer - Iadd(&z, x, y) - return &z -} - - -func Isub(z, x, y *Integer) { - if x.sign != y.sign { - // x - (-y) == x + y - // (-x) - y == -(x + y) - z.sign = x.sign - Nadd(&z.mant, x.mant, y.mant) - } else { - // x - y == x - y == -(y - x) - // (-x) - (-y) == y - x == -(x - y) - if x.mant.Cmp(y.mant) >= 0 { - z.sign = x.sign - Nsub(&z.mant, x.mant, y.mant) - } else { - z.sign = !x.sign - Nsub(&z.mant, y.mant, x.mant) - } - } -} - - -// Sub returns the difference x - y. -// -func (x *Integer) Sub(y *Integer) *Integer { - var z Integer - Isub(&z, x, y) - return &z -} - - -// Nscale sets *z to the scaled value (*z) * d. -// -func Iscale(z *Integer, d int64) { - f := uint64(d) - if d < 0 { - f = uint64(-d) - } - z.sign = z.sign != (d < 0) - Nscale(&z.mant, f) -} - - -// Mul1 returns the product x * d. -// -func (x *Integer) Mul1(d int64) *Integer { - f := uint64(d) - if d < 0 { - f = uint64(-d) - } - return MakeInt(x.sign != (d < 0), x.mant.Mul1(f)) -} - - -// 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: x = y*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:], base) - - return MakeInt(i0 > 0 && s[0] == '-', mant), base, i0 + slen -} |