aboutsummaryrefslogtreecommitdiff
path: root/libgo/go/big/int.go
diff options
context:
space:
mode:
Diffstat (limited to 'libgo/go/big/int.go')
-rw-r--r--libgo/go/big/int.go302
1 files changed, 218 insertions, 84 deletions
diff --git a/libgo/go/big/int.go b/libgo/go/big/int.go
index f1ea7b1..701b697 100644
--- a/libgo/go/big/int.go
+++ b/libgo/go/big/int.go
@@ -8,8 +8,10 @@ package big
import (
"fmt"
+ "io"
"os"
"rand"
+ "strings"
)
// An Int represents a signed multi-precision integer.
@@ -19,10 +21,8 @@ type Int struct {
abs nat // absolute value of the integer
}
-
var intOne = &Int{false, natOne}
-
// Sign returns:
//
// -1 if x < 0
@@ -39,7 +39,6 @@ func (x *Int) Sign() int {
return 1
}
-
// SetInt64 sets z to x and returns z.
func (z *Int) SetInt64(x int64) *Int {
neg := false
@@ -52,13 +51,11 @@ func (z *Int) SetInt64(x int64) *Int {
return z
}
-
// NewInt allocates and returns a new Int set to x.
func NewInt(x int64) *Int {
return new(Int).SetInt64(x)
}
-
// Set sets z to x and returns z.
func (z *Int) Set(x *Int) *Int {
z.abs = z.abs.set(x.abs)
@@ -66,7 +63,6 @@ func (z *Int) Set(x *Int) *Int {
return z
}
-
// Abs sets z to |x| (the absolute value of x) and returns z.
func (z *Int) Abs(x *Int) *Int {
z.abs = z.abs.set(x.abs)
@@ -74,7 +70,6 @@ func (z *Int) Abs(x *Int) *Int {
return z
}
-
// Neg sets z to -x and returns z.
func (z *Int) Neg(x *Int) *Int {
z.abs = z.abs.set(x.abs)
@@ -82,7 +77,6 @@ func (z *Int) Neg(x *Int) *Int {
return z
}
-
// Add sets z to the sum x+y and returns z.
func (z *Int) Add(x, y *Int) *Int {
neg := x.neg
@@ -104,7 +98,6 @@ func (z *Int) Add(x, y *Int) *Int {
return z
}
-
// Sub sets z to the difference x-y and returns z.
func (z *Int) Sub(x, y *Int) *Int {
neg := x.neg
@@ -126,7 +119,6 @@ func (z *Int) Sub(x, y *Int) *Int {
return z
}
-
// Mul sets z to the product x*y and returns z.
func (z *Int) Mul(x, y *Int) *Int {
// x * y == x * y
@@ -138,7 +130,6 @@ func (z *Int) Mul(x, y *Int) *Int {
return z
}
-
// MulRange sets z to the product of all integers
// in the range [a, b] inclusively and returns z.
// If a > b (empty range), the result is 1.
@@ -162,7 +153,6 @@ func (z *Int) MulRange(a, b int64) *Int {
return z
}
-
// Binomial sets z to the binomial coefficient of (n, k) and returns z.
func (z *Int) Binomial(n, k int64) *Int {
var a, b Int
@@ -171,7 +161,6 @@ func (z *Int) Binomial(n, k int64) *Int {
return z.Quo(&a, &b)
}
-
// Quo sets z to the quotient x/y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// See QuoRem for more details.
@@ -181,7 +170,6 @@ func (z *Int) Quo(x, y *Int) *Int {
return z
}
-
// Rem sets z to the remainder x%y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// See QuoRem for more details.
@@ -191,7 +179,6 @@ func (z *Int) Rem(x, y *Int) *Int {
return z
}
-
// QuoRem sets z to the quotient x/y and r to the remainder x%y
// and returns the pair (z, r) for y != 0.
// If y == 0, a division-by-zero run-time panic occurs.
@@ -209,7 +196,6 @@ func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
return z, r
}
-
// Div sets z to the quotient x/y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// See DivMod for more details.
@@ -227,7 +213,6 @@ func (z *Int) Div(x, y *Int) *Int {
return z
}
-
// Mod sets z to the modulus x%y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// See DivMod for more details.
@@ -248,7 +233,6 @@ func (z *Int) Mod(x, y *Int) *Int {
return z
}
-
// DivMod sets z to the quotient x div y and m to the modulus x mod y
// and returns the pair (z, m) for y != 0.
// If y == 0, a division-by-zero run-time panic occurs.
@@ -281,7 +265,6 @@ func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
return z, m
}
-
// Cmp compares x and y and returns:
//
// -1 if x < y
@@ -307,49 +290,197 @@ func (x *Int) Cmp(y *Int) (r int) {
return
}
-
func (x *Int) String() string {
- s := ""
- if x.neg {
- s = "-"
+ switch {
+ case x == nil:
+ return "<nil>"
+ case x.neg:
+ return "-" + x.abs.decimalString()
}
- return s + x.abs.string(10)
+ return x.abs.decimalString()
}
-
-func fmtbase(ch int) int {
+func charset(ch int) string {
switch ch {
case 'b':
- return 2
+ return lowercaseDigits[0:2]
case 'o':
- return 8
- case 'd':
- return 10
+ return lowercaseDigits[0:8]
+ case 'd', 's', 'v':
+ return lowercaseDigits[0:10]
case 'x':
- return 16
+ return lowercaseDigits[0:16]
+ case 'X':
+ return uppercaseDigits[0:16]
}
- return 10
+ return "" // unknown format
}
+// write count copies of text to s
+func writeMultiple(s fmt.State, text string, count int) {
+ if len(text) > 0 {
+ b := []byte(text)
+ for ; count > 0; count-- {
+ s.Write(b)
+ }
+ }
+}
// Format is a support routine for fmt.Formatter. It accepts
-// the formats 'b' (binary), 'o' (octal), 'd' (decimal) and
-// 'x' (hexadecimal).
+// the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x'
+// (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
+// Also supported are the full suite of package fmt's format
+// verbs for integral types, including '+', '-', and ' '
+// for sign control, '#' for leading zero in octal and for
+// hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X"
+// respectively, specification of minimum digits precision,
+// output field width, space or zero padding, and left or
+// right justification.
//
func (x *Int) Format(s fmt.State, ch int) {
- if x == nil {
+ cs := charset(ch)
+
+ // special cases
+ switch {
+ case cs == "":
+ // unknown format
+ fmt.Fprintf(s, "%%!%c(big.Int=%s)", ch, x.String())
+ return
+ case x == nil:
fmt.Fprint(s, "<nil>")
return
}
- if x.neg {
- fmt.Fprint(s, "-")
+
+ // determine sign character
+ sign := ""
+ switch {
+ case x.neg:
+ sign = "-"
+ case s.Flag('+'): // supersedes ' ' when both specified
+ sign = "+"
+ case s.Flag(' '):
+ sign = " "
+ }
+
+ // determine prefix characters for indicating output base
+ prefix := ""
+ if s.Flag('#') {
+ switch ch {
+ case 'o': // octal
+ prefix = "0"
+ case 'x': // hexadecimal
+ prefix = "0x"
+ case 'X':
+ prefix = "0X"
+ }
+ }
+
+ // determine digits with base set by len(cs) and digit characters from cs
+ digits := x.abs.string(cs)
+
+ // number of characters for the three classes of number padding
+ var left int // space characters to left of digits for right justification ("%8d")
+ var zeroes int // zero characters (actually cs[0]) as left-most digits ("%.8d")
+ var right int // space characters to right of digits for left justification ("%-8d")
+
+ // determine number padding from precision: the least number of digits to output
+ precision, precisionSet := s.Precision()
+ if precisionSet {
+ switch {
+ case len(digits) < precision:
+ zeroes = precision - len(digits) // count of zero padding
+ case digits == "0" && precision == 0:
+ return // print nothing if zero value (x == 0) and zero precision ("." or ".0")
+ }
+ }
+
+ // determine field pad from width: the least number of characters to output
+ length := len(sign) + len(prefix) + zeroes + len(digits)
+ if width, widthSet := s.Width(); widthSet && length < width { // pad as specified
+ switch d := width - length; {
+ case s.Flag('-'):
+ // pad on the right with spaces; supersedes '0' when both specified
+ right = d
+ case s.Flag('0') && !precisionSet:
+ // pad with zeroes unless precision also specified
+ zeroes = d
+ default:
+ // pad on the left with spaces
+ left = d
+ }
}
- fmt.Fprint(s, x.abs.string(fmtbase(ch)))
+
+ // print number as [left pad][sign][prefix][zero pad][digits][right pad]
+ writeMultiple(s, " ", left)
+ writeMultiple(s, sign, 1)
+ writeMultiple(s, prefix, 1)
+ writeMultiple(s, "0", zeroes)
+ writeMultiple(s, digits, 1)
+ writeMultiple(s, " ", right)
}
+// scan sets z to the integer value corresponding to the longest possible prefix
+// read from r representing a signed integer number in a given conversion base.
+// It returns z, the actual conversion base used, and an error, if any. In the
+// error case, the value of z is undefined. The syntax follows the syntax of
+// integer literals in Go.
+//
+// The base argument must be 0 or a value from 2 through MaxBase. If the base
+// 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, and a
+// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
+//
+func (z *Int) scan(r io.RuneScanner, base int) (*Int, int, os.Error) {
+ // determine sign
+ ch, _, err := r.ReadRune()
+ if err != nil {
+ return z, 0, err
+ }
+ neg := false
+ switch ch {
+ case '-':
+ neg = true
+ case '+': // nothing to do
+ default:
+ r.UnreadRune()
+ }
-// Int64 returns the int64 representation of z.
-// If z cannot be represented in an int64, the result is undefined.
+ // determine mantissa
+ z.abs, base, err = z.abs.scan(r, base)
+ if err != nil {
+ return z, base, err
+ }
+ z.neg = len(z.abs) > 0 && neg // 0 has no sign
+
+ return z, base, nil
+}
+
+// Scan is a support routine for fmt.Scanner; it sets z to the value of
+// the scanned number. It accepts the formats 'b' (binary), 'o' (octal),
+// 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
+func (z *Int) Scan(s fmt.ScanState, ch int) os.Error {
+ s.SkipSpace() // skip leading space characters
+ base := 0
+ switch ch {
+ case 'b':
+ base = 2
+ case 'o':
+ base = 8
+ case 'd':
+ base = 10
+ case 'x', 'X':
+ base = 16
+ case 's', 'v':
+ // let scan determine the base
+ default:
+ return os.NewError("Int.Scan: invalid verb")
+ }
+ _, _, err := z.scan(s, base)
+ return err
+}
+
+// Int64 returns the int64 representation of x.
+// If x cannot be represented in an int64, the result is undefined.
func (x *Int) Int64() int64 {
if len(x.abs) == 0 {
return 0
@@ -364,40 +495,25 @@ func (x *Int) Int64() int64 {
return v
}
-
// SetString sets z to the value of s, interpreted in the given base,
// and returns z and a boolean indicating success. If SetString fails,
// the value of z is undefined.
//
-// 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, and a ``0b'' or ``0B'' prefix selects
-// base 2. Otherwise the selected base is 10.
+// The base argument must be 0 or a value from 2 through MaxBase. If the base
+// 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, and a
+// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
//
func (z *Int) SetString(s string, base int) (*Int, bool) {
- if len(s) == 0 || base < 0 || base == 1 || 16 < base {
- return z, false
- }
-
- neg := s[0] == '-'
- if neg || s[0] == '+' {
- s = s[1:]
- if len(s) == 0 {
- return z, false
- }
- }
-
- var scanned int
- z.abs, _, scanned = z.abs.scan(s, base)
- if scanned != len(s) {
+ r := strings.NewReader(s)
+ _, _, err := z.scan(r, base)
+ if err != nil {
return z, false
}
- z.neg = len(z.abs) > 0 && neg // 0 has no sign
-
- return z, true
+ _, _, err = r.ReadRune()
+ return z, err == os.EOF // err == os.EOF => scan consumed all of s
}
-
// SetBytes interprets buf as the bytes of a big-endian unsigned
// integer, sets z to that value, and returns z.
func (z *Int) SetBytes(buf []byte) *Int {
@@ -406,21 +522,18 @@ func (z *Int) SetBytes(buf []byte) *Int {
return z
}
-
// Bytes returns the absolute value of z as a big-endian byte slice.
func (z *Int) Bytes() []byte {
buf := make([]byte, len(z.abs)*_S)
return buf[z.abs.bytes(buf):]
}
-
// BitLen returns the length of the absolute value of z in bits.
// The bit length of 0 is 0.
func (z *Int) BitLen() int {
return z.abs.bitLen()
}
-
// Exp sets z = x**y mod m. If m is nil, z = x**y.
// See Knuth, volume 2, section 4.6.3.
func (z *Int) Exp(x, y, m *Int) *Int {
@@ -441,7 +554,6 @@ func (z *Int) Exp(x, y, m *Int) *Int {
return z
}
-
// GcdInt sets d to the greatest common divisor of a and b, which must be
// positive numbers.
// If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
@@ -500,7 +612,6 @@ func GcdInt(d, x, y, a, b *Int) {
*d = *A
}
-
// ProbablyPrime performs n Miller-Rabin tests to check whether z is prime.
// If it returns true, z is prime with probability 1 - 1/4^n.
// If it returns false, z is not prime.
@@ -508,8 +619,7 @@ func ProbablyPrime(z *Int, n int) bool {
return !z.neg && z.abs.probablyPrime(n)
}
-
-// Rand sets z to a pseudo-random number in [0, n) and returns z.
+// Rand sets z to a pseudo-random number in [0, n) and returns z.
func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
z.neg = false
if n.neg == true || len(n.abs) == 0 {
@@ -520,7 +630,6 @@ func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
return z
}
-
// ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where
// p is a prime) and returns z.
func (z *Int) ModInverse(g, p *Int) *Int {
@@ -534,7 +643,6 @@ func (z *Int) ModInverse(g, p *Int) *Int {
return z
}
-
// Lsh sets z = x << n and returns z.
func (z *Int) Lsh(x *Int, n uint) *Int {
z.abs = z.abs.shl(x.abs, n)
@@ -542,7 +650,6 @@ func (z *Int) Lsh(x *Int, n uint) *Int {
return z
}
-
// Rsh sets z = x >> n and returns z.
func (z *Int) Rsh(x *Int, n uint) *Int {
if x.neg {
@@ -559,6 +666,39 @@ func (z *Int) Rsh(x *Int, n uint) *Int {
return z
}
+// Bit returns the value of the i'th bit of z. That is, it
+// returns (z>>i)&1. The bit index i must be >= 0.
+func (z *Int) Bit(i int) uint {
+ if i < 0 {
+ panic("negative bit index")
+ }
+ if z.neg {
+ t := nat{}.sub(z.abs, natOne)
+ return t.bit(uint(i)) ^ 1
+ }
+
+ return z.abs.bit(uint(i))
+}
+
+// SetBit sets the i'th bit of z to bit and returns z.
+// That is, if bit is 1 SetBit sets z = x | (1 << i);
+// if bit is 0 it sets z = x &^ (1 << i). If bit is not 0 or 1,
+// SetBit will panic.
+func (z *Int) SetBit(x *Int, i int, b uint) *Int {
+ if i < 0 {
+ panic("negative bit index")
+ }
+ if x.neg {
+ t := z.abs.sub(x.abs, natOne)
+ t = t.setBit(t, uint(i), b^1)
+ z.abs = t.add(t, natOne)
+ z.neg = len(z.abs) > 0
+ return z
+ }
+ z.abs = z.abs.setBit(x.abs, uint(i), b)
+ z.neg = false
+ return z
+}
// And sets z = x & y and returns z.
func (z *Int) And(x, y *Int) *Int {
@@ -590,7 +730,6 @@ func (z *Int) And(x, y *Int) *Int {
return z
}
-
// AndNot sets z = x &^ y and returns z.
func (z *Int) AndNot(x, y *Int) *Int {
if x.neg == y.neg {
@@ -624,7 +763,6 @@ func (z *Int) AndNot(x, y *Int) *Int {
return z
}
-
// Or sets z = x | y and returns z.
func (z *Int) Or(x, y *Int) *Int {
if x.neg == y.neg {
@@ -655,7 +793,6 @@ func (z *Int) Or(x, y *Int) *Int {
return z
}
-
// Xor sets z = x ^ y and returns z.
func (z *Int) Xor(x, y *Int) *Int {
if x.neg == y.neg {
@@ -686,7 +823,6 @@ func (z *Int) Xor(x, y *Int) *Int {
return z
}
-
// Not sets z = ^x and returns z.
func (z *Int) Not(x *Int) *Int {
if x.neg {
@@ -702,15 +838,14 @@ func (z *Int) Not(x *Int) *Int {
return z
}
-
// Gob codec version. Permits backward-compatible changes to the encoding.
-const version byte = 1
+const intGobVersion byte = 1
// GobEncode implements the gob.GobEncoder interface.
func (z *Int) GobEncode() ([]byte, os.Error) {
- buf := make([]byte, len(z.abs)*_S+1) // extra byte for version and sign bit
+ buf := make([]byte, 1+len(z.abs)*_S) // extra byte for version and sign bit
i := z.abs.bytes(buf) - 1 // i >= 0
- b := version << 1 // make space for sign bit
+ b := intGobVersion << 1 // make space for sign bit
if z.neg {
b |= 1
}
@@ -718,14 +853,13 @@ func (z *Int) GobEncode() ([]byte, os.Error) {
return buf[i:], nil
}
-
// GobDecode implements the gob.GobDecoder interface.
func (z *Int) GobDecode(buf []byte) os.Error {
if len(buf) == 0 {
return os.NewError("Int.GobDecode: no data")
}
b := buf[0]
- if b>>1 != version {
+ if b>>1 != intGobVersion {
return os.NewError(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
}
z.neg = b&1 != 0
generated by cgit v1.1 at 2025-04-15 00:40:01 +0000