summaryrefslogtreecommitdiff
path: root/libgo/go/big
diff options
context:
space:
mode:
Diffstat (limited to 'libgo/go/big')
-rw-r--r--libgo/go/big/arith.go25
-rw-r--r--libgo/go/big/arith_decl.go4
-rw-r--r--libgo/go/big/arith_test.go33
-rw-r--r--libgo/go/big/calibrate_test.go4
-rw-r--r--libgo/go/big/hilbert_test.go13
-rw-r--r--libgo/go/big/int.go302
-rw-r--r--libgo/go/big/int_test.go402
-rw-r--r--libgo/go/big/nat.go388
-rw-r--r--libgo/go/big/nat_test.go403
-rw-r--r--libgo/go/big/rat.go107
-rw-r--r--libgo/go/big/rat_test.go74
11 files changed, 1351 insertions, 404 deletions
diff --git a/libgo/go/big/arith.go b/libgo/go/big/arith.go
index a4048d6d751..242bd1e8cc4 100644
--- a/libgo/go/big/arith.go
+++ b/libgo/go/big/arith.go
@@ -27,7 +27,6 @@ const (
_M2 = _B2 - 1 // half digit mask
)
-
// ----------------------------------------------------------------------------
// Elementary operations on words
//
@@ -43,7 +42,6 @@ func addWW_g(x, y, c Word) (z1, z0 Word) {
return
}
-
// z1<<_W + z0 = x-y-c, with c == 0 or 1
func subWW_g(x, y, c Word) (z1, z0 Word) {
yc := y + c
@@ -54,7 +52,6 @@ func subWW_g(x, y, c Word) (z1, z0 Word) {
return
}
-
// z1<<_W + z0 = x*y
func mulWW(x, y Word) (z1, z0 Word) { return mulWW_g(x, y) }
// Adapted from Warren, Hacker's Delight, p. 132.
@@ -73,7 +70,6 @@ func mulWW_g(x, y Word) (z1, z0 Word) {
return
}
-
// z1<<_W + z0 = x*y + c
func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
z1, zz0 := mulWW(x, y)
@@ -83,7 +79,6 @@ func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
return
}
-
// Length of x in bits.
func bitLen(x Word) (n int) {
for ; x >= 0x100; x >>= 8 {
@@ -95,7 +90,6 @@ func bitLen(x Word) (n int) {
return
}
-
// log2 computes the integer binary logarithm of x.
// The result is the integer n for which 2^n <= x < 2^(n+1).
// If x == 0, the result is -1.
@@ -103,13 +97,11 @@ func log2(x Word) int {
return bitLen(x) - 1
}
-
// Number of leading zeros in x.
func leadingZeros(x Word) uint {
return uint(_W - bitLen(x))
}
-
// q = (u1<<_W + u0 - r)/y
func divWW(x1, x0, y Word) (q, r Word) { return divWW_g(x1, x0, y) }
// Adapted from Warren, Hacker's Delight, p. 152.
@@ -155,7 +147,6 @@ again2:
return q1*_B2 + q0, (un21*_B2 + un0 - q0*v) >> s
}
-
func addVV(z, x, y []Word) (c Word) { return addVV_g(z, x, y) }
func addVV_g(z, x, y []Word) (c Word) {
for i := range z {
@@ -164,7 +155,6 @@ func addVV_g(z, x, y []Word) (c Word) {
return
}
-
func subVV(z, x, y []Word) (c Word) { return subVV_g(z, x, y) }
func subVV_g(z, x, y []Word) (c Word) {
for i := range z {
@@ -173,7 +163,6 @@ func subVV_g(z, x, y []Word) (c Word) {
return
}
-
func addVW(z, x []Word, y Word) (c Word) { return addVW_g(z, x, y) }
func addVW_g(z, x []Word, y Word) (c Word) {
c = y
@@ -183,7 +172,6 @@ func addVW_g(z, x []Word, y Word) (c Word) {
return
}
-
func subVW(z, x []Word, y Word) (c Word) { return subVW_g(z, x, y) }
func subVW_g(z, x []Word, y Word) (c Word) {
c = y
@@ -193,9 +181,8 @@ func subVW_g(z, x []Word, y Word) (c Word) {
return
}
-
-func shlVW(z, x []Word, s Word) (c Word) { return shlVW_g(z, x, s) }
-func shlVW_g(z, x []Word, s Word) (c Word) {
+func shlVU(z, x []Word, s uint) (c Word) { return shlVU_g(z, x, s) }
+func shlVU_g(z, x []Word, s uint) (c Word) {
if n := len(z); n > 0 {
ŝ := _W - s
w1 := x[n-1]
@@ -210,9 +197,8 @@ func shlVW_g(z, x []Word, s Word) (c Word) {
return
}
-
-func shrVW(z, x []Word, s Word) (c Word) { return shrVW_g(z, x, s) }
-func shrVW_g(z, x []Word, s Word) (c Word) {
+func shrVU(z, x []Word, s uint) (c Word) { return shrVU_g(z, x, s) }
+func shrVU_g(z, x []Word, s uint) (c Word) {
if n := len(z); n > 0 {
ŝ := _W - s
w1 := x[0]
@@ -227,7 +213,6 @@ func shrVW_g(z, x []Word, s Word) (c Word) {
return
}
-
func mulAddVWW(z, x []Word, y, r Word) (c Word) { return mulAddVWW_g(z, x, y, r) }
func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
c = r
@@ -237,7 +222,6 @@ func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
return
}
-
func addMulVVW(z, x []Word, y Word) (c Word) { return addMulVVW_g(z, x, y) }
func addMulVVW_g(z, x []Word, y Word) (c Word) {
for i := range z {
@@ -248,7 +232,6 @@ func addMulVVW_g(z, x []Word, y Word) (c Word) {
return
}
-
func divWVW(z []Word, xn Word, x []Word, y Word) (r Word) { return divWVW_g(z, xn, x, y) }
func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) {
r = xn
diff --git a/libgo/go/big/arith_decl.go b/libgo/go/big/arith_decl.go
index c456d5f67d3..95fcd8b94be 100644
--- a/libgo/go/big/arith_decl.go
+++ b/libgo/go/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/libgo/go/big/arith_test.go b/libgo/go/big/arith_test.go
index 934b302df03..b6c56c39ef4 100644
--- a/libgo/go/big/arith_test.go
+++ b/libgo/go/big/arith_test.go
@@ -6,7 +6,6 @@ package big
import "testing"
-
type funWW func(x, y, c Word) (z1, z0 Word)
type argWW struct {
x, y, c, z1, z0 Word
@@ -26,7 +25,6 @@ var sumWW = []argWW{
{_M, _M, 1, 1, _M},
}
-
func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
z1, z0 := f(a.x, a.y, a.c)
if z1 != a.z1 || z0 != a.z0 {
@@ -34,7 +32,6 @@ func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
}
}
-
func TestFunWW(t *testing.T) {
for _, a := range sumWW {
arg := a
@@ -51,7 +48,6 @@ func TestFunWW(t *testing.T) {
}
}
-
type funVV func(z, x, y []Word) (c Word)
type argVV struct {
z, x, y nat
@@ -70,7 +66,6 @@ var sumVV = []argVV{
{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
}
-
func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
z := make(nat, len(a.z))
c := f(z, a.x, a.y)
@@ -85,7 +80,6 @@ func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
}
}
-
func TestFunVV(t *testing.T) {
for _, a := range sumVV {
arg := a
@@ -106,7 +100,6 @@ func TestFunVV(t *testing.T) {
}
}
-
type funVW func(z, x []Word, y Word) (c Word)
type argVW struct {
z, x nat
@@ -169,7 +162,6 @@ var rshVW = []argVW{
{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
}
-
func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
z := make(nat, len(a.z))
c := f(z, a.x, a.y)
@@ -184,6 +176,11 @@ 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 {
@@ -196,20 +193,23 @@ 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)
}
}
-
type funVWW func(z, x []Word, y, r Word) (c Word)
type argVWW struct {
z, x nat
@@ -243,7 +243,6 @@ var prodVWW = []argVWW{
{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
}
-
func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
z := make(nat, len(a.z))
c := f(z, a.x, a.y, a.r)
@@ -258,7 +257,6 @@ func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
}
}
-
// TODO(gri) mulAddVWW and divWVW are symmetric operations but
// their signature is not symmetric. Try to unify.
@@ -285,7 +283,6 @@ func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
}
}
-
func TestFunVWW(t *testing.T) {
for _, a := range prodVWW {
arg := a
@@ -300,7 +297,6 @@ func TestFunVWW(t *testing.T) {
}
}
-
var mulWWTests = []struct {
x, y Word
q, r Word
@@ -309,7 +305,6 @@ var mulWWTests = []struct {
// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
}
-
func TestMulWW(t *testing.T) {
for i, test := range mulWWTests {
q, r := mulWW_g(test.x, test.y)
@@ -319,7 +314,6 @@ func TestMulWW(t *testing.T) {
}
}
-
var mulAddWWWTests = []struct {
x, y, c Word
q, r Word
@@ -331,7 +325,6 @@ var mulAddWWWTests = []struct {
{_M, _M, _M, _M, 0},
}
-
func TestMulAddWWW(t *testing.T) {
for i, test := range mulAddWWWTests {
q, r := mulAddWWW_g(test.x, test.y, test.c)
diff --git a/libgo/go/big/calibrate_test.go b/libgo/go/big/calibrate_test.go
index c6cd2e693b7..1cd93b1052b 100644
--- a/libgo/go/big/calibrate_test.go
+++ b/libgo/go/big/calibrate_test.go
@@ -19,10 +19,8 @@ import (
"time"
)
-
var calibrate = flag.Bool("calibrate", false, "run calibration test")
-
// measure returns the time to run f
func measure(f func()) int64 {
const N = 100
@@ -34,7 +32,6 @@ func measure(f func()) int64 {
return (stop - start) / N
}
-
func computeThresholds() {
fmt.Printf("Multiplication times for varying Karatsuba thresholds\n")
fmt.Printf("(run repeatedly for good results)\n")
@@ -84,7 +81,6 @@ func computeThresholds() {
}
}
-
func TestCalibrate(t *testing.T) {
if *calibrate {
computeThresholds()
diff --git a/libgo/go/big/hilbert_test.go b/libgo/go/big/hilbert_test.go
index 66a21214d22..1a84341b3c0 100644
--- a/libgo/go/big/hilbert_test.go
+++ b/libgo/go/big/hilbert_test.go
@@ -13,13 +13,11 @@ import (
"testing"
)
-
type matrix struct {
n, m int
a []*Rat
}
-
func (a *matrix) at(i, j int) *Rat {
if !(0 <= i && i < a.n && 0 <= j && j < a.m) {
panic("index out of range")
@@ -27,7 +25,6 @@ func (a *matrix) at(i, j int) *Rat {
return a.a[i*a.m+j]
}
-
func (a *matrix) set(i, j int, x *Rat) {
if !(0 <= i && i < a.n && 0 <= j && j < a.m) {
panic("index out of range")
@@ -35,7 +32,6 @@ func (a *matrix) set(i, j int, x *Rat) {
a.a[i*a.m+j] = x
}
-
func newMatrix(n, m int) *matrix {
if !(0 <= n && 0 <= m) {
panic("illegal matrix")
@@ -47,7 +43,6 @@ func newMatrix(n, m int) *matrix {
return a
}
-
func newUnit(n int) *matrix {
a := newMatrix(n, n)
for i := 0; i < n; i++ {
@@ -62,7 +57,6 @@ func newUnit(n int) *matrix {
return a
}
-
func newHilbert(n int) *matrix {
a := newMatrix(n, n)
for i := 0; i < n; i++ {
@@ -73,7 +67,6 @@ func newHilbert(n int) *matrix {
return a
}
-
func newInverseHilbert(n int) *matrix {
a := newMatrix(n, n)
for i := 0; i < n; i++ {
@@ -98,7 +91,6 @@ func newInverseHilbert(n int) *matrix {
return a
}
-
func (a *matrix) mul(b *matrix) *matrix {
if a.m != b.n {
panic("illegal matrix multiply")
@@ -116,7 +108,6 @@ func (a *matrix) mul(b *matrix) *matrix {
return c
}
-
func (a *matrix) eql(b *matrix) bool {
if a.n != b.n || a.m != b.m {
return false
@@ -131,7 +122,6 @@ func (a *matrix) eql(b *matrix) bool {
return true
}
-
func (a *matrix) String() string {
s := ""
for i := 0; i < a.n; i++ {
@@ -143,7 +133,6 @@ func (a *matrix) String() string {
return s
}
-
func doHilbert(t *testing.T, n int) {
a := newHilbert(n)
b := newInverseHilbert(n)
@@ -160,12 +149,10 @@ func doHilbert(t *testing.T, n int) {
}
}
-
func TestHilbert(t *testing.T) {
doHilbert(t, 10)
}
-
func BenchmarkHilbert(b *testing.B) {
for i := 0; i < b.N; i++ {
doHilbert(nil, 10)
diff --git a/libgo/go/big/int.go b/libgo/go/big/int.go
index f1ea7b1c2ec..701b69715db 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
diff --git a/libgo/go/big/int_test.go b/libgo/go/big/int_test.go
index 9c19dd5da6d..03446d6ae2d 100644
--- a/libgo/go/big/int_test.go
+++ b/libgo/go/big/int_test.go
@@ -13,7 +13,6 @@ import (
"testing/quick"
)
-
func isNormalized(x *Int) bool {
if len(x.abs) == 0 {
return !x.neg
@@ -22,13 +21,11 @@ func isNormalized(x *Int) bool {
return x.abs[len(x.abs)-1] != 0
}
-
type funZZ func(z, x, y *Int) *Int
type argZZ struct {
z, x, y *Int
}
-
var sumZZ = []argZZ{
{NewInt(0), NewInt(0), NewInt(0)},
{NewInt(1), NewInt(1), NewInt(0)},
@@ -38,7 +35,6 @@ var sumZZ = []argZZ{
{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
}
-
var prodZZ = []argZZ{
{NewInt(0), NewInt(0), NewInt(0)},
{NewInt(0), NewInt(1), NewInt(0)},
@@ -47,7 +43,6 @@ var prodZZ = []argZZ{
// TODO(gri) add larger products
}
-
func TestSignZ(t *testing.T) {
var zero Int
for _, a := range sumZZ {
@@ -59,7 +54,6 @@ func TestSignZ(t *testing.T) {
}
}
-
func TestSetZ(t *testing.T) {
for _, a := range sumZZ {
var z Int
@@ -73,7 +67,6 @@ func TestSetZ(t *testing.T) {
}
}
-
func TestAbsZ(t *testing.T) {
var zero Int
for _, a := range sumZZ {
@@ -90,7 +83,6 @@ func TestAbsZ(t *testing.T) {
}
}
-
func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
var z Int
f(&z, a.x, a.y)
@@ -102,7 +94,6 @@ func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
}
}
-
func TestSumZZ(t *testing.T) {
AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
@@ -121,7 +112,6 @@ func TestSumZZ(t *testing.T) {
}
}
-
func TestProdZZ(t *testing.T) {
MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
for _, a := range prodZZ {
@@ -133,7 +123,6 @@ func TestProdZZ(t *testing.T) {
}
}
-
// mulBytes returns x*y via grade school multiplication. Both inputs
// and the result are assumed to be in big-endian representation (to
// match the semantics of Int.Bytes and Int.SetBytes).
@@ -166,7 +155,6 @@ func mulBytes(x, y []byte) []byte {
return z[i:]
}
-
func checkMul(a, b []byte) bool {
var x, y, z1 Int
x.SetBytes(a)
@@ -179,14 +167,12 @@ func checkMul(a, b []byte) bool {
return z1.Cmp(&z2) == 0
}
-
func TestMul(t *testing.T) {
if err := quick.Check(checkMul, nil); err != nil {
t.Error(err)
}
}
-
var mulRangesZ = []struct {
a, b int64
prod string
@@ -212,7 +198,6 @@ var mulRangesZ = []struct {
},
}
-
func TestMulRangeZ(t *testing.T) {
var tmp Int
// test entirely positive ranges
@@ -231,7 +216,6 @@ func TestMulRangeZ(t *testing.T) {
}
}
-
var stringTests = []struct {
in string
out string
@@ -280,7 +264,6 @@ var stringTests = []struct {
{"1001010111", "1001010111", 2, 0x257, true},
}
-
func format(base int) string {
switch base {
case 2:
@@ -293,7 +276,6 @@ func format(base int) string {
return "%d"
}
-
func TestGetString(t *testing.T) {
z := new(Int)
for i, test := range stringTests {
@@ -316,7 +298,6 @@ func TestGetString(t *testing.T) {
}
}
-
func TestSetString(t *testing.T) {
tmp := new(Int)
for i, test := range stringTests {
@@ -347,6 +328,212 @@ 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)"},
+
+ {"1234", "%d", "1234"},
+ {"1234", "%3d", "1234"},
+ {"1234", "%4d", "1234"},
+ {"-1234", "%d", "-1234"},
+ {"1234", "% 5d", " 1234"},
+ {"1234", "%+5d", "+1234"},
+ {"1234", "%-5d", "1234 "},
+ {"1234", "%x", "4d2"},
+ {"1234", "%X", "4D2"},
+ {"-1234", "%3x", "-4d2"},
+ {"-1234", "%4x", "-4d2"},
+ {"-1234", "%5x", " -4d2"},
+ {"-1234", "%-5x", "-4d2 "},
+ {"1234", "%03d", "1234"},
+ {"1234", "%04d", "1234"},
+ {"1234", "%05d", "01234"},
+ {"1234", "%06d", "001234"},
+ {"-1234", "%06d", "-01234"},
+ {"1234", "%+06d", "+01234"},
+ {"1234", "% 06d", " 01234"},
+ {"1234", "%-6d", "1234 "},
+ {"1234", "%-06d", "1234 "},
+ {"-1234", "%-06d", "-1234 "},
+
+ {"1234", "%.3d", "1234"},
+ {"1234", "%.4d", "1234"},
+ {"1234", "%.5d", "01234"},
+ {"1234", "%.6d", "001234"},
+ {"-1234", "%.3d", "-1234"},
+ {"-1234", "%.4d", "-1234"},
+ {"-1234", "%.5d", "-01234"},
+ {"-1234", "%.6d", "-001234"},
+
+ {"1234", "%8.3d", " 1234"},
+ {"1234", "%8.4d", " 1234"},
+ {"1234", "%8.5d", " 01234"},
+ {"1234", "%8.6d", " 001234"},
+ {"-1234", "%8.3d", " -1234"},
+ {"-1234", "%8.4d", " -1234"},
+ {"-1234", "%8.5d", " -01234"},
+ {"-1234", "%8.6d", " -001234"},
+
+ {"1234", "%+8.3d", " +1234"},
+ {"1234", "%+8.4d", " +1234"},
+ {"1234", "%+8.5d", " +01234"},
+ {"1234", "%+8.6d", " +001234"},
+ {"-1234", "%+8.3d", " -1234"},
+ {"-1234", "%+8.4d", " -1234"},
+ {"-1234", "%+8.5d", " -01234"},
+ {"-1234", "%+8.6d", " -001234"},
+
+ {"1234", "% 8.3d", " 1234"},
+ {"1234", "% 8.4d", " 1234"},
+ {"1234", "% 8.5d", " 01234"},
+ {"1234", "% 8.6d", " 001234"},
+ {"-1234", "% 8.3d", " -1234"},
+ {"-1234", "% 8.4d", " -1234"},
+ {"-1234", "% 8.5d", " -01234"},
+ {"-1234", "% 8.6d", " -001234"},
+
+ {"1234", "%.3x", "4d2"},
+ {"1234", "%.4x", "04d2"},
+ {"1234", "%.5x", "004d2"},
+ {"1234", "%.6x", "0004d2"},
+ {"-1234", "%.3x", "-4d2"},
+ {"-1234", "%.4x", "-04d2"},
+ {"-1234", "%.5x", "-004d2"},
+ {"-1234", "%.6x", "-0004d2"},
+
+ {"1234", "%8.3x", " 4d2"},
+ {"1234", "%8.4x", " 04d2"},
+ {"1234", "%8.5x", " 004d2"},
+ {"1234", "%8.6x", " 0004d2"},
+ {"-1234", "%8.3x", " -4d2"},
+ {"-1234", "%8.4x", " -04d2"},
+ {"-1234", "%8.5x", " -004d2"},
+ {"-1234", "%8.6x", " -0004d2"},
+
+ {"1234", "%+8.3x", " +4d2"},
+ {"1234", "%+8.4x", " +04d2"},
+ {"1234", "%+8.5x", " +004d2"},
+ {"1234", "%+8.6x", " +0004d2"},
+ {"-1234", "%+8.3x", " -4d2"},
+ {"-1234", "%+8.4x", " -04d2"},
+ {"-1234", "%+8.5x", " -004d2"},
+ {"-1234", "%+8.6x", " -0004d2"},
+
+ {"1234", "% 8.3x", " 4d2"},
+ {"1234", "% 8.4x", " 04d2"},
+ {"1234", "% 8.5x", " 004d2"},
+ {"1234", "% 8.6x", " 0004d2"},
+ {"1234", "% 8.7x", " 00004d2"},
+ {"1234", "% 8.8x", " 000004d2"},
+ {"-1234", "% 8.3x", " -4d2"},
+ {"-1234", "% 8.4x", " -04d2"},
+ {"-1234", "% 8.5x", " -004d2"},
+ {"-1234", "% 8.6x", " -0004d2"},
+ {"-1234", "% 8.7x", "-00004d2"},
+ {"-1234", "% 8.8x", "-000004d2"},
+
+ {"1234", "%-8.3d", "1234 "},
+ {"1234", "%-8.4d", "1234 "},
+ {"1234", "%-8.5d", "01234 "},
+ {"1234", "%-8.6d", "001234 "},
+ {"1234", "%-8.7d", "0001234 "},
+ {"1234", "%-8.8d", "00001234"},
+ {"-1234", "%-8.3d", "-1234 "},
+ {"-1234", "%-8.4d", "-1234 "},
+ {"-1234", "%-8.5d", "-01234 "},
+ {"-1234", "%-8.6d", "-001234 "},
+ {"-1234", "%-8.7d", "-0001234"},
+ {"-1234", "%-8.8d", "-00001234"},
+
+ {"16777215", "%b", "111111111111111111111111"}, // 2**24 - 1
+
+ {"0", "%.d", ""},
+ {"0", "%.0d", ""},
+ {"0", "%3.d", ""},
+}
+
+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 %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, 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 {
@@ -362,7 +549,6 @@ var divisionSignsTests = []struct {
{8, 4, 2, 0, 2, 0},
}
-
func TestDivisionSigns(t *testing.T) {
for i, test := range divisionSignsTests {
x := NewInt(test.x)
@@ -420,7 +606,6 @@ func TestDivisionSigns(t *testing.T) {
}
}
-
func checkSetBytes(b []byte) bool {
hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
hex2 := hex.EncodeToString(b)
@@ -436,27 +621,23 @@ func checkSetBytes(b []byte) bool {
return hex1 == hex2
}
-
func TestSetBytes(t *testing.T) {
if err := quick.Check(checkSetBytes, nil); err != nil {
t.Error(err)
}
}
-
func checkBytes(b []byte) bool {
b2 := new(Int).SetBytes(b).Bytes()
return bytes.Compare(b, b2) == 0
}
-
func TestBytes(t *testing.T) {
if err := quick.Check(checkSetBytes, nil); err != nil {
t.Error(err)
}
}
-
func checkQuo(x, y []byte) bool {
u := new(Int).SetBytes(x)
v := new(Int).SetBytes(y)
@@ -479,7 +660,6 @@ func checkQuo(x, y []byte) bool {
return uprime.Cmp(u) == 0
}
-
var quoTests = []struct {
x, y string
q, r string
@@ -498,7 +678,6 @@ var quoTests = []struct {
},
}
-
func TestQuo(t *testing.T) {
if err := quick.Check(checkQuo, nil); err != nil {
t.Error(err)
@@ -519,7 +698,6 @@ func TestQuo(t *testing.T) {
}
}
-
func TestQuoStepD6(t *testing.T) {
// See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
// a code path which only triggers 1 in 10^{-19} cases.
@@ -539,7 +717,6 @@ func TestQuoStepD6(t *testing.T) {
}
}
-
var bitLenTests = []struct {
in string
out int
@@ -558,7 +735,6 @@ var bitLenTests = []struct {
{"-0x4000000000000000000000", 87},
}
-
func TestBitLen(t *testing.T) {
for i, test := range bitLenTests {
x, ok := new(Int).SetString(test.in, 0)
@@ -573,7 +749,6 @@ func TestBitLen(t *testing.T) {
}
}
-
var expTests = []struct {
x, y, m string
out string
@@ -598,7 +773,6 @@ var expTests = []struct {
},
}
-
func TestExp(t *testing.T) {
for i, test := range expTests {
x, ok1 := new(Int).SetString(test.x, 0)
@@ -629,7 +803,6 @@ func TestExp(t *testing.T) {
}
}
-
func checkGcd(aBytes, bBytes []byte) bool {
a := new(Int).SetBytes(aBytes)
b := new(Int).SetBytes(bBytes)
@@ -646,7 +819,6 @@ func checkGcd(aBytes, bBytes []byte) bool {
return x.Cmp(d) == 0
}
-
var gcdTests = []struct {
a, b int64
d, x, y int64
@@ -654,7 +826,6 @@ var gcdTests = []struct {
{120, 23, 1, -9, 47},
}
-
func TestGcd(t *testing.T) {
for i, test := range gcdTests {
a := NewInt(test.a)
@@ -680,7 +851,6 @@ func TestGcd(t *testing.T) {
quick.Check(checkGcd, nil)
}
-
var primes = []string{
"2",
"3",
@@ -706,7 +876,6 @@ var primes = []string{
"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
}
-
var composites = []string{
"21284175091214687912771199898307297748211672914763848041968395774954376176754",
"6084766654921918907427900243509372380954290099172559290432744450051395395951",
@@ -714,7 +883,6 @@ var composites = []string{
"82793403787388584738507275144194252681",
}
-
func TestProbablyPrime(t *testing.T) {
nreps := 20
if testing.Short() {
@@ -738,14 +906,12 @@ func TestProbablyPrime(t *testing.T) {
}
}
-
type intShiftTest struct {
in string
shift uint
out string
}
-
var rshTests = []intShiftTest{
{"0", 0, "0"},
{"-0", 0, "0"},
@@ -773,7 +939,6 @@ var rshTests = []intShiftTest{
{"340282366920938463463374607431768211456", 128, "1"},
}
-
func TestRsh(t *testing.T) {
for i, test := range rshTests {
in, _ := new(Int).SetString(test.in, 10)
@@ -789,7 +954,6 @@ func TestRsh(t *testing.T) {
}
}
-
func TestRshSelf(t *testing.T) {
for i, test := range rshTests {
z, _ := new(Int).SetString(test.in, 10)
@@ -805,7 +969,6 @@ func TestRshSelf(t *testing.T) {
}
}
-
var lshTests = []intShiftTest{
{"0", 0, "0"},
{"0", 1, "0"},
@@ -828,7 +991,6 @@ var lshTests = []intShiftTest{
{"1", 128, "340282366920938463463374607431768211456"},
}
-
func TestLsh(t *testing.T) {
for i, test := range lshTests {
in, _ := new(Int).SetString(test.in, 10)
@@ -844,7 +1006,6 @@ func TestLsh(t *testing.T) {
}
}
-
func TestLshSelf(t *testing.T) {
for i, test := range lshTests {
z, _ := new(Int).SetString(test.in, 10)
@@ -860,7 +1021,6 @@ func TestLshSelf(t *testing.T) {
}
}
-
func TestLshRsh(t *testing.T) {
for i, test := range rshTests {
in, _ := new(Int).SetString(test.in, 10)
@@ -888,7 +1048,6 @@ func TestLshRsh(t *testing.T) {
}
}
-
var int64Tests = []int64{
0,
1,
@@ -902,7 +1061,6 @@ var int64Tests = []int64{
-9223372036854775808,
}
-
func TestInt64(t *testing.T) {
for i, testVal := range int64Tests {
in := NewInt(testVal)
@@ -914,7 +1072,6 @@ func TestInt64(t *testing.T) {
}
}
-
var bitwiseTests = []struct {
x, y string
and, or, xor, andNot string
@@ -958,7 +1115,6 @@ var bitwiseTests = []struct {
},
}
-
type bitFun func(z, x, y *Int) *Int
func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
@@ -971,7 +1127,6 @@ func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
}
}
-
func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
self := new(Int)
self.Set(x)
@@ -984,6 +1139,142 @@ 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)
@@ -1003,7 +1294,6 @@ func TestBitwise(t *testing.T) {
}
}
-
var notTests = []struct {
in string
out string
@@ -1037,7 +1327,6 @@ func TestNot(t *testing.T) {
}
}
-
var modInverseTests = []struct {
element string
prime string
@@ -1062,7 +1351,7 @@ func TestModInverse(t *testing.T) {
}
}
-
+// used by TestIntGobEncoding and TestRatGobEncoding
var gobEncodingTests = []string{
"0",
"1",
@@ -1073,7 +1362,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 +1370,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/libgo/go/big/nat.go b/libgo/go/big/nat.go
index 4848d427b39..be3aff29d18 100644
--- a/libgo/go/big/nat.go
+++ b/libgo/go/big/nat.go
@@ -18,7 +18,11 @@ 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
//
@@ -40,14 +44,12 @@ var (
natTen = nat{10}
)
-
func (z nat) clear() {
for i := range z {
z[i] = 0
}
}
-
func (z nat) norm() nat {
i := len(z)
for i > 0 && z[i-1] == 0 {
@@ -56,7 +58,6 @@ func (z nat) norm() nat {
return z[0:i]
}
-
func (z nat) make(n int) nat {
if n <= cap(z) {
return z[0:n] // reuse z
@@ -67,7 +68,6 @@ func (z nat) make(n int) nat {
return make(nat, n, n+e)
}
-
func (z nat) setWord(x Word) nat {
if x == 0 {
return z.make(0)
@@ -77,7 +77,6 @@ func (z nat) setWord(x Word) nat {
return z
}
-
func (z nat) setUint64(x uint64) nat {
// single-digit values
if w := Word(x); uint64(w) == x {
@@ -100,14 +99,12 @@ func (z nat) setUint64(x uint64) nat {
return z
}
-
func (z nat) set(x nat) nat {
z = z.make(len(x))
copy(z, x)
return z
}
-
func (z nat) add(x, y nat) nat {
m := len(x)
n := len(y)
@@ -134,7 +131,6 @@ func (z nat) add(x, y nat) nat {
return z.norm()
}
-
func (z nat) sub(x, y nat) nat {
m := len(x)
n := len(y)
@@ -163,7 +159,6 @@ func (z nat) sub(x, y nat) nat {
return z.norm()
}
-
func (x nat) cmp(y nat) (r int) {
m := len(x)
n := len(y)
@@ -191,7 +186,6 @@ func (x nat) cmp(y nat) (r int) {
return
}
-
func (z nat) mulAddWW(x nat, y, r Word) nat {
m := len(x)
if m == 0 || y == 0 {
@@ -205,7 +199,6 @@ func (z nat) mulAddWW(x nat, y, r Word) nat {
return z.norm()
}
-
// basicMul multiplies x and y and leaves the result in z.
// The (non-normalized) result is placed in z[0 : len(x) + len(y)].
func basicMul(z, x, y nat) {
@@ -217,7 +210,6 @@ func basicMul(z, x, y nat) {
}
}
-
// Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks.
// Factored out for readability - do not use outside karatsuba.
func karatsubaAdd(z, x nat, n int) {
@@ -226,7 +218,6 @@ func karatsubaAdd(z, x nat, n int) {
}
}
-
// Like karatsubaAdd, but does subtract.
func karatsubaSub(z, x nat, n int) {
if c := subVV(z[0:n], z, x); c != 0 {
@@ -234,7 +225,6 @@ func karatsubaSub(z, x nat, n int) {
}
}
-
// Operands that are shorter than karatsubaThreshold are multiplied using
// "grade school" multiplication; for longer operands the Karatsuba algorithm
// is used.
@@ -339,13 +329,11 @@ func karatsuba(z, x, y nat) {
}
}
-
// alias returns true if x and y share the same base array.
func alias(x, y nat) bool {
return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]
}
-
// addAt implements z += x*(1<<(_W*i)); z must be long enough.
// (we don't use nat.add because we need z to stay the same
// slice, and we don't need to normalize z after each addition)
@@ -360,7 +348,6 @@ func addAt(z, x nat, i int) {
}
}
-
func max(x, y int) int {
if x > y {
return x
@@ -368,7 +355,6 @@ func max(x, y int) int {
return y
}
-
// karatsubaLen computes an approximation to the maximum k <= n such that
// k = p<<i for a number p <= karatsubaThreshold and an i >= 0. Thus, the
// result is the largest number that can be divided repeatedly by 2 before
@@ -382,7 +368,6 @@ func karatsubaLen(n int) int {
return n << i
}
-
func (z nat) mul(x, y nat) nat {
m := len(x)
n := len(y)
@@ -450,7 +435,6 @@ func (z nat) mul(x, y nat) nat {
return z.norm()
}
-
// mulRange computes the product of all the unsigned integers in the
// range [a, b] inclusively. If a > b (empty range), the result is 1.
func (z nat) mulRange(a, b uint64) nat {
@@ -469,7 +453,6 @@ func (z nat) mulRange(a, b uint64) nat {
return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
}
-
// q = (x-r)/y, with 0 <= r < y
func (z nat) divW(x nat, y Word) (q nat, r Word) {
m := len(x)
@@ -490,7 +473,6 @@ func (z nat) divW(x nat, y Word) (q nat, r Word) {
return
}
-
func (z nat) div(z2, u, v nat) (q, r nat) {
if len(v) == 0 {
panic("division by zero")
@@ -518,7 +500,6 @@ func (z nat) div(z2, u, v nat) (q, r nat) {
return
}
-
// q = (uIn-r)/v, with 0 <= r < y
// Uses z as storage for q, and u as storage for r if possible.
// See Knuth, Volume 2, section 4.3.1, Algorithm D.
@@ -545,9 +526,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,14 +572,12 @@ 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
}
-
// Length of x in bits. x must be normalized.
func (x nat) bitLen() int {
if i := len(x) - 1; i >= 0 {
@@ -602,103 +586,253 @@ func (x nat) bitLen() int {
return 0
}
+// MaxBase is the largest number base accepted for string conversions.
+const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1
-func hexValue(ch byte) int {
- var d byte
+
+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.NewError("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.NewError("syntax error scanning number")
+ }
+
+ return z.norm(), int(b), nil
}
+// Character sets for string conversion.
+const (
+ lowercaseDigits = "0123456789abcdefghijklmnopqrstuvwxyz"
+ uppercaseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+)
-// 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")
- }
+// 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])
+}
- if len(x) == 0 {
- return "0"
+// 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:])
}
-
const deBruijn32 = 0x077CB531
var deBruijn32Lookup = []byte{
@@ -721,7 +855,7 @@ var deBruijn64Lookup = []byte{
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
@@ -739,7 +873,6 @@ func trailingZeroBits(x Word) int {
return 0
}
-
// z = x << s
func (z nat) shl(x nat, s uint) nat {
m := len(x)
@@ -750,13 +883,12 @@ 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()
}
-
// z = x >> s
func (z nat) shr(x nat, s uint) nat {
m := len(x)
@@ -767,11 +899,45 @@ 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)
@@ -789,7 +955,6 @@ func (z nat) and(x, y nat) nat {
return z.norm()
}
-
func (z nat) andNot(x, y nat) nat {
m := len(x)
n := len(y)
@@ -807,7 +972,6 @@ func (z nat) andNot(x, y nat) nat {
return z.norm()
}
-
func (z nat) or(x, y nat) nat {
m := len(x)
n := len(y)
@@ -827,7 +991,6 @@ func (z nat) or(x, y nat) nat {
return z.norm()
}
-
func (z nat) xor(x, y nat) nat {
m := len(x)
n := len(y)
@@ -847,10 +1010,10 @@ func (z nat) xor(x, y nat) nat {
return z.norm()
}
-
// 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.
func (x nat) modW(d Word) (r Word) {
@@ -860,30 +1023,29 @@ func (x nat) modW(d Word) (r Word) {
return divWVW(q, 0, x, d)
}
-
-// 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
}
-
// random creates a random integer in [0..limit), using the space in z if
// possible. n is the bit length of limit.
func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
@@ -914,7 +1076,6 @@ func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
return z.norm()
}
-
// If m != nil, expNN calculates x**y mod m. Otherwise it calculates x**y. It
// reuses the storage of z if possible.
func (z nat) expNN(x, y, m nat) nat {
@@ -983,7 +1144,6 @@ func (z nat) expNN(x, y, m nat) nat {
return z
}
-
// probablyPrime performs reps Miller-Rabin tests to check whether n is prime.
// If it returns true, n is prime with probability 1 - 1/4^reps.
// If it returns false, n is not prime.
@@ -1050,7 +1210,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 {
@@ -1066,7 +1226,6 @@ NextRandom:
return true
}
-
// bytes writes the value of z into buf using big-endian encoding.
// len(buf) must be >= len(z)*_S. The value of z is encoded in the
// slice buf[i:]. The number i of unused bytes at the beginning of
@@ -1088,7 +1247,6 @@ func (z nat) bytes(buf []byte) (i int) {
return
}
-
// setBytes interprets buf as the bytes of a big-endian unsigned
// integer, sets z to that value, and returns z.
func (z nat) setBytes(buf []byte) nat {
diff --git a/libgo/go/big/nat_test.go b/libgo/go/big/nat_test.go
index 0bcb945548a..71d0860878c 100644
--- a/libgo/go/big/nat_test.go
+++ b/libgo/go/big/nat_test.go
@@ -4,7 +4,12 @@
package big
-import "testing"
+import (
+ "fmt"
+ "os"
+ "strings"
+ "testing"
+)
var cmpTests = []struct {
x, y nat
@@ -26,7 +31,6 @@ var cmpTests = []struct {
{nat{34986, 41, 105, 1957}, nat{56, 7458, 104, 1957}, 1},
}
-
func TestCmp(t *testing.T) {
for i, a := range cmpTests {
r := a.x.cmp(a.y)
@@ -36,13 +40,11 @@ func TestCmp(t *testing.T) {
}
}
-
type funNN func(z, x, y nat) nat
type argNN struct {
z, x, y nat
}
-
var sumNN = []argNN{
{},
{nat{1}, nil, nat{1}},
@@ -52,7 +54,6 @@ var sumNN = []argNN{
{nat{0, 0, 0, 1}, nat{0, 0, _M}, nat{0, 0, 1}},
}
-
var prodNN = []argNN{
{},
{nil, nil, nil},
@@ -64,7 +65,6 @@ var prodNN = []argNN{
{nat{4, 11, 20, 30, 20, 11, 4}, nat{1, 2, 3, 4}, nat{4, 3, 2, 1}},
}
-
func TestSet(t *testing.T) {
for _, a := range sumNN {
z := nat(nil).set(a.z)
@@ -74,7 +74,6 @@ func TestSet(t *testing.T) {
}
}
-
func testFunNN(t *testing.T, msg string, f funNN, a argNN) {
z := f(nil, a.x, a.y)
if z.cmp(a.z) != 0 {
@@ -82,7 +81,6 @@ func testFunNN(t *testing.T, msg string, f funNN, a argNN) {
}
}
-
func TestFunNN(t *testing.T) {
for _, a := range sumNN {
arg := a
@@ -107,7 +105,6 @@ func TestFunNN(t *testing.T) {
}
}
-
var mulRangesN = []struct {
a, b uint64
prod string
@@ -130,17 +127,15 @@ 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)
}
}
}
-
var mulArg, mulTmp nat
func init() {
@@ -151,7 +146,6 @@ func init() {
}
}
-
func benchmarkMulLoad() {
for j := 1; j <= 10; j++ {
x := mulArg[0 : j*100]
@@ -159,46 +153,376 @@ func benchmarkMulLoad() {
}
}
-
func BenchmarkMul(b *testing.B) {
for i := 0; i < b.N; i++ {
benchmarkMulLoad()
}
}
+func toString(x nat, charset string) string {
+ base := len(charset)
-var tab = []struct {
- x nat
- b int
- s string
-}{
- {nil, 10, "0"},
- {nat{1}, 10, "1"},
- {nat{10}, 10, "10"},
- {nat{1234567890}, 10, "1234567890"},
+ // 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, "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)
+ }
+ next, _, err := r.ReadRune()
+ if err == os.EOF {
+ next = 0
+ err = nil
}
- if n != len(a.s) {
- t.Errorf("scan%+v\n\tgot n = %d; want %d", a, n, len(a.s))
+ 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])
+ }
+}
func TestLeadingZeros(t *testing.T) {
var x Word = _B >> 1
@@ -210,14 +534,12 @@ func TestLeadingZeros(t *testing.T) {
}
}
-
type shiftTest struct {
in nat
shift uint
out nat
}
-
var leftShiftTests = []shiftTest{
{nil, 0, nil},
{nil, 1, nil},
@@ -227,7 +549,6 @@ var leftShiftTests = []shiftTest{
{nat{1 << (_W - 1), 0}, 1, nat{0, 1}},
}
-
func TestShiftLeft(t *testing.T) {
for i, test := range leftShiftTests {
var z nat
@@ -241,7 +562,6 @@ func TestShiftLeft(t *testing.T) {
}
}
-
var rightShiftTests = []shiftTest{
{nil, 0, nil},
{nil, 1, nil},
@@ -252,7 +572,6 @@ var rightShiftTests = []shiftTest{
{nat{2, 1, 1}, 1, nat{1<<(_W-1) + 1, 1 << (_W - 1)}},
}
-
func TestShiftRight(t *testing.T) {
for i, test := range rightShiftTests {
var z nat
@@ -266,24 +585,20 @@ func TestShiftRight(t *testing.T) {
}
}
-
type modWTest struct {
in string
dividend string
out string
}
-
var modWTests32 = []modWTest{
{"23492635982634928349238759823742", "252341", "220170"},
}
-
var modWTests64 = []modWTest{
{"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
}
-
func runModWTests(t *testing.T, tests []modWTest) {
for i, test := range tests {
in, _ := new(Int).SetString(test.in, 10)
@@ -297,7 +612,6 @@ func runModWTests(t *testing.T, tests []modWTest) {
}
}
-
func TestModW(t *testing.T) {
if _W >= 32 {
runModWTests(t, modWTests32)
@@ -307,7 +621,6 @@ func TestModW(t *testing.T) {
}
}
-
func TestTrailingZeroBits(t *testing.T) {
var x Word
x--
@@ -319,7 +632,6 @@ func TestTrailingZeroBits(t *testing.T) {
}
}
-
var expNNTests = []struct {
x, y, m string
out string
@@ -337,17 +649,16 @@ 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/libgo/go/big/rat.go b/libgo/go/big/rat.go
index e70673a1cba..327b9bd9ca7 100644
--- a/libgo/go/big/rat.go
+++ b/libgo/go/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.
@@ -15,13 +20,11 @@ type Rat struct {
b nat
}
-
// NewRat creates a new Rat with numerator a and denominator b.
func NewRat(a, b int64) *Rat {
return new(Rat).SetFrac64(a, b)
}
-
// SetFrac sets z to a/b and returns z.
func (z *Rat) SetFrac(a, b *Int) *Rat {
z.a.Set(a)
@@ -30,7 +33,6 @@ func (z *Rat) SetFrac(a, b *Int) *Rat {
return z.norm()
}
-
// SetFrac64 sets z to a/b and returns z.
func (z *Rat) SetFrac64(a, b int64) *Rat {
z.a.SetInt64(a)
@@ -42,7 +44,6 @@ func (z *Rat) SetFrac64(a, b int64) *Rat {
return z.norm()
}
-
// SetInt sets z to x (by making a copy of x) and returns z.
func (z *Rat) SetInt(x *Int) *Rat {
z.a.Set(x)
@@ -50,7 +51,6 @@ func (z *Rat) SetInt(x *Int) *Rat {
return z
}
-
// SetInt64 sets z to x and returns z.
func (z *Rat) SetInt64(x int64) *Rat {
z.a.SetInt64(x)
@@ -58,7 +58,6 @@ func (z *Rat) SetInt64(x int64) *Rat {
return z
}
-
// Sign returns:
//
// -1 if x < 0
@@ -69,13 +68,11 @@ func (x *Rat) Sign() int {
return x.a.Sign()
}
-
// IsInt returns true if the denominator of x is 1.
func (x *Rat) IsInt() bool {
return len(x.b) == 1 && x.b[0] == 1
}
-
// Num returns the numerator of z; it may be <= 0.
// The result is a reference to z's numerator; it
// may change if a new value is assigned to z.
@@ -83,15 +80,13 @@ func (z *Rat) Num() *Int {
return &z.a
}
-
-// 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 {
return &Int{false, z.b}
}
-
func gcd(x, y nat) nat {
// Euclidean algorithm.
var a, b nat
@@ -106,7 +101,6 @@ func gcd(x, y nat) nat {
return a
}
-
func (z *Rat) norm() *Rat {
f := gcd(z.a.abs, z.b)
if len(z.a.abs) == 0 {
@@ -122,7 +116,6 @@ func (z *Rat) norm() *Rat {
return z
}
-
func mulNat(x *Int, y nat) *Int {
var z Int
z.abs = z.abs.mul(x.abs, y)
@@ -130,7 +123,6 @@ func mulNat(x *Int, y nat) *Int {
return &z
}
-
// Cmp compares x and y and returns:
//
// -1 if x < y
@@ -141,7 +133,6 @@ func (x *Rat) Cmp(y *Rat) (r int) {
return mulNat(&x.a, y.b).Cmp(mulNat(&y.a, x.b))
}
-
// Abs sets z to |x| (the absolute value of x) and returns z.
func (z *Rat) Abs(x *Rat) *Rat {
z.a.Abs(&x.a)
@@ -149,7 +140,6 @@ func (z *Rat) Abs(x *Rat) *Rat {
return z
}
-
// Add sets z to the sum x+y and returns z.
func (z *Rat) Add(x, y *Rat) *Rat {
a1 := mulNat(&x.a, y.b)
@@ -159,7 +149,6 @@ func (z *Rat) Add(x, y *Rat) *Rat {
return z.norm()
}
-
// Sub sets z to the difference x-y and returns z.
func (z *Rat) Sub(x, y *Rat) *Rat {
a1 := mulNat(&x.a, y.b)
@@ -169,7 +158,6 @@ func (z *Rat) Sub(x, y *Rat) *Rat {
return z.norm()
}
-
// Mul sets z to the product x*y and returns z.
func (z *Rat) Mul(x, y *Rat) *Rat {
z.a.Mul(&x.a, &y.a)
@@ -177,7 +165,6 @@ func (z *Rat) Mul(x, y *Rat) *Rat {
return z.norm()
}
-
// Quo sets z to the quotient x/y and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
func (z *Rat) Quo(x, y *Rat) *Rat {
@@ -192,7 +179,6 @@ func (z *Rat) Quo(x, y *Rat) *Rat {
return z.norm()
}
-
// Neg sets z to -x (by making a copy of x if necessary) and returns z.
func (z *Rat) Neg(x *Rat) *Rat {
z.a.Neg(&x.a)
@@ -200,7 +186,6 @@ func (z *Rat) Neg(x *Rat) *Rat {
return z
}
-
// Set sets z to x (by making a copy of x if necessary) and returns z.
func (z *Rat) Set(x *Rat) *Rat {
z.a.Set(&x.a)
@@ -208,6 +193,25 @@ func (z *Rat) Set(x *Rat) *Rat {
return z
}
+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.NewError("Rat.Scan: invalid verb")
+ }
+ if _, ok := z.SetString(string(tok)); !ok {
+ return os.NewError("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
@@ -225,8 +229,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
@@ -267,13 +271,11 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
return z, true
}
-
// 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()
}
-
// RatString returns a string representation of z in the form "a/b" if b != 1,
// and in the form "a" if b == 1.
func (z *Rat) RatString() string {
@@ -283,12 +285,15 @@ func (z *Rat) RatString() string {
return z.String()
}
-
// FloatString returns a string representation of z in decimal form with prec
// 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 +316,56 @@ 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.NewError("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.NewError("Rat.GobDecode: no data")
+ }
+ b := buf[0]
+ if b>>1 != ratGobVersion {
+ return os.NewError(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/libgo/go/big/rat_test.go b/libgo/go/big/rat_test.go
index 8f42949b087..dbc5bb6cca1 100644
--- a/libgo/go/big/rat_test.go
+++ b/libgo/go/big/rat_test.go
@@ -4,8 +4,12 @@
package big
-import "testing"
-
+import (
+ "bytes"
+ "fmt"
+ "gob"
+ "testing"
+)
var setStringTests = []struct {
in, out string
@@ -52,6 +56,27 @@ 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
@@ -59,12 +84,13 @@ var floatStringTests = []struct {
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"},
@@ -84,7 +110,6 @@ func TestFloatString(t *testing.T) {
}
}
-
func TestRatSign(t *testing.T) {
zero := NewRat(0, 1)
for _, a := range setStringTests {
@@ -98,7 +123,6 @@ func TestRatSign(t *testing.T) {
}
}
-
var ratCmpTests = []struct {
rat1, rat2 string
out int
@@ -126,7 +150,6 @@ func TestRatCmp(t *testing.T) {
}
}
-
func TestIsInt(t *testing.T) {
one := NewInt(1)
for _, a := range setStringTests {
@@ -140,7 +163,6 @@ func TestIsInt(t *testing.T) {
}
}
-
func TestRatAbs(t *testing.T) {
zero := NewRat(0, 1)
for _, a := range setStringTests {
@@ -158,7 +180,6 @@ func TestRatAbs(t *testing.T) {
}
}
-
type ratBinFun func(z, x, y *Rat) *Rat
type ratBinArg struct {
x, y, z string
@@ -175,7 +196,6 @@ func testRatBin(t *testing.T, i int, name string, f ratBinFun, a ratBinArg) {
}
}
-
var ratBinTests = []struct {
x, y string
sum, prod string
@@ -232,7 +252,6 @@ func TestRatBin(t *testing.T) {
}
}
-
func TestIssue820(t *testing.T) {
x := NewRat(3, 1)
y := NewRat(2, 1)
@@ -258,7 +277,6 @@ func TestIssue820(t *testing.T) {
}
}
-
var setFrac64Tests = []struct {
a, b int64
out string
@@ -280,3 +298,35 @@ 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)
+ }
+ }
+ }
+}
View Lorry Controller Status