summaryrefslogtreecommitdiff
path: root/src/pkg/big
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/big')
-rw-r--r--src/pkg/big/arith.go4
-rw-r--r--src/pkg/big/arith_386.s8
-rw-r--r--src/pkg/big/arith_amd64.s12
-rw-r--r--src/pkg/big/arith_arm.s12
-rw-r--r--src/pkg/big/arith_decl.go4
-rw-r--r--src/pkg/big/arith_test.go19
-rwxr-xr-xsrc/pkg/big/int.go204
-rwxr-xr-xsrc/pkg/big/int_test.go246
-rwxr-xr-xsrc/pkg/big/nat.go358
-rwxr-xr-xsrc/pkg/big/nat_test.go413
-rw-r--r--src/pkg/big/rat.go89
-rw-r--r--src/pkg/big/rat_test.go68
12 files changed, 1260 insertions, 177 deletions
diff --git a/src/pkg/big/arith.go b/src/pkg/big/arith.go
index df3808f5e..b9aeea968 100644
--- a/src/pkg/big/arith.go
+++ b/src/pkg/big/arith.go
@@ -188,7 +188,7 @@ func subVW_g(z, x []Word, y Word) (c Word) {
}
-func shlVW_g(z, x []Word, s Word) (c Word) {
+func shlVU_g(z, x []Word, s uint) (c Word) {
if n := len(z); n > 0 {
ŝ := _W - s
w1 := x[n-1]
@@ -204,7 +204,7 @@ func shlVW_g(z, x []Word, s Word) (c Word) {
}
-func shrVW_g(z, x []Word, s Word) (c Word) {
+func shrVU_g(z, x []Word, s uint) (c Word) {
if n := len(z); n > 0 {
ŝ := _W - s
w1 := x[0]
diff --git a/src/pkg/big/arith_386.s b/src/pkg/big/arith_386.s
index 21521635b..07c07b02c 100644
--- a/src/pkg/big/arith_386.s
+++ b/src/pkg/big/arith_386.s
@@ -118,8 +118,8 @@ E4: CMPL BX, BP // i < n
RET
-// func shlVW(z, x []Word, s Word) (c Word)
-TEXT ·shlVW(SB),7,$0
+// func shlVU(z, x []Word, s uint) (c Word)
+TEXT ·shlVU(SB),7,$0
MOVL n+4(FP), BX // i = n
SUBL $1, BX // i--
JL X8b // i < 0 (n <= 0)
@@ -153,8 +153,8 @@ X8b: MOVL $0, c+28(FP)
RET
-// func shrVW(z, x []Word, s Word) (c Word)
-TEXT ·shrVW(SB),7,$0
+// func shrVU(z, x []Word, s uint) (c Word)
+TEXT ·shrVU(SB),7,$0
MOVL n+4(FP), BP
SUBL $1, BP // n--
JL X9b // n < 0 (n <= 0)
diff --git a/src/pkg/big/arith_amd64.s b/src/pkg/big/arith_amd64.s
index c740565a7..89b65f38a 100644
--- a/src/pkg/big/arith_amd64.s
+++ b/src/pkg/big/arith_amd64.s
@@ -120,8 +120,8 @@ E4: CMPQ BX, R11 // i < n
RET
-// func shlVW(z, x []Word, s Word) (c Word)
-TEXT ·shlVW(SB),7,$0
+// func shlVU(z, x []Word, s uint) (c Word)
+TEXT ·shlVU(SB),7,$0
MOVL n+8(FP), BX // i = n
SUBL $1, BX // i--
JL X8b // i < 0 (n <= 0)
@@ -129,7 +129,7 @@ TEXT ·shlVW(SB),7,$0
// n > 0
MOVQ z+0(FP), R10
MOVQ x+16(FP), R8
- MOVQ s+32(FP), CX
+ MOVL s+32(FP), CX
MOVQ (R8)(BX*8), AX // w1 = x[n-1]
MOVQ $0, DX
SHLQ CX, DX:AX // w1>>ŝ
@@ -155,8 +155,8 @@ X8b: MOVQ $0, c+40(FP)
RET
-// func shrVW(z, x []Word, s Word) (c Word)
-TEXT ·shrVW(SB),7,$0
+// func shrVU(z, x []Word, s uint) (c Word)
+TEXT ·shrVU(SB),7,$0
MOVL n+8(FP), R11
SUBL $1, R11 // n--
JL X9b // n < 0 (n <= 0)
@@ -164,7 +164,7 @@ TEXT ·shrVW(SB),7,$0
// n > 0
MOVQ z+0(FP), R10
MOVQ x+16(FP), R8
- MOVQ s+32(FP), CX
+ MOVL s+32(FP), CX
MOVQ (R8), AX // w1 = x[0]
MOVQ $0, DX
SHRQ CX, DX:AX // w1<<ŝ
diff --git a/src/pkg/big/arith_arm.s b/src/pkg/big/arith_arm.s
index e4a9a962c..60abe6eaa 100644
--- a/src/pkg/big/arith_arm.s
+++ b/src/pkg/big/arith_arm.s
@@ -97,6 +97,7 @@ E3:
RET
+// func subVW(z, x []Word, y Word) (c Word)
TEXT ·subVW(SB),7,$0
MOVW z+0(FP), R1
MOVW x+12(FP), R2
@@ -131,8 +132,8 @@ E4:
RET
-// func shlVW(z, x []Word, s Word) (c Word)
-TEXT ·shlVW(SB),7,$0
+// func shlVU(z, x []Word, s uint) (c Word)
+TEXT ·shlVU(SB),7,$0
MOVW n+4(FP), R5
CMP $0, R5
BEQ X7
@@ -180,7 +181,8 @@ X7:
RET
-TEXT ·shrVW(SB),7,$0
+// func shrVU(z, x []Word, s uint) (c Word)
+TEXT ·shrVU(SB),7,$0
MOVW n+4(FP), R5
CMP $0, R5
BEQ X6
@@ -229,6 +231,7 @@ X6:
RET
+// func mulAddVWW(z, x []Word, y, r Word) (c Word)
TEXT ·mulAddVWW(SB),7,$0
MOVW $0, R0
MOVW z+0(FP), R1
@@ -256,6 +259,7 @@ E8:
RET
+// func addMulVVW(z, x []Word, y Word) (c Word)
TEXT ·addMulVVW(SB),7,$0
MOVW $0, R0
MOVW z+0(FP), R1
@@ -286,11 +290,13 @@ E9:
RET
+// divWVW(z* Word, xn Word, x []Word, y Word) (r Word)
TEXT ·divWVW(SB),7,$0
// ARM has no multiword division, so use portable code.
B ·divWVW_g(SB)
+// func divWW(x1, x0, y Word) (q, r Word)
TEXT ·divWW(SB),7,$0
// ARM has no multiword division, so use portable code.
B ·divWW_g(SB)
diff --git a/src/pkg/big/arith_decl.go b/src/pkg/big/arith_decl.go
index c456d5f67..95fcd8b94 100644
--- a/src/pkg/big/arith_decl.go
+++ b/src/pkg/big/arith_decl.go
@@ -11,8 +11,8 @@ func addVV(z, x, y []Word) (c Word)
func subVV(z, x, y []Word) (c Word)
func addVW(z, x []Word, y Word) (c Word)
func subVW(z, x []Word, y Word) (c Word)
-func shlVW(z, x []Word, s Word) (c Word)
-func shrVW(z, x []Word, s Word) (c Word)
+func shlVU(z, x []Word, s uint) (c Word)
+func shrVU(z, x []Word, s uint) (c Word)
func mulAddVWW(z, x []Word, y, r Word) (c Word)
func addMulVVW(z, x []Word, y Word) (c Word)
func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
diff --git a/src/pkg/big/arith_test.go b/src/pkg/big/arith_test.go
index 934b302df..f3e2d4735 100644
--- a/src/pkg/big/arith_test.go
+++ b/src/pkg/big/arith_test.go
@@ -185,6 +185,13 @@ func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
}
+func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
+ return func(z, x []Word, s Word) (c Word) {
+ return f(z, x, uint(s))
+ }
+}
+
+
func TestFunVW(t *testing.T) {
for _, a := range sumVW {
arg := a
@@ -196,16 +203,20 @@ func TestFunVW(t *testing.T) {
testFunVW(t, "subVW", subVW, arg)
}
+ shlVW_g := makeFunVW(shlVU_g)
+ shlVW := makeFunVW(shlVU)
for _, a := range lshVW {
arg := a
- testFunVW(t, "shlVW_g", shlVW_g, arg)
- testFunVW(t, "shlVW", shlVW, arg)
+ testFunVW(t, "shlVU_g", shlVW_g, arg)
+ testFunVW(t, "shlVU", shlVW, arg)
}
+ shrVW_g := makeFunVW(shrVU_g)
+ shrVW := makeFunVW(shrVU)
for _, a := range rshVW {
arg := a
- testFunVW(t, "shrVW_g", shrVW_g, arg)
- testFunVW(t, "shrVW", shrVW, arg)
+ testFunVW(t, "shrVU_g", shrVW_g, arg)
+ testFunVW(t, "shrVU", shrVW, arg)
}
}
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go
index f1ea7b1c2..22bdf8d2f 100755
--- a/src/pkg/big/int.go
+++ b/src/pkg/big/int.go
@@ -8,8 +8,10 @@ package big
import (
"fmt"
+ "io"
"os"
"rand"
+ "strings"
)
// An Int represents a signed multi-precision integer.
@@ -309,47 +311,134 @@ func (x *Int) Cmp(y *Int) (r int) {
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
}
// 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).
//
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
}
+
+ // determine format
+ format := "%s"
+ if s.Flag('#') {
+ switch ch {
+ case 'o':
+ format = "0%s"
+ case 'x':
+ format = "0x%s"
+ case 'X':
+ format = "0X%s"
+ }
+ }
if x.neg {
- fmt.Fprint(s, "-")
+ format = "-" + format
+ }
+
+ fmt.Fprintf(s, format, x.abs.string(cs))
+}
+
+
+// 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()
+ }
+
+ // 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 {
+ 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.ErrorString("Int.Scan: invalid verb")
}
- fmt.Fprint(s, x.abs.string(fmtbase(ch)))
+ _, _, err := z.scan(s, base)
+ return err
}
-// Int64 returns the int64 representation of z.
-// If z cannot be represented in an int64, the result is undefined.
+// 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
@@ -369,32 +458,19 @@ func (x *Int) Int64() int64 {
// 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 {
+ r := strings.NewReader(s)
+ _, _, err := z.scan(r, base)
+ if err != nil {
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) {
- 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
}
@@ -560,6 +636,42 @@ func (z *Int) Rsh(x *Int, n uint) *Int {
}
+// 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 {
if x.neg == y.neg {
@@ -704,13 +816,13 @@ func (z *Int) Not(x *Int) *Int {
// 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
}
@@ -722,11 +834,11 @@ func (z *Int) GobEncode() ([]byte, os.Error) {
// 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")
+ return os.ErrorString("Int.GobDecode: no data")
}
b := buf[0]
- if b>>1 != version {
- return os.NewError(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
+ if b>>1 != intGobVersion {
+ return os.ErrorString(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
}
z.neg = b&1 != 0
z.abs = z.abs.setBytes(buf[1:])
diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go
index 9c19dd5da..58a55030d 100755
--- a/src/pkg/big/int_test.go
+++ b/src/pkg/big/int_test.go
@@ -348,6 +348,98 @@ func TestSetString(t *testing.T) {
}
+var formatTests = []struct {
+ input string
+ format string
+ output string
+}{
+ {"<nil>", "%x", "<nil>"},
+ {"<nil>", "%#x", "<nil>"},
+ {"<nil>", "%#y", "%!y(big.Int=<nil>)"},
+
+ {"10", "%b", "1010"},
+ {"10", "%o", "12"},
+ {"10", "%d", "10"},
+ {"10", "%v", "10"},
+ {"10", "%x", "a"},
+ {"10", "%X", "A"},
+ {"-10", "%X", "-A"},
+ {"10", "%y", "%!y(big.Int=10)"},
+ {"-10", "%y", "%!y(big.Int=-10)"},
+
+ {"10", "%#b", "1010"},
+ {"10", "%#o", "012"},
+ {"10", "%#d", "10"},
+ {"10", "%#v", "10"},
+ {"10", "%#x", "0xa"},
+ {"10", "%#X", "0XA"},
+ {"-10", "%#X", "-0XA"},
+ {"10", "%#y", "%!y(big.Int=10)"},
+ {"-10", "%#y", "%!y(big.Int=-10)"},
+}
+
+
+func TestFormat(t *testing.T) {
+ for i, test := range formatTests {
+ var x *Int
+ if test.input != "<nil>" {
+ var ok bool
+ x, ok = new(Int).SetString(test.input, 0)
+ if !ok {
+ t.Errorf("#%d failed reading input %s", i, test.input)
+ }
+ }
+ output := fmt.Sprintf(test.format, x)
+ if output != test.output {
+ t.Errorf("#%d got %s; want %s", i, output, test.output)
+ }
+ }
+}
+
+
+var scanTests = []struct {
+ input string
+ format string
+ output string
+ remaining int
+}{
+ {"1010", "%b", "10", 0},
+ {"0b1010", "%v", "10", 0},
+ {"12", "%o", "10", 0},
+ {"012", "%v", "10", 0},
+ {"10", "%d", "10", 0},
+ {"10", "%v", "10", 0},
+ {"a", "%x", "10", 0},
+ {"0xa", "%v", "10", 0},
+ {"A", "%X", "10", 0},
+ {"-A", "%X", "-10", 0},
+ {"+0b1011001", "%v", "89", 0},
+ {"0xA", "%v", "10", 0},
+ {"0 ", "%v", "0", 1},
+ {"2+3", "%v", "2", 2},
+ {"0XABC 12", "%v", "2748", 3},
+}
+
+
+func TestScan(t *testing.T) {
+ var buf bytes.Buffer
+ for i, test := range scanTests {
+ x := new(Int)
+ buf.Reset()
+ buf.WriteString(test.input)
+ if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
+ t.Errorf("#%d error: %s", i, err.String())
+ }
+ if x.String() != test.output {
+ t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
+ }
+ if buf.Len() != test.remaining {
+ t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
+ }
+ }
+}
+
+
// Examples from the Go Language Spec, section "Arithmetic operators"
var divisionSignsTests = []struct {
x, y int64
@@ -985,6 +1077,152 @@ func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
}
+func altBit(x *Int, i int) uint {
+ z := new(Int).Rsh(x, uint(i))
+ z = z.And(z, NewInt(1))
+ if z.Cmp(new(Int)) != 0 {
+ return 1
+ }
+ return 0
+}
+
+
+func altSetBit(z *Int, x *Int, i int, b uint) *Int {
+ one := NewInt(1)
+ m := one.Lsh(one, uint(i))
+ switch b {
+ case 1:
+ return z.Or(x, m)
+ case 0:
+ return z.AndNot(x, m)
+ }
+ panic("set bit is not 0 or 1")
+}
+
+
+func testBitset(t *testing.T, x *Int) {
+ n := x.BitLen()
+ z := new(Int).Set(x)
+ z1 := new(Int).Set(x)
+ for i := 0; i < n+10; i++ {
+ old := z.Bit(i)
+ old1 := altBit(z1, i)
+ if old != old1 {
+ t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
+ }
+ z := new(Int).SetBit(z, i, 1)
+ z1 := altSetBit(new(Int), z1, i, 1)
+ if z.Bit(i) == 0 {
+ t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
+ }
+ if z.Cmp(z1) != 0 {
+ t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
+ }
+ z.SetBit(z, i, 0)
+ altSetBit(z1, z1, i, 0)
+ if z.Bit(i) != 0 {
+ t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
+ }
+ if z.Cmp(z1) != 0 {
+ t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
+ }
+ altSetBit(z1, z1, i, old)
+ z.SetBit(z, i, old)
+ if z.Cmp(z1) != 0 {
+ t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
+ }
+ }
+ if z.Cmp(x) != 0 {
+ t.Errorf("bitset: got %s want %s", z, x)
+ }
+}
+
+
+var bitsetTests = []struct {
+ x string
+ i int
+ b uint
+}{
+ {"0", 0, 0},
+ {"0", 200, 0},
+ {"1", 0, 1},
+ {"1", 1, 0},
+ {"-1", 0, 1},
+ {"-1", 200, 1},
+ {"0x2000000000000000000000000000", 108, 0},
+ {"0x2000000000000000000000000000", 109, 1},
+ {"0x2000000000000000000000000000", 110, 0},
+ {"-0x2000000000000000000000000001", 108, 1},
+ {"-0x2000000000000000000000000001", 109, 0},
+ {"-0x2000000000000000000000000001", 110, 1},
+}
+
+
+func TestBitSet(t *testing.T) {
+ for _, test := range bitwiseTests {
+ x := new(Int)
+ x.SetString(test.x, 0)
+ testBitset(t, x)
+ x = new(Int)
+ x.SetString(test.y, 0)
+ testBitset(t, x)
+ }
+ for i, test := range bitsetTests {
+ x := new(Int)
+ x.SetString(test.x, 0)
+ b := x.Bit(test.i)
+ if b != test.b {
+
+ t.Errorf("#%d want %v got %v", i, test.b, b)
+ }
+ }
+}
+
+
+func BenchmarkBitset(b *testing.B) {
+ z := new(Int)
+ z.SetBit(z, 512, 1)
+ b.ResetTimer()
+ b.StartTimer()
+ for i := b.N - 1; i >= 0; i-- {
+ z.SetBit(z, i&512, 1)
+ }
+}
+
+
+func BenchmarkBitsetNeg(b *testing.B) {
+ z := NewInt(-1)
+ z.SetBit(z, 512, 0)
+ b.ResetTimer()
+ b.StartTimer()
+ for i := b.N - 1; i >= 0; i-- {
+ z.SetBit(z, i&512, 0)
+ }
+}
+
+
+func BenchmarkBitsetOrig(b *testing.B) {
+ z := new(Int)
+ altSetBit(z, z, 512, 1)
+ b.ResetTimer()
+ b.StartTimer()
+ for i := b.N - 1; i >= 0; i-- {
+ altSetBit(z, z, i&512, 1)
+ }
+}
+
+
+func BenchmarkBitsetNegOrig(b *testing.B) {
+ z := NewInt(-1)
+ altSetBit(z, z, 512, 0)
+ b.ResetTimer()
+ b.StartTimer()
+ for i := b.N - 1; i >= 0; i-- {
+ altSetBit(z, z, i&512, 0)
+ }
+}
+
+
func TestBitwise(t *testing.T) {
x := new(Int)
y := new(Int)
@@ -1019,6 +1257,7 @@ var notTests = []struct {
},
}
+
func TestNot(t *testing.T) {
in := new(Int)
out := new(Int)
@@ -1047,6 +1286,7 @@ var modInverseTests = []struct {
{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
}
+
func TestModInverse(t *testing.T) {
var element, prime Int
one := NewInt(1)
@@ -1063,6 +1303,7 @@ func TestModInverse(t *testing.T) {
}
+// used by TestIntGobEncoding and TestRatGobEncoding
var gobEncodingTests = []string{
"0",
"1",
@@ -1073,7 +1314,7 @@ var gobEncodingTests = []string{
"298472983472983471903246121093472394872319615612417471234712061",
}
-func TestGobEncoding(t *testing.T) {
+func TestIntGobEncoding(t *testing.T) {
var medium bytes.Buffer
enc := gob.NewEncoder(&medium)
dec := gob.NewDecoder(&medium)
@@ -1081,7 +1322,8 @@ func TestGobEncoding(t *testing.T) {
for j := 0; j < 2; j++ {
medium.Reset() // empty buffer for each test case (in case of failures)
stest := test
- if j == 0 {
+ if j != 0 {
+ // negative numbers
stest = "-" + test
}
var tx Int
diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index 4848d427b..734568e06 100755
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -18,7 +18,12 @@ package big
// These are the building blocks for the operations on signed integers
// and rationals.
-import "rand"
+import (
+ "io"
+ "os"
+ "rand"
+)
+
// An unsigned integer x of the form
//
@@ -545,9 +550,14 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
u.clear()
// D1.
- shift := Word(leadingZeros(v[n-1]))
- shlVW(v, v, shift)
- u[len(uIn)] = shlVW(u[0:len(uIn)], uIn, shift)
+ shift := leadingZeros(v[n-1])
+ if shift > 0 {
+ // do not modify v, it may be used by another goroutine simultaneously
+ v1 := make(nat, n)
+ shlVU(v1, v, shift)
+ v = v1
+ }
+ u[len(uIn)] = shlVU(u[0:len(uIn)], uIn, shift)
// D2.
for j := m; j >= 0; j-- {
@@ -586,8 +596,7 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
}
q = q.norm()
- shrVW(u, u, shift)
- shrVW(v, v, shift)
+ shrVU(u, u, shift)
r = u.norm()
return q, r
@@ -603,96 +612,252 @@ func (x nat) bitLen() int {
}
-func hexValue(ch byte) int {
- var d byte
+// MaxBase is the largest number base accepted for string conversions.
+const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1
+
+
+func hexValue(ch int) Word {
+ d := MaxBase + 1 // illegal base
switch {
case '0' <= ch && ch <= '9':
d = ch - '0'
- case 'a' <= ch && ch <= 'f':
+ case 'a' <= ch && ch <= 'z':
d = ch - 'a' + 10
- case 'A' <= ch && ch <= 'F':
+ case 'A' <= ch && ch <= 'Z':
d = ch - 'A' + 10
- default:
- return -1
}
- return int(d)
+ return Word(d)
}
-// scan returns the natural number corresponding to the
-// longest possible prefix of s representing a natural number in a
-// given conversion base, the actual conversion base used, and the
-// prefix length. The syntax of natural numbers follows the syntax
-// of unsigned integer literals in Go.
+// scan sets z to the natural number corresponding to the longest possible prefix
+// read from r representing an unsigned integer 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
+// unsigned 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, 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 nat) scan(s string, base int) (nat, int, int) {
+func (z nat) scan(r io.RuneScanner, base int) (nat, int, os.Error) {
+ // reject illegal bases
+ if base < 0 || base == 1 || MaxBase < base {
+ return z, 0, os.ErrorString("illegal number base")
+ }
+
+ // one char look-ahead
+ ch, _, err := r.ReadRune()
+ if err != nil {
+ return z, 0, err
+ }
+
// determine base if necessary
- i, n := 0, len(s)
+ b := Word(base)
if base == 0 {
- base = 10
- if n > 0 && s[0] == '0' {
- base, i = 8, 1
- if n > 1 {
- switch s[1] {
+ b = 10
+ if ch == '0' {
+ switch ch, _, err = r.ReadRune(); err {
+ case nil:
+ b = 8
+ switch ch {
case 'x', 'X':
- base, i = 16, 2
+ b = 16
case 'b', 'B':
- base, i = 2, 2
+ b = 2
}
+ if b == 2 || b == 16 {
+ if ch, _, err = r.ReadRune(); err != nil {
+ return z, 0, err
+ }
+ }
+ case os.EOF:
+ return z, 10, nil
+ default:
+ return z, 10, err
}
}
}
- // reject illegal bases or strings consisting only of prefix
- if base < 2 || 16 < base || (base != 8 && i >= n) {
- return z, 0, 0
- }
-
// convert string
+ // - group as many digits d as possible together into a "super-digit" dd with "super-base" bb
+ // - only when bb does not fit into a word anymore, do a full number mulAddWW using bb and dd
z = z.make(0)
- for ; i < n; i++ {
- d := hexValue(s[i])
- if 0 <= d && d < base {
- z = z.mulAddWW(z, Word(base), Word(d))
+ bb := Word(1)
+ dd := Word(0)
+ for max := _M / b; ; {
+ d := hexValue(ch)
+ if d >= b {
+ r.UnreadRune() // ch does not belong to number anymore
+ break
+ }
+
+ if bb <= max {
+ bb *= b
+ dd = dd*b + d
} else {
+ // bb * b would overflow
+ z = z.mulAddWW(z, bb, dd)
+ bb = b
+ dd = d
+ }
+
+ if ch, _, err = r.ReadRune(); err != nil {
+ if err != os.EOF {
+ return z, int(b), err
+ }
break
}
}
- return z.norm(), base, i
+ switch {
+ case bb > 1:
+ // there was at least one mantissa digit
+ z = z.mulAddWW(z, bb, dd)
+ case base == 0 && b == 8:
+ // there was only the octal prefix 0 (possibly followed by digits > 7);
+ // return base 10, not 8
+ return z, 10, nil
+ case base != 0 || b != 8:
+ // there was neither a mantissa digit nor the octal prefix 0
+ return z, int(b), os.ErrorString("syntax error scanning number")
+ }
+
+ return z.norm(), int(b), nil
}
-// string converts x to a string for a given base, with 2 <= base <= 16.
-// TODO(gri) in the style of the other routines, perhaps this should take
-// a []byte buffer and return it
-func (x nat) string(base int) string {
- if base < 2 || 16 < base {
- panic("illegal base")
- }
+// Character sets for string conversion.
+const (
+ lowercaseDigits = "0123456789abcdefghijklmnopqrstuvwxyz"
+ uppercaseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+)
- if len(x) == 0 {
- return "0"
+
+// decimalString returns a decimal representation of x.
+// It calls x.string with the charset "0123456789".
+func (x nat) decimalString() string {
+ return x.string(lowercaseDigits[0:10])
+}
+
+
+// string converts x to a string using digits from a charset; a digit with
+// value d is represented by charset[d]. The conversion base is determined
+// by len(charset), which must be >= 2.
+func (x nat) string(charset string) string {
+ b := Word(len(charset))
+
+ // special cases
+ switch {
+ case b < 2 || b > 256:
+ panic("illegal base")
+ case len(x) == 0:
+ return string(charset[0])
}
// allocate buffer for conversion
- i := x.bitLen()/log2(Word(base)) + 1 // +1: round up
+ i := x.bitLen()/log2(b) + 1 // +1: round up
s := make([]byte, i)
- // don't destroy x
+ // special case: power of two bases can avoid divisions completely
+ if b == b&-b {
+ // shift is base-b digit size in bits
+ shift := uint(trailingZeroBits(b)) // shift > 0 because b >= 2
+ mask := Word(1)<<shift - 1
+ w := x[0]
+ nbits := uint(_W) // number of unprocessed bits in w
+
+ // convert less-significant words
+ for k := 1; k < len(x); k++ {
+ // convert full digits
+ for nbits >= shift {
+ i--
+ s[i] = charset[w&mask]
+ w >>= shift
+ nbits -= shift
+ }
+
+ // convert any partial leading digit and advance to next word
+ if nbits == 0 {
+ // no partial digit remaining, just advance
+ w = x[k]
+ nbits = _W
+ } else {
+ // partial digit in current (k-1) and next (k) word
+ w |= x[k] << nbits
+ i--
+ s[i] = charset[w&mask]
+
+ // advance
+ w = x[k] >> (shift - nbits)
+ nbits = _W - (shift - nbits)
+ }
+ }
+
+ // convert digits of most-significant word (omit leading zeros)
+ for nbits >= 0 && w != 0 {
+ i--
+ s[i] = charset[w&mask]
+ w >>= shift
+ nbits -= shift
+ }
+
+ return string(s[i:])
+ }
+
+ // general case: extract groups of digits by multiprecision division
+
+ // maximize ndigits where b**ndigits < 2^_W; bb (big base) is b**ndigits
+ bb := Word(1)
+ ndigits := 0
+ for max := Word(_M / b); bb <= max; bb *= b {
+ ndigits++
+ }
+
+ // preserve x, create local copy for use in repeated divisions
q := nat(nil).set(x)
+ var r Word
// convert
- for len(q) > 0 {
- i--
- var r Word
- q, r = q.divW(q, Word(base))
- s[i] = "0123456789abcdef"[r]
+ if b == 10 { // hard-coding for 10 here speeds this up by 1.25x
+ for len(q) > 0 {
+ // extract least significant, base bb "digit"
+ q, r = q.divW(q, bb) // N.B. >82% of time is here. Optimize divW
+ if len(q) == 0 {
+ // skip leading zeros in most-significant group of digits
+ for j := 0; j < ndigits && r != 0; j++ {
+ i--
+ s[i] = charset[r%10]
+ r /= 10
+ }
+ } else {
+ for j := 0; j < ndigits; j++ {
+ i--
+ s[i] = charset[r%10]
+ r /= 10
+ }
+ }
+ }
+ } else {
+ for len(q) > 0 {
+ // extract least significant group of digits
+ q, r = q.divW(q, bb) // N.B. >82% of time is here. Optimize divW
+ if len(q) == 0 {
+ // skip leading zeros in most-significant group of digits
+ for j := 0; j < ndigits && r != 0; j++ {
+ i--
+ s[i] = charset[r%b]
+ r /= b
+ }
+ } else {
+ for j := 0; j < ndigits; j++ {
+ i--
+ s[i] = charset[r%b]
+ r /= b
+ }
+ }
+ }
}
return string(s[i:])
@@ -715,13 +880,14 @@ var deBruijn64Lookup = []byte{
54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
}
+
// trailingZeroBits returns the number of consecutive zero bits on the right
// side of the given Word.
// See Knuth, volume 4, section 7.3.1
func trailingZeroBits(x Word) int {
// x & -x leaves only the right-most bit set in the word. Let k be the
// index of that bit. Since only a single bit is set, the value is two
- // to the power of k. Multipling by a power of two is equivalent to
+ // to the power of k. Multiplying by a power of two is equivalent to
// left shifting, in this case by k bits. The de Bruijn constant is
// such that all six bit, consecutive substrings are distinct.
// Therefore, if we have a left shifted version of this constant we can
@@ -750,7 +916,7 @@ func (z nat) shl(x nat, s uint) nat {
n := m + int(s/_W)
z = z.make(n + 1)
- z[n] = shlVW(z[n-m:n], x, Word(s%_W))
+ z[n] = shlVU(z[n-m:n], x, s%_W)
z[0 : n-m].clear()
return z.norm()
@@ -767,12 +933,49 @@ func (z nat) shr(x nat, s uint) nat {
// n > 0
z = z.make(n)
- shrVW(z, x[m-n:], Word(s%_W))
+ shrVU(z, x[m-n:], s%_W)
return z.norm()
}
+func (z nat) setBit(x nat, i uint, b uint) nat {
+ j := int(i / _W)
+ m := Word(1) << (i % _W)
+ n := len(x)
+ switch b {
+ case 0:
+ z = z.make(n)
+ copy(z, x)
+ if j >= n {
+ // no need to grow
+ return z
+ }
+ z[j] &^= m
+ return z.norm()
+ case 1:
+ if j >= n {
+ n = j + 1
+ }
+ z = z.make(n)
+ copy(z, x)
+ z[j] |= m
+ // no need to normalize
+ return z
+ }
+ panic("set bit is not 0 or 1")
+}
+
+
+func (z nat) bit(i uint) uint {
+ j := int(i / _W)
+ if j >= len(z) {
+ return 0
+ }
+ return uint(z[j] >> (i % _W) & 1)
+}
+
+
func (z nat) and(x, y nat) nat {
m := len(x)
n := len(y)
@@ -849,7 +1052,9 @@ func (z nat) xor(x, y nat) nat {
// greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2)
-func greaterThan(x1, x2, y1, y2 Word) bool { return x1 > y1 || x1 == y1 && x2 > y2 }
+func greaterThan(x1, x2, y1, y2 Word) bool {
+ return x1 > y1 || x1 == y1 && x2 > y2
+}
// modW returns x % d.
@@ -861,25 +1066,26 @@ func (x nat) modW(d Word) (r Word) {
}
-// powersOfTwoDecompose finds q and k such that q * 1<<k = n and q is odd.
-func (n nat) powersOfTwoDecompose() (q nat, k Word) {
- if len(n) == 0 {
- return n, 0
+// powersOfTwoDecompose finds q and k with x = q * 1<<k and q is odd, or q and k are 0.
+func (x nat) powersOfTwoDecompose() (q nat, k int) {
+ if len(x) == 0 {
+ return x, 0
}
- zeroWords := 0
- for n[zeroWords] == 0 {
- zeroWords++
+ // One of the words must be non-zero by definition,
+ // so this loop will terminate with i < len(x), and
+ // i is the number of 0 words.
+ i := 0
+ for x[i] == 0 {
+ i++
}
- // One of the words must be non-zero by invariant, therefore
- // zeroWords < len(n).
- x := trailingZeroBits(n[zeroWords])
+ n := trailingZeroBits(x[i]) // x[i] != 0
- q = q.make(len(n) - zeroWords)
- shrVW(q, n[zeroWords:], Word(x))
- q = q.norm()
+ q = make(nat, len(x)-i)
+ shrVU(q, x[i:], uint(n))
- k = Word(_W*zeroWords + x)
+ q = q.norm()
+ k = i*_W + n
return
}
@@ -1050,7 +1256,7 @@ NextRandom:
if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 {
continue
}
- for j := Word(1); j < k; j++ {
+ for j := 1; j < k; j++ {
y = y.mul(y, y)
quotient, y = quotient.div(y, y, n)
if y.cmp(nm1) == 0 {
diff --git a/src/pkg/big/nat_test.go b/src/pkg/big/nat_test.go
index 0bcb94554..fd93592dd 100755
--- a/src/pkg/big/nat_test.go
+++ b/src/pkg/big/nat_test.go
@@ -4,7 +4,12 @@
package big
-import "testing"
+import (
+ "fmt"
+ "os"
+ "strings"
+ "testing"
+)
var cmpTests = []struct {
x, y nat
@@ -133,7 +138,7 @@ var mulRangesN = []struct {
func TestMulRangeN(t *testing.T) {
for i, r := range mulRangesN {
- prod := nat(nil).mulRange(r.a, r.b).string(10)
+ prod := nat(nil).mulRange(r.a, r.b).decimalString()
if prod != r.prod {
t.Errorf("#%d: got %s; want %s", i, prod, r.prod)
}
@@ -167,35 +172,402 @@ func BenchmarkMul(b *testing.B) {
}
-var tab = []struct {
- x nat
- b int
- s string
+func toString(x nat, charset string) string {
+ base := len(charset)
+
+ // special cases
+ switch {
+ case base < 2:
+ panic("illegal base")
+ case len(x) == 0:
+ return string(charset[0])
+ }
+
+ // allocate buffer for conversion
+ i := x.bitLen()/log2(Word(base)) + 1 // +1: round up
+ s := make([]byte, i)
+
+ // don't destroy x
+ q := nat(nil).set(x)
+
+ // convert
+ for len(q) > 0 {
+ i--
+ var r Word
+ q, r = q.divW(q, Word(base))
+ s[i] = charset[r]
+ }
+
+ return string(s[i:])
+}
+
+
+var strTests = []struct {
+ x nat // nat value to be converted
+ c string // conversion charset
+ s string // expected result
}{
- {nil, 10, "0"},
- {nat{1}, 10, "1"},
- {nat{10}, 10, "10"},
- {nat{1234567890}, 10, "1234567890"},
+ {nil, "01", "0"},
+ {nat{1}, "01", "1"},
+ {nat{0xc5}, "01", "11000101"},
+ {nat{03271}, lowercaseDigits[0:8], "3271"},
+ {nat{10}, lowercaseDigits[0:10], "10"},
+ {nat{1234567890}, uppercaseDigits[0:10], "1234567890"},
+ {nat{0xdeadbeef}, lowercaseDigits[0:16], "deadbeef"},
+ {nat{0xdeadbeef}, uppercaseDigits[0:16], "DEADBEEF"},
+ {nat{0x229be7}, lowercaseDigits[0:17], "1a2b3c"},
+ {nat{0x309663e6}, uppercaseDigits[0:32], "O9COV6"},
}
func TestString(t *testing.T) {
- for _, a := range tab {
- s := a.x.string(a.b)
+ for _, a := range strTests {
+ s := a.x.string(a.c)
if s != a.s {
t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
}
- x, b, n := nat(nil).scan(a.s, a.b)
+ x, b, err := nat(nil).scan(strings.NewReader(a.s), len(a.c))
+ if x.cmp(a.x) != 0 {
+ t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
+ }
+ if b != len(a.c) {
+ t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, len(a.c))
+ }
+ if err != nil {
+ t.Errorf("scan%+v\n\tgot error = %s", a, err)
+ }
+ }
+}
+
+
+var natScanTests = []struct {
+ s string // string to be scanned
+ base int // input base
+ x nat // expected nat
+ b int // expected base
+ ok bool // expected success
+ next int // next character (or 0, if at EOF)
+}{
+ // error: illegal base
+ {base: -1},
+ {base: 1},
+ {base: 37},
+
+ // error: no mantissa
+ {},
+ {s: "?"},
+ {base: 10},
+ {base: 36},
+ {s: "?", base: 10},
+ {s: "0x"},
+ {s: "345", base: 2},
+
+ // no errors
+ {"0", 0, nil, 10, true, 0},
+ {"0", 10, nil, 10, true, 0},
+ {"0", 36, nil, 36, true, 0},
+ {"1", 0, nat{1}, 10, true, 0},
+ {"1", 10, nat{1}, 10, true, 0},
+ {"0 ", 0, nil, 10, true, ' '},
+ {"08", 0, nil, 10, true, '8'},
+ {"018", 0, nat{1}, 8, true, '8'},
+ {"0b1", 0, nat{1}, 2, true, 0},
+ {"0b11000101", 0, nat{0xc5}, 2, true, 0},
+ {"03271", 0, nat{03271}, 8, true, 0},
+ {"10ab", 0, nat{10}, 10, true, 'a'},
+ {"1234567890", 0, nat{1234567890}, 10, true, 0},
+ {"xyz", 36, nat{(33*36+34)*36 + 35}, 36, true, 0},
+ {"xyz?", 36, nat{(33*36+34)*36 + 35}, 36, true, '?'},
+ {"0x", 16, nil, 16, true, 'x'},
+ {"0xdeadbeef", 0, nat{0xdeadbeef}, 16, true, 0},
+ {"0XDEADBEEF", 0, nat{0xdeadbeef}, 16, true, 0},
+}
+
+
+func TestScanBase(t *testing.T) {
+ for _, a := range natScanTests {
+ r := strings.NewReader(a.s)
+ x, b, err := nat(nil).scan(r, a.base)
+ if err == nil && !a.ok {
+ t.Errorf("scan%+v\n\texpected error", a)
+ }
+ if err != nil {
+ if a.ok {
+ t.Errorf("scan%+v\n\tgot error = %s", a, err)
+ }
+ continue
+ }
if x.cmp(a.x) != 0 {
t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
}
if b != a.b {
- t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.b)
+ t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.base)
}
- if n != len(a.s) {
- t.Errorf("scan%+v\n\tgot n = %d; want %d", a, n, len(a.s))
+ next, _, err := r.ReadRune()
+ if err == os.EOF {
+ next = 0
+ err = nil
}
+ if err == nil && next != a.next {
+ t.Errorf("scan%+v\n\tgot next = %q; want %q", a, next, a.next)
+ }
+ }
+}
+
+
+var pi = "3" +
+ "14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651" +
+ "32823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461" +
+ "28475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920" +
+ "96282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179" +
+ "31051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798" +
+ "60943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901" +
+ "22495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837" +
+ "29780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083" +
+ "81420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909" +
+ "21642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151" +
+ "55748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035" +
+ "63707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104" +
+ "75216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992" +
+ "45863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818" +
+ "34797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548" +
+ "16136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179" +
+ "04946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886" +
+ "26945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645" +
+ "99581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745" +
+ "53050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382" +
+ "68683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244" +
+ "13654976278079771569143599770012961608944169486855584840635342207222582848864815845602850601684273945226746767" +
+ "88952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288" +
+ "79710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821" +
+ "68299894872265880485756401427047755513237964145152374623436454285844479526586782105114135473573952311342716610" +
+ "21359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435" +
+ "06430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675" +
+ "14269123974894090718649423196156794520809514655022523160388193014209376213785595663893778708303906979207734672" +
+ "21825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539" +
+ "05796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007" +
+ "23055876317635942187312514712053292819182618612586732157919841484882916447060957527069572209175671167229109816" +
+ "90915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398" +
+ "31501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064" +
+ "20467525907091548141654985946163718027098199430992448895757128289059232332609729971208443357326548938239119325" +
+ "97463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100" +
+ "44929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915" +
+ "44110104468232527162010526522721116603966655730925471105578537634668206531098965269186205647693125705863566201" +
+ "85581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318" +
+ "58676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797" +
+ "27082668306343285878569830523580893306575740679545716377525420211495576158140025012622859413021647155097925923" +
+ "09907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111" +
+ "79042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043" +
+ "06332175182979866223717215916077166925474873898665494945011465406284336639379003976926567214638530673609657120" +
+ "91807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862" +
+ "94726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939" +
+ "78054193414473774418426312986080998886874132604721569516239658645730216315981931951673538129741677294786724229" +
+ "24654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001" +
+ "59377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541" +
+ "34189948544473456738316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759" +
+ "88281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267" +
+ "94561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337"
+
+
+// Test case for BenchmarkScanPi.
+func TestScanPi(t *testing.T) {
+ var x nat
+ z, _, err := x.scan(strings.NewReader(pi), 10)
+ if err != nil {
+ t.Errorf("scanning pi: %s", err)
+ }
+ if s := z.decimalString(); s != pi {
+ t.Errorf("scanning pi: got %s", s)
+ }
+}
+
+
+func BenchmarkScanPi(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ var x nat
+ x.scan(strings.NewReader(pi), 10)
+ }
+}
+
+
+const (
+ // 314**271
+ // base 2: 2249 digits
+ // base 8: 751 digits
+ // base 10: 678 digits
+ // base 16: 563 digits
+ shortBase = 314
+ shortExponent = 271
+
+ // 3141**2178
+ // base 2: 31577 digits
+ // base 8: 10527 digits
+ // base 10: 9507 digits
+ // base 16: 7895 digits
+ mediumBase = 3141
+ mediumExponent = 2718
+
+ // 3141**2178
+ // base 2: 406078 digits
+ // base 8: 135360 digits
+ // base 10: 122243 digits
+ // base 16: 101521 digits
+ longBase = 31415
+ longExponent = 27182
+)
+
+
+func BenchmarkScanShort2(b *testing.B) {
+ ScanHelper(b, 2, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanShort8(b *testing.B) {
+ ScanHelper(b, 8, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanSort10(b *testing.B) {
+ ScanHelper(b, 10, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanShort16(b *testing.B) {
+ ScanHelper(b, 16, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanMedium2(b *testing.B) {
+ ScanHelper(b, 2, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanMedium8(b *testing.B) {
+ ScanHelper(b, 8, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanMedium10(b *testing.B) {
+ ScanHelper(b, 10, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanMedium16(b *testing.B) {
+ ScanHelper(b, 16, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanLong2(b *testing.B) {
+ ScanHelper(b, 2, longBase, longExponent)
+}
+
+
+func BenchmarkScanLong8(b *testing.B) {
+ ScanHelper(b, 8, longBase, longExponent)
+}
+
+
+func BenchmarkScanLong10(b *testing.B) {
+ ScanHelper(b, 10, longBase, longExponent)
+}
+
+
+func BenchmarkScanLong16(b *testing.B) {
+ ScanHelper(b, 16, longBase, longExponent)
+}
+
+
+func ScanHelper(b *testing.B, base int, xv, yv Word) {
+ b.StopTimer()
+ var x, y, z nat
+ x = x.setWord(xv)
+ y = y.setWord(yv)
+ z = z.expNN(x, y, nil)
+
+ var s string
+ s = z.string(lowercaseDigits[0:base])
+ if t := toString(z, lowercaseDigits[0:base]); t != s {
+ panic(fmt.Sprintf("scanning: got %s; want %s", s, t))
+ }
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ x.scan(strings.NewReader(s), base)
+ }
+}
+
+
+func BenchmarkStringShort2(b *testing.B) {
+ StringHelper(b, 2, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringShort8(b *testing.B) {
+ StringHelper(b, 8, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringShort10(b *testing.B) {
+ StringHelper(b, 10, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringShort16(b *testing.B) {
+ StringHelper(b, 16, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringMedium2(b *testing.B) {
+ StringHelper(b, 2, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringMedium8(b *testing.B) {
+ StringHelper(b, 8, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringMedium10(b *testing.B) {
+ StringHelper(b, 10, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringMedium16(b *testing.B) {
+ StringHelper(b, 16, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringLong2(b *testing.B) {
+ StringHelper(b, 2, longBase, longExponent)
+}
+
+
+func BenchmarkStringLong8(b *testing.B) {
+ StringHelper(b, 8, longBase, longExponent)
+}
+
+
+func BenchmarkStringLong10(b *testing.B) {
+ StringHelper(b, 10, longBase, longExponent)
+}
+
+
+func BenchmarkStringLong16(b *testing.B) {
+ StringHelper(b, 16, longBase, longExponent)
+}
+
+
+func StringHelper(b *testing.B, base int, xv, yv Word) {
+ b.StopTimer()
+ var x, y, z nat
+ x = x.setWord(xv)
+ y = y.setWord(yv)
+ z = z.expNN(x, y, nil)
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ z.string(lowercaseDigits[0:base])
}
}
@@ -319,7 +691,6 @@ func TestTrailingZeroBits(t *testing.T) {
}
}
-
var expNNTests = []struct {
x, y, m string
out string
@@ -340,14 +711,14 @@ var expNNTests = []struct {
func TestExpNN(t *testing.T) {
for i, test := range expNNTests {
- x, _, _ := nat(nil).scan(test.x, 0)
- y, _, _ := nat(nil).scan(test.y, 0)
- out, _, _ := nat(nil).scan(test.out, 0)
+ x, _, _ := nat(nil).scan(strings.NewReader(test.x), 0)
+ y, _, _ := nat(nil).scan(strings.NewReader(test.y), 0)
+ out, _, _ := nat(nil).scan(strings.NewReader(test.out), 0)
var m nat
if len(test.m) > 0 {
- m, _, _ = nat(nil).scan(test.m, 0)
+ m, _, _ = nat(nil).scan(strings.NewReader(test.m), 0)
}
z := nat(nil).expNN(x, y, m)
diff --git a/src/pkg/big/rat.go b/src/pkg/big/rat.go
index e70673a1c..1fbf8c459 100644
--- a/src/pkg/big/rat.go
+++ b/src/pkg/big/rat.go
@@ -6,7 +6,12 @@
package big
-import "strings"
+import (
+ "encoding/binary"
+ "fmt"
+ "os"
+ "strings"
+)
// A Rat represents a quotient a/b of arbitrary precision. The zero value for
// a Rat, 0/0, is not a legal Rat.
@@ -84,7 +89,7 @@ func (z *Rat) Num() *Int {
}
-// Demom returns the denominator of z; it is always > 0.
+// Denom returns the denominator of z; it is always > 0.
// The result is a reference to z's denominator; it
// may change if a new value is assigned to z.
func (z *Rat) Denom() *Int {
@@ -209,6 +214,28 @@ func (z *Rat) Set(x *Rat) *Rat {
}
+func ratTok(ch int) bool {
+ return strings.IndexRune("+-/0123456789.eE", ch) >= 0
+}
+
+
+// Scan is a support routine for fmt.Scanner. It accepts the formats
+// 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent.
+func (z *Rat) Scan(s fmt.ScanState, ch int) os.Error {
+ tok, err := s.Token(true, ratTok)
+ if err != nil {
+ return err
+ }
+ if strings.IndexRune("efgEFGv", ch) < 0 {
+ return os.ErrorString("Rat.Scan: invalid verb")
+ }
+ if _, ok := z.SetString(string(tok)); !ok {
+ return os.ErrorString("Rat.Scan: invalid syntax")
+ }
+ return nil
+}
+
+
// SetString sets z to the value of s and returns z and a boolean indicating
// success. s can be given as a fraction "a/b" or as a floating-point number
// optionally followed by an exponent. If the operation failed, the value of z
@@ -225,8 +252,8 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
return z, false
}
s = s[sep+1:]
- var n int
- if z.b, _, n = z.b.scan(s, 10); n != len(s) {
+ var err os.Error
+ if z.b, _, err = z.b.scan(strings.NewReader(s), 10); err != nil {
return z, false
}
return z.norm(), true
@@ -270,7 +297,7 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
// String returns a string representation of z in the form "a/b" (even if b == 1).
func (z *Rat) String() string {
- return z.a.String() + "/" + z.b.string(10)
+ return z.a.String() + "/" + z.b.decimalString()
}
@@ -288,7 +315,11 @@ func (z *Rat) RatString() string {
// digits of precision after the decimal point and the last digit rounded.
func (z *Rat) FloatString(prec int) string {
if z.IsInt() {
- return z.a.String()
+ s := z.a.String()
+ if prec > 0 {
+ s += "." + strings.Repeat("0", prec)
+ }
+ return s
}
q, r := nat{}.div(nat{}, z.a.abs, z.b)
@@ -311,16 +342,58 @@ func (z *Rat) FloatString(prec int) string {
}
}
- s := q.string(10)
+ s := q.decimalString()
if z.a.neg {
s = "-" + s
}
if prec > 0 {
- rs := r.string(10)
+ rs := r.decimalString()
leadingZeros := prec - len(rs)
s += "." + strings.Repeat("0", leadingZeros) + rs
}
return s
}
+
+
+// Gob codec version. Permits backward-compatible changes to the encoding.
+const ratGobVersion byte = 1
+
+// GobEncode implements the gob.GobEncoder interface.
+func (z *Rat) GobEncode() ([]byte, os.Error) {
+ buf := make([]byte, 1+4+(len(z.a.abs)+len(z.b))*_S) // extra bytes for version and sign bit (1), and numerator length (4)
+ i := z.b.bytes(buf)
+ j := z.a.abs.bytes(buf[0:i])
+ n := i - j
+ if int(uint32(n)) != n {
+ // this should never happen
+ return nil, os.ErrorString("Rat.GobEncode: numerator too large")
+ }
+ binary.BigEndian.PutUint32(buf[j-4:j], uint32(n))
+ j -= 1 + 4
+ b := ratGobVersion << 1 // make space for sign bit
+ if z.a.neg {
+ b |= 1
+ }
+ buf[j] = b
+ return buf[j:], nil
+}
+
+
+// GobDecode implements the gob.GobDecoder interface.
+func (z *Rat) GobDecode(buf []byte) os.Error {
+ if len(buf) == 0 {
+ return os.ErrorString("Rat.GobDecode: no data")
+ }
+ b := buf[0]
+ if b>>1 != ratGobVersion {
+ return os.ErrorString(fmt.Sprintf("Rat.GobDecode: encoding version %d not supported", b>>1))
+ }
+ const j = 1 + 4
+ i := j + binary.BigEndian.Uint32(buf[j-4:j])
+ z.a.neg = b&1 != 0
+ z.a.abs = z.a.abs.setBytes(buf[j:i])
+ z.b = z.b.setBytes(buf[i:])
+ return nil
+}
diff --git a/src/pkg/big/rat_test.go b/src/pkg/big/rat_test.go
index 8f42949b0..e64505ea3 100644
--- a/src/pkg/big/rat_test.go
+++ b/src/pkg/big/rat_test.go
@@ -4,7 +4,12 @@
package big
-import "testing"
+import (
+ "bytes"
+ "fmt"
+ "gob"
+ "testing"
+)
var setStringTests = []struct {
@@ -53,18 +58,42 @@ func TestRatSetString(t *testing.T) {
}
+func TestRatScan(t *testing.T) {
+ var buf bytes.Buffer
+ for i, test := range setStringTests {
+ x := new(Rat)
+ buf.Reset()
+ buf.WriteString(test.in)
+
+ _, err := fmt.Fscanf(&buf, "%v", x)
+ if err == nil != test.ok {
+ if test.ok {
+ t.Errorf("#%d error: %s", i, err.String())
+ } else {
+ t.Errorf("#%d expected error", i)
+ }
+ continue
+ }
+ if err == nil && x.RatString() != test.out {
+ t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
+ }
+ }
+}
+
+
var floatStringTests = []struct {
in string
prec int
out string
}{
{"0", 0, "0"},
- {"0", 4, "0"},
+ {"0", 4, "0.0000"},
{"1", 0, "1"},
- {"1", 2, "1"},
+ {"1", 2, "1.00"},
{"-1", 0, "-1"},
{".25", 2, "0.25"},
{".25", 1, "0.3"},
+ {".25", 3, "0.250"},
{"-1/3", 3, "-0.333"},
{"-2/3", 4, "-0.6667"},
{"0.96", 1, "1.0"},
@@ -280,3 +309,36 @@ func TestRatSetFrac64Rat(t *testing.T) {
}
}
}
+
+
+func TestRatGobEncoding(t *testing.T) {
+ var medium bytes.Buffer
+ enc := gob.NewEncoder(&medium)
+ dec := gob.NewDecoder(&medium)
+ for i, test := range gobEncodingTests {
+ for j := 0; j < 4; j++ {
+ medium.Reset() // empty buffer for each test case (in case of failures)
+ stest := test
+ if j&1 != 0 {
+ // negative numbers
+ stest = "-" + test
+ }
+ if j%2 != 0 {
+ // fractions
+ stest = stest + "." + test
+ }
+ var tx Rat
+ tx.SetString(stest)
+ if err := enc.Encode(&tx); err != nil {
+ t.Errorf("#%d%c: encoding failed: %s", i, 'a'+j, err)
+ }
+ var rx Rat
+ if err := dec.Decode(&rx); err != nil {
+ t.Errorf("#%d%c: decoding failed: %s", i, 'a'+j, err)
+ }
+ if rx.Cmp(&tx) != 0 {
+ t.Errorf("#%d%c: transmission failed: got %s want %s", i, 'a'+j, &rx, &tx)
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-27 15:10:26 +0000