diff options
Diffstat (limited to 'src/pkg/bignum/bignum.go')
| -rwxr-xr-x | src/pkg/bignum/bignum.go | 739 |
1 files changed, 15 insertions, 724 deletions
diff --git a/src/pkg/bignum/bignum.go b/src/pkg/bignum/bignum.go index 91a207dd4..71bf66d76 100755 --- a/src/pkg/bignum/bignum.go +++ b/src/pkg/bignum/bignum.go @@ -109,23 +109,24 @@ func dump(x []digit) { // type Natural []digit; -var ( - natZero = Natural{}; - natOne = Natural{1}; - natTwo = Natural{2}; - natTen = Natural{10}; -) + +// Common small values - allocate once. +var nat [16]Natural; + +func init() { + nat[0] = Natural{}; // zero has no digits + for i := 1; i < len(nat); i++ { + nat[i] = Natural{digit(i)}; + } +} // Nat creates a small natural number with value x. // func Nat(x uint64) Natural { // avoid allocation for common small values - switch x { - case 0: return natZero; - case 1: return natOne; - case 2: return natTwo; - case 10: return natTen; + if x < uint64(len(nat)) { + return nat[x]; } // single-digit values @@ -851,7 +852,7 @@ func NatFromString(s string, base uint) (Natural, uint, int) { // convert string assert(2 <= base && base <= 16); - x := Nat(0); + x := nat[0]; for ; i < n; i++ { d := hexvalue(s[i]); if d < base { @@ -891,7 +892,7 @@ func (x Natural) Pop() uint { // Pow computes x to the power of n. // func (xp Natural) Pow(n uint) Natural { - z := Nat(1); + z := nat[1]; x := xp; for n > 0 { // z * x^n == x^n0 @@ -909,7 +910,7 @@ func (xp Natural) Pow(n uint) Natural { // func MulRange(a, b uint) Natural { switch { - case a > b: return Nat(1); + case a > b: return nat[1]; case a == b: return Nat(uint64(a)); case a + 1 == b: return Nat(uint64(a)).Mul(Nat(uint64(b))); } @@ -945,713 +946,3 @@ func (x Natural) Gcd(y Natural) Natural { } return a; } - - -// ---------------------------------------------------------------------------- -// Integer numbers -// -// Integers are normalized if the mantissa is normalized and the sign is -// false for mant == 0. Use MakeInt to create normalized Integers. - -// 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(natOne).Shr(s).Add(natOne)); - } - - 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(natOne)); - } - - // ^x == -x-1 == -(x+1) - return MakeInt(true, x.mant.Add(natOne)); -} - - -// 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(natOne).Or(y.mant.Sub(natOne)).Add(natOne)); - } - - // 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(natOne))); -} - - -// 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(natOne).AndNot(x.mant.Sub(natOne))); - } - - // 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(natOne).Or(y.mant).Add(natOne)); - } - - // x &^ (-y) == x &^ ^(y-1) == x & (y-1) - return MakeInt(false, x.mant.And(y.mant.Sub(natOne))); -} - - -// 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(natOne).And(y.mant.Sub(natOne)).Add(natOne)); - } - - // 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(natOne).AndNot(x.mant).Add(natOne)); -} - - -// 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(natOne).Xor(y.mant.Sub(natOne))); - } - - // 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(natOne)).Add(natOne)); -} - - -// 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 *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; -} - - -// ---------------------------------------------------------------------------- -// Rational numbers - -// 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 : len(s)], base); - } else if ch == '.' { - alen++; - b, base, blen = NatFromString(s[alen : len(s)], 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 : len(s)], 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; -} |