diff options
| -rwxr-xr-x | src/lib/bignum.go | 466 |
1 files changed, 345 insertions, 121 deletions
diff --git a/src/lib/bignum.go b/src/lib/bignum.go index 078374ad7..e122a2cac 100755 --- a/src/lib/bignum.go +++ b/src/lib/bignum.go @@ -2,14 +2,14 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -package bignum - // A package for arbitrary precision arithmethic. // It implements the following numeric types: // -// - Natural unsigned integer numbers -// - Integer signed integer numbers +// - Natural unsigned integers +// - Integer signed integers // - Rational rational numbers +// +package bignum import "fmt" @@ -21,13 +21,13 @@ import "fmt" // // x = x[n-1]*B^(n-1) + x[n-2]*B^(n-2) + ... + x[1]*B + x[0] // -// with 0 <= x[i] < B and 0 <= i < n is stored in an array of length n, -// with the digits x[i] as the array elements. +// with 0 <= x[i] < B and 0 <= i < n is stored in a slice of length n, +// with the digits x[i] as the slice elements. // -// A natural number is normalized if the array contains no leading 0 digits. -// During arithmetic operations, denormalized values may occur which are +// A natural number is normalized if the slice contains no leading 0 digits. +// During arithmetic operations, denormalized values may occur but are // always normalized before returning the final result. The normalized -// representation of 0 is the empty array (length = 0). +// representation of 0 is the empty slice (length = 0). // // The operations for all other numeric types are implemented on top of // the operations for natural numbers. @@ -42,7 +42,7 @@ import "fmt" // arithmetic. This makes addition, subtraction, and conversion routines // twice as fast. It requires a "buffer" of 4 bits per operand digit. // That is, the size of B must be 4 bits smaller then the size of the -// type (Digit) in which these operations are performed. Having this +// type (digit) in which these operations are performed. Having this // buffer also allows for trivial (single-bit) carry computation in // addition and subtraction (optimization suggested by Ken Thompson). // @@ -53,17 +53,16 @@ import "fmt" // in bits must be even. type ( - Digit uint64; - Digit2 uint32; // half-digits for division + digit uint64; + digit2 uint32; // half-digits for division ) -const _LogW = 64; -const _LogH = 4; // bits for a hex digit (= "small" number) -const _LogB = _LogW - _LogH; // largest bit-width available - - const ( + _LogW = 64; + _LogH = 4; // bits for a hex digit (= "small" number) + _LogB = _LogW - _LogH; // largest bit-width available + // half-digits _W2 = _LogB / 2; // width _B2 = 1 << _W2; // base @@ -86,12 +85,13 @@ func assert(p bool) { } -func isSmall(x Digit) bool { +func isSmall(x digit) bool { return x < 1<<_LogH; } -func Dump(x []Digit) { +// For debugging. +func dump(x []digit) { print("[", len(x), "]"); for i := len(x) - 1; i >= 0; i-- { print(" ", x[i]); @@ -102,16 +102,10 @@ func Dump(x []Digit) { // ---------------------------------------------------------------------------- // Natural numbers -// -// Naming conventions -// -// c carry -// x, y operands -// z result -// n, m len(x), len(y) - -type Natural []Digit; +// Natural represents an unsigned integer value of arbitrary precision. +// +type Natural []digit; var ( natZero Natural = Natural{}; @@ -121,8 +115,10 @@ var ( ) -// Creation - +// Nat creates a "small" natural number with value x. +// Implementation restriction: At the moment, only values +// x < (1<<60) are supported. +// func Nat(x uint) Natural { switch x { case 0: return natZero; @@ -130,24 +126,40 @@ func Nat(x uint) Natural { case 2: return natTwo; case 10: return natTen; } - assert(Digit(x) < _B); - return Natural{Digit(x)}; + assert(digit(x) < _B); + return Natural{digit(x)}; } -// Predicates +// IsEven returns true iff x is divisible by 2. +// +func (x Natural) IsEven() bool { + return len(x) == 0 || x[0]&1 == 0; +} + +// IsOdd returns true iff x is not divisible by 2. +// func (x Natural) IsOdd() bool { return len(x) > 0 && x[0]&1 != 0; } +// IsZero returns true iff x == 0. +// func (x Natural) IsZero() bool { return len(x) == 0; } // Operations +// +// Naming conventions +// +// c carry +// x, y operands +// z result +// n, m len(x), len(y) func normalize(x Natural) Natural { n := len(x); @@ -159,6 +171,8 @@ func normalize(x Natural) Natural { } +// Add returns the sum x + y. +// func (x Natural) Add(y Natural) Natural { n := len(x); m := len(y); @@ -166,7 +180,7 @@ func (x Natural) Add(y Natural) Natural { return y.Add(x); } - c := Digit(0); + c := digit(0); z := make(Natural, n + 1); i := 0; for i < m { @@ -188,6 +202,9 @@ func (x Natural) Add(y Natural) Natural { } +// Sub returns the difference x - y for x >= y. +// If x < y, an underflow run-time error occurs (use Cmp to test if x >= y). +// func (x Natural) Sub(y Natural) Natural { n := len(x); m := len(y); @@ -195,17 +212,17 @@ func (x Natural) Sub(y Natural) Natural { panic("underflow") } - c := Digit(0); + c := digit(0); z := make(Natural, n); i := 0; for i < m { t := c + x[i] - y[i]; - c, z[i] = Digit(int64(t)>>_W), t&_M; // requires arithmetic shift! + c, z[i] = digit(int64(t)>>_W), t&_M; // requires arithmetic shift! i++; } for i < n { t := c + x[i]; - c, z[i] = Digit(int64(t)>>_W), t&_M; // requires arithmetic shift! + c, z[i] = digit(int64(t)>>_W), t&_M; // requires arithmetic shift! i++; } for i > 0 && z[i - 1] == 0 { // normalize @@ -217,7 +234,8 @@ func (x Natural) Sub(y Natural) Natural { // Returns c = x*y div B, z = x*y mod B. -func mul11(x, y Digit) (Digit, Digit) { +// +func mul11(x, y digit) (digit, digit) { // Split x and y into 2 sub-digits each, // multiply the digits separately while avoiding overflow, // and return the product as two separate digits. @@ -250,6 +268,8 @@ func mul11(x, y Digit) (Digit, Digit) { } +// Mul returns the product x * y. +// func (x Natural) Mul(y Natural) Natural { n := len(x); m := len(y); @@ -258,7 +278,7 @@ func (x Natural) Mul(y Natural) Natural { for j := 0; j < m; j++ { d := y[j]; if d != 0 { - c := Digit(0); + c := digit(0); for i := 0; i < n; i++ { // z[i+j] += c + x[i]*d; z1, z0 := mul11(x[i], d); @@ -274,18 +294,18 @@ func (x Natural) Mul(y Natural) Natural { } -// DivMod needs multi-precision division which is not available if Digit +// DivMod needs multi-precision division, which is not available if digit // is already using the largest uint size. Instead, unpack each operand -// into operands with twice as many digits of half the size (Digit2), do +// into operands with twice as many digits of half the size (digit2), do // DivMod, and then pack the results again. -func unpack(x Natural) []Digit2 { +func unpack(x Natural) []digit2 { n := len(x); - z := make([]Digit2, n*2 + 1); // add space for extra digit (used by DivMod) + z := make([]digit2, n*2 + 1); // add space for extra digit (used by DivMod) for i := 0; i < n; i++ { t := x[i]; - z[i*2] = Digit2(t & _M2); - z[i*2 + 1] = Digit2(t >> _W2 & _M2); + z[i*2] = digit2(t & _M2); + z[i*2 + 1] = digit2(t >> _W2 & _M2); } // normalize result @@ -295,42 +315,42 @@ func unpack(x Natural) []Digit2 { } -func pack(x []Digit2) Natural { +func pack(x []digit2) Natural { n := (len(x) + 1) / 2; z := make(Natural, n); if len(x) & 1 == 1 { // handle odd len(x) n--; - z[n] = Digit(x[n*2]); + z[n] = digit(x[n*2]); } for i := 0; i < n; i++ { - z[i] = Digit(x[i*2 + 1]) << _W2 | Digit(x[i*2]); + z[i] = digit(x[i*2 + 1]) << _W2 | digit(x[i*2]); } return normalize(z); } -func mul1(z, x []Digit2, y Digit2) Digit2 { +func mul1(z, x []digit2, y digit2) digit2 { n := len(x); - c := Digit(0); - f := Digit(y); + c := digit(0); + f := digit(y); for i := 0; i < n; i++ { - t := c + Digit(x[i])*f; - c, z[i] = t>>_W2, Digit2(t&_M2); + t := c + digit(x[i])*f; + c, z[i] = t>>_W2, digit2(t&_M2); } - return Digit2(c); + return digit2(c); } -func div1(z, x []Digit2, y Digit2) Digit2 { +func div1(z, x []digit2, y digit2) digit2 { n := len(x); - c := Digit(0); - d := Digit(y); + c := digit(0); + d := digit(y); for i := n-1; i >= 0; i-- { - t := c*_B2 + Digit(x[i]); - c, z[i] = t%d, Digit2(t/d); + t := c*_B2 + digit(x[i]); + c, z[i] = t%d, digit2(t/d); } - return Digit2(c); + return digit2(c); } @@ -354,7 +374,7 @@ func div1(z, x []Digit2, y Digit2) Digit2 { // minefield. "Software - Practice and Experience 24", (June 1994), // 579-601. John Wiley & Sons, Ltd. -func divmod(x, y []Digit2) ([]Digit2, []Digit2) { +func divmod(x, y []digit2) ([]digit2, []digit2) { n := len(x); m := len(y); if m == 0 { @@ -382,21 +402,21 @@ func divmod(x, y []Digit2) ([]Digit2, []Digit2) { // TODO Instead of multiplying, it would be sufficient to // shift y such that the normalization condition is // satisfied (as done in "Hacker's Delight"). - f := _B2 / (Digit(y[m-1]) + 1); + f := _B2 / (digit(y[m-1]) + 1); if f != 1 { - mul1(x, x, Digit2(f)); - mul1(y, y, Digit2(f)); + mul1(x, x, digit2(f)); + mul1(y, y, digit2(f)); } assert(_B2/2 <= y[m-1] && y[m-1] < _B2); // incorrect scaling - y1, y2 := Digit(y[m-1]), Digit(y[m-2]); - d2 := Digit(y1)<<_W2 + Digit(y2); + y1, y2 := digit(y[m-1]), digit(y[m-2]); + d2 := digit(y1)<<_W2 + digit(y2); for i := n-m; i >= 0; i-- { k := i+m; // compute trial digit (Knuth) - var q Digit; - { x0, x1, x2 := Digit(x[k]), Digit(x[k-1]), Digit(x[k-2]); + var q digit; + { x0, x1, x2 := digit(x[k]), digit(x[k-1]), digit(x[k-2]); if x0 != y1 { q = (x0<<_W2 + x1)/y1; } else { @@ -408,31 +428,31 @@ func divmod(x, y []Digit2) ([]Digit2, []Digit2) { } // subtract y*q - c := Digit(0); + c := digit(0); for j := 0; j < m; j++ { - t := c + Digit(x[i+j]) - Digit(y[j])*q; - c, x[i+j] = Digit(int64(t) >> _W2), Digit2(t & _M2); // requires arithmetic shift! + t := c + digit(x[i+j]) - digit(y[j])*q; + c, x[i+j] = digit(int64(t) >> _W2), digit2(t & _M2); // requires arithmetic shift! } // correct if trial digit was too large - if c + Digit(x[k]) != 0 { + if c + digit(x[k]) != 0 { // add y - c := Digit(0); + c := digit(0); for j := 0; j < m; j++ { - t := c + Digit(x[i+j]) + Digit(y[j]); - c, x[i+j] = t >> _W2, Digit2(t & _M2) + t := c + digit(x[i+j]) + digit(y[j]); + c, x[i+j] = t >> _W2, digit2(t & _M2) } - assert(c + Digit(x[k]) == 0); + assert(c + digit(x[k]) == 0); // correct trial digit q--; } - x[k] = Digit2(q); + x[k] = digit2(q); } // undo normalization for remainder if f != 1 { - c := div1(x[0 : m], x[0 : m], Digit2(f)); + c := div1(x[0 : m], x[0 : m], digit2(f)); assert(c == 0); } } @@ -441,28 +461,39 @@ func divmod(x, y []Digit2) ([]Digit2, []Digit2) { } +// Div returns the quotient q = x / y for y > 0, +// with x = y*q + r and 0 <= r < y. +// If y == 0, a division-by-zero run-time error occurs. +// func (x Natural) Div(y Natural) Natural { q, r := divmod(unpack(x), unpack(y)); return pack(q); } +// Mod returns the modulus r of the division x / y for y > 0, +// with x = y*q + r and 0 <= r < y. +// If y == 0, a division-by-zero run-time error occurs. +// func (x Natural) Mod(y Natural) Natural { q, r := divmod(unpack(x), unpack(y)); return pack(r); } +// DivMod returns the pair (x.Div(y), x.Mod(y)) for y > 0. +// If y == 0, a division-by-zero run-time error occurs. +// func (x Natural) DivMod(y Natural) (Natural, Natural) { q, r := divmod(unpack(x), unpack(y)); return pack(q), pack(r); } -func shl(z, x []Digit, s uint) Digit { +func shl(z, x []digit, s uint) digit { assert(s <= _W); n := len(x); - c := Digit(0); + c := digit(0); for i := 0; i < n; i++ { c, z[i] = x[i] >> (_W-s), x[i] << s & _M | c; } @@ -470,6 +501,8 @@ func shl(z, x []Digit, s uint) Digit { } +// Shl implements "shift left" x << s. It returns x * 2^s. +// func (x Natural) Shl(s uint) Natural { n := uint(len(x)); m := n + s/_W; @@ -481,10 +514,10 @@ func (x Natural) Shl(s uint) Natural { } -func shr(z, x []Digit, s uint) Digit { +func shr(z, x []digit, s uint) digit { assert(s <= _W); n := len(x); - c := Digit(0); + c := digit(0); for i := n - 1; i >= 0; i-- { c, z[i] = x[i] << (_W-s) & _M, x[i] >> s | c; } @@ -492,6 +525,8 @@ func shr(z, x []Digit, s uint) Digit { } +// Shr implements "shift right" x >> s. It returns x / 2^s. +// func (x Natural) Shr(s uint) Natural { n := uint(len(x)); m := n - s/_W; @@ -506,6 +541,8 @@ func (x Natural) Shr(s uint) Natural { } +// And returns the "bitwise and" x & y for the binary representation of x and y. +// func (x Natural) And(y Natural) Natural { n := len(x); m := len(y); @@ -523,13 +560,15 @@ func (x Natural) And(y Natural) Natural { } -func copy(z, x []Digit) { +func copy(z, x []digit) { for i, e := range x { z[i] = e } } +// Or returns the "bitwise or" x | y for the binary representation of x and y. +// func (x Natural) Or(y Natural) Natural { n := len(x); m := len(y); @@ -547,6 +586,8 @@ func (x Natural) Or(y Natural) Natural { } +// Xor returns the "bitwise exclusive or" x ^ y for the binary representation of x and y. +// func (x Natural) Xor(y Natural) Natural { n := len(x); m := len(y); @@ -564,6 +605,12 @@ func (x Natural) Xor(y Natural) Natural { } +// 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 Natural) Cmp(y Natural) int { n := len(x); m := len(y); @@ -585,7 +632,7 @@ func (x Natural) Cmp(y Natural) int { } -func log2(x Digit) uint { +func log2(x digit) uint { assert(x > 0); n := uint(0); for x > 0 { @@ -596,6 +643,10 @@ func log2(x Digit) uint { } +// Log2 computes the binary logarithm of x for x > 0. +// The result is the integer n for which 2^n <= x < 2^(n+1). +// If x == 0 a run-time error occurs. +// func (x Natural) Log2() uint { n := len(x); if n > 0 { @@ -607,10 +658,11 @@ func (x Natural) Log2() uint { // Computes x = x div d in place (modifies x) for "small" d's. // Returns updated x and x mod d. -func divmod1(x Natural, d Digit) (Natural, Digit) { +// +func divmod1(x Natural, d digit) (Natural, digit) { assert(0 < d && isSmall(d - 1)); - c := Digit(0); + c := digit(0); for i := len(x) - 1; i >= 0; i-- { t := c<<_W + x[i]; c, x[i] = t%d, t/d; @@ -620,6 +672,8 @@ func divmod1(x Natural, d Digit) (Natural, Digit) { } +// ToString converts x to a string for a given base, with 2 <= base <= 16. +// func (x Natural) ToString(base uint) string { if len(x) == 0 { return "0"; @@ -627,7 +681,7 @@ func (x Natural) ToString(base uint) string { // allocate buffer for conversion assert(2 <= base && base <= 16); - n := (x.Log2() + 1) / log2(Digit(base)) + 1; // +1: round up + n := (x.Log2() + 1) / log2(digit(base)) + 1; // +1: round up s := make([]byte, n); // don't destroy x @@ -638,8 +692,8 @@ func (x Natural) ToString(base uint) string { i := n; for !t.IsZero() { i--; - var d Digit; - t, d = divmod1(t, Digit(base)); + var d digit; + t, d = divmod1(t, digit(base)); s[i] = "0123456789abcdef"[d]; }; @@ -647,6 +701,9 @@ func (x Natural) ToString(base uint) string { } +// String converts x to its decimal string representation. +// (x.String is the same as x.ToString(10)). +// func (x Natural) String() string { return x.ToString(10); } @@ -662,6 +719,9 @@ func fmtbase(c int) uint { } +// Format is a support routine for fmt.Formatter. It accepts +// the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal). +// func (x Natural) Format(h fmt.Formatter, c int) { fmt.Fprintf(h, "%s", x.ToString(fmtbase(c))); } @@ -679,7 +739,8 @@ func hexvalue(ch byte) uint { // Computes x = x*d + c for "small" d's. -func muladd1(x Natural, d, c Digit) Natural { +// +func muladd1(x Natural, d, c digit) Natural { assert(isSmall(d-1) && isSmall(c)); n := len(x); z := make(Natural, n + 1); @@ -694,8 +755,17 @@ func muladd1(x Natural, d, c Digit) Natural { } -// Determines base (octal, decimal, hexadecimal) if base == 0. -// Returns the number and base. +// NatFromString returns the natural number corresponding to the +// longest possible prefix of s representing a natural number in a +// given conversion base. +// +// 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. +// +// If a non-nil slen argument is provided, *slen is set to the length +// of the string prefix converted. +// func NatFromString(s string, base uint, slen *int) (Natural, uint) { // determine base if necessary i, n := 0, len(s); @@ -716,7 +786,7 @@ func NatFromString(s string, base uint, slen *int) (Natural, uint) { for ; i < n; i++ { d := hexvalue(s[i]); if d < base { - x = muladd1(x, Digit(base), Digit(d)); + x = muladd1(x, digit(base), digit(d)); } else { break; } @@ -733,7 +803,7 @@ func NatFromString(s string, base uint, slen *int) (Natural, uint) { // Natural number functions -func pop1(x Digit) uint { +func pop1(x digit) uint { n := uint(0); for x != 0 { x &= x-1; @@ -743,6 +813,10 @@ func pop1(x Digit) uint { } +// Pop computes the "population count" of x. +// The result is the number of set bits (i.e., "1" digits) +// in the binary representation of x. +// func (x Natural) Pop() uint { n := uint(0); for i := len(x) - 1; i >= 0; i-- { @@ -752,6 +826,8 @@ func (x Natural) Pop() uint { } +// Pow computes x to the power of n. +// func (xp Natural) Pow(n uint) Natural { z := Nat(1); x := xp; @@ -766,6 +842,9 @@ func (xp Natural) Pow(n uint) Natural { } +// MulRange computes the product of all the unsigned integers +// in the range [a, b] inclusively. +// func MulRange(a, b uint) Natural { switch { case a > b: return Nat(1); @@ -778,6 +857,8 @@ func MulRange(a, b uint) Natural { } +// Fact computes the factorial of n (Fact(n) == MulRange(2, n)). +// func Fact(n uint) Natural { // Using MulRange() instead of the basic for-loop // lead to faster factorial computation. @@ -785,18 +866,22 @@ func Fact(n uint) Natural { } +// Binomial computes the binomial coefficient of (n, k). +// func Binomial(n, k uint) Natural { return MulRange(n-k+1, n).Div(MulRange(1, k)); } -func (xp Natural) Gcd(y Natural) Natural { +// Gcd computes the gcd of x and y. +// +func (x Natural) Gcd(y Natural) Natural { // Euclidean algorithm. - x := xp; - for !y.IsZero() { - x, y = y, x.Mod(y); + a, b := x, y; + for !b.IsZero() { + a, b = b, a.Mod(b); } - return x; + return a; } @@ -806,14 +891,18 @@ func (xp Natural) Gcd(y Natural) Natural { // 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; } -// Creation - +// 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 @@ -822,6 +911,10 @@ func MakeInt(sign bool, mant Natural) *Integer { } +// Int creates a "small" integer with value x. +// Implementation restriction: At the moment, only values +// with an absolute value |x| < (1<<60) are supported. +// func Int(x int) *Integer { sign := false; var ux uint; @@ -843,21 +936,36 @@ func Int(x int) *Integer { // 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() } @@ -865,11 +973,15 @@ func (x *Integer) IsPos() bool { // 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 { @@ -892,6 +1004,8 @@ func (x *Integer) Add(y *Integer) *Integer { } +// Sub returns the difference x - y. +// func (x *Integer) Sub(y *Integer) *Integer { var z *Integer; if x.sign != y.sign { @@ -914,6 +1028,8 @@ func (x *Integer) Sub(y *Integer) *Integer { } +// Mul returns the product x * y. +// func (x *Integer) Mul(y *Integer) *Integer { // x * y == x * y // x * (-y) == -(x * y) @@ -923,6 +1039,8 @@ func (x *Integer) Mul(y *Integer) *Integer { } +// 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) @@ -930,13 +1048,16 @@ func (x *Integer) MulNat(y Natural) *Integer { } +// 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". ) - +// (Daan Leijen, "Division and Modulus for Computer Scientists".) +// func (x *Integer) Quo(y *Integer) *Integer { // x / y == x / y // x / (-y) == -(x / y) @@ -946,6 +1067,11 @@ func (x *Integer) Quo(y *Integer) *Integer { } +// 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 @@ -955,23 +1081,28 @@ func (x *Integer) Rem(y *Integer) *Integer { } +// 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: // -// d = x.Div(y) -// m = x.Mod(y) with: 0 <= m < |d| and: y = x*d + m +// 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.) // -// ( 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() { @@ -985,6 +1116,10 @@ func (x *Integer) Div(y *Integer) *Integer { } +// 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() { @@ -998,6 +1133,8 @@ func (x *Integer) Mod(y *Integer) *Integer { } +// 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() { @@ -1013,53 +1150,73 @@ func (x *Integer) DivMod(y *Integer) (*Integer, *Integer) { } +// 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)); } +// Shr implements "shift right" x >> s. It returns x / 2^s. +// Implementation restriction: Shl is not yet implemented for negative x. +// func (x *Integer) Shr(s uint) *Integer { z := MakeInt(x.sign, x.mant.Shr(s)); if x.IsNeg() { - panic("UNIMPLEMENTED Integer.Shr() of negative values"); + panic("UNIMPLEMENTED Integer.Shr of negative values"); } return z; } +// And returns the "bitwise and" x & y for the binary representation of x and y. +// Implementation restriction: And is not implemented for negative x. +// func (x *Integer) And(y *Integer) *Integer { var z *Integer; if !x.sign && !y.sign { z = MakeInt(false, x.mant.And(y.mant)); } else { - panic("UNIMPLEMENTED Integer.And() of negative values"); + panic("UNIMPLEMENTED Integer.And of negative values"); } return z; } +// Or returns the "bitwise or" x | y for the binary representation of x and y. +// Implementation restriction: Or is not implemented for negative x. +// func (x *Integer) Or(y *Integer) *Integer { var z *Integer; if !x.sign && !y.sign { z = MakeInt(false, x.mant.Or(y.mant)); } else { - panic("UNIMPLEMENTED Integer.Or() of negative values"); + panic("UNIMPLEMENTED Integer.Or of negative values"); } return z; } +// Xor returns the "bitwise xor" x | y for the binary representation of x and y. +// Implementation restriction: Xor is not implemented for negative integers. +// func (x *Integer) Xor(y *Integer) *Integer { var z *Integer; if !x.sign && !y.sign { z = MakeInt(false, x.mant.Xor(y.mant)); } else { - panic("UNIMPLEMENTED Integer.Xor() of negative values"); + panic("UNIMPLEMENTED Integer.Xor of negative values"); } return z; } +// 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 @@ -1079,6 +1236,8 @@ func (x *Integer) Cmp(y *Integer) int { } +// 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"; @@ -1091,18 +1250,33 @@ func (x *Integer) ToString(base uint) string { } +// 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.Formatter, c int) { fmt.Fprintf(h, "%s", x.ToString(fmtbase(c))); } -// Determines base (octal, decimal, hexadecimal) if base == 0. -// Returns the number and base. +// IntFromString returns the integer corresponding to the +// longest possible prefix of s representing an integer in a +// given conversion base. +// +// 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. +// +// If a non-nil slen argument is provided, *slen is set to the length +// of the string prefix converted. +// func IntFromString(s string, base uint, slen *int) (*Integer, uint) { // get sign, if any sign := false; @@ -1126,14 +1300,16 @@ func IntFromString(s string, base uint, slen *int) (*Integer, uint) { // ---------------------------------------------------------------------------- // Rational numbers +// Rational represents a quotient a/b of arbitrary precision. +// type Rational struct { a *Integer; // numerator b Natural; // denominator } -// Creation - +// 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 { @@ -1144,6 +1320,10 @@ func MakeRat(a *Integer, b Natural) *Rational { } +// Rat creates a "small" rational number with value a0/b0. +// Implementation restriction: At the moment, only values a0, b0 +// with an absolute value |a0|, |b0| < (1<<60) are supported. +// func Rat(a0 int, b0 int) *Rational { a, b := Int(a0), Int(b0); if b.sign { @@ -1155,21 +1335,30 @@ func Rat(a0 int, b0 int) *Rational { // 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; } @@ -1177,26 +1366,37 @@ func (x *Rational) IsInt() bool { // 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); @@ -1207,11 +1407,20 @@ func (x *Rational) Quo(y *Rational) *Rational { } +// 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 "numerator/denominator". +// func (x *Rational) ToString(base uint) string { s := x.a.ToString(base); if !x.IsInt() { @@ -1221,18 +1430,33 @@ func (x *Rational) ToString(base uint) string { } +// 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.Formatter, c int) { fmt.Fprintf(h, "%s", x.ToString(fmtbase(c))); } -// Determines base (octal, decimal, hexadecimal) if base == 0. -// Returns the number and base of the nominator. +// RatFromString returns the rational number corresponding to the +// longest possible prefix of s representing a rational number in a +// given conversion base. +// +// 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. +// +// If a non-nil slen argument is provided, *slen is set to the length +// of the string prefix converted. +// func RatFromString(s string, base uint, slen *int) (*Rational, uint) { // read nominator var alen, blen int; |