big: Add Lsh and Value; convert pidigits to use big
This yields a pretty significant performance boost to pidigits and there are still some improvements to be made. Here are my numbers:
amd64 w/ bignum:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.10u 0.00s 2.10r
gc pidigits 22.92u 0.02s 22.97r
gc_B pidigits 22.62u 0.00s 22.65r
amd64 w/ big:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.09u 0.02s 2.11r
gc pidigits 12.68u 0.04s 12.72r
gc_B pidigits 12.71u 0.03s 12.75r
386 w/ bignum:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.09u 0.00s 2.09r
gc pidigits 44.30u 0.01s 44.35r
gc_B pidigits 44.29u 0.03s 44.35r
386 w/ big:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.10u 0.00s 2.10r
gc pidigits 22.70u 0.06s 22.79r
gc_B pidigits 22.80u 0.09s 22.91r
R=rsc, gri
CC=golang-dev
https://golang.org/cl/881050
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go
index 8f776b5..ca94c5a 100644
--- a/src/pkg/big/int.go
+++ b/src/pkg/big/int.go
@@ -100,21 +100,26 @@
}
-// Div calculates q = (x-r)/y where 0 <= r < y. The receiver is set to q.
-func (z *Int) Div(x, y *Int) (q, r *Int) {
- q = z
- r = new(Int)
- div(q, r, x, y)
- return
+// Div calculates q = (x-r)/y and sets z = q.
+func (z *Int) Div(x, y *Int) *Int {
+ r := new(Int)
+ div(z, r, x, y)
+ return z
}
-// Mod calculates q = (x-r)/y and returns r.
-func (z *Int) Mod(x, y *Int) (r *Int) {
+// Mod calculates q = (x-r)/y and sets z = r.
+func (z *Int) Mod(x, y *Int) *Int {
q := new(Int)
- r = z
- div(q, r, x, y)
- return
+ div(q, z, x, y)
+ return z
+}
+
+
+// DivMod calculates q = (x-r)/y and sets z = q. (It returns z, r.)
+func (z *Int) DivMod(x, y, r *Int) (*Int, *Int) {
+ div(z, r, x, y)
+ return z, r
}
@@ -169,6 +174,23 @@
}
+// Int64 returns the int64 representation of z.
+// If z cannot be represented in an int64, the result is undefined.
+func (z *Int) Int64() int64 {
+ if len(z.abs) == 0 {
+ return 0
+ }
+ v := int64(z.abs[0])
+ if _W == 32 && len(z.abs) > 1 {
+ v |= int64(z.abs[1]) << 32
+ }
+ if z.neg {
+ v = -v
+ }
+ return v
+}
+
+
// SetString sets z to the value of s, interpreted in the given base.
// If base is 0 then SetString attempts to detect the base by at the prefix of
// s. '0x' implies base 16, '0' implies base 8. Otherwise base 10 is assumed.
@@ -324,7 +346,8 @@
temp := new(Int)
for len(B.abs) > 0 {
- q, r := q.Div(A, B)
+ r := new(Int)
+ q, r = q.DivMod(A, B, r)
A, B = B, r
@@ -359,12 +382,28 @@
func ProbablyPrime(z *Int, n int) bool { return !z.neg && probablyPrime(z.abs, n) }
-// Rsh sets z = x >> s and returns z.
-func (z *Int) Rsh(x *Int, n int) *Int {
- removedWords := n / _W
- z.abs = makeN(z.abs, len(x.abs)-removedWords, false)
+// Lsh sets z = x << n and returns z.
+func (z *Int) Lsh(x *Int, n uint) *Int {
+ addedWords := int(n) / _W
+ // Don't assign z.abs yet, in case z == x
+ znew := makeN(z.abs, len(x.abs)+addedWords+1, false)
z.neg = x.neg
- shiftRight(z.abs, x.abs[removedWords:], n%_W)
- z.abs = normN(z.abs)
+ shiftLeft(znew[addedWords:], x.abs, n%_W)
+ for i := range znew[0:addedWords] {
+ znew[i] = 0
+ }
+ z.abs = normN(znew)
+ return z
+}
+
+
+// Rsh sets z = x >> n and returns z.
+func (z *Int) Rsh(x *Int, n uint) *Int {
+ removedWords := int(n) / _W
+ // Don't assign z.abs yet, in case z == x
+ znew := makeN(z.abs, len(x.abs)-removedWords, false)
+ z.neg = x.neg
+ shiftRight(znew, x.abs[removedWords:], n%_W)
+ z.abs = normN(znew)
return z
}
diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go
index 70dbe59..1e9c0e0 100644
--- a/src/pkg/big/int_test.go
+++ b/src/pkg/big/int_test.go
@@ -192,7 +192,8 @@
for i, test := range divSignsTests {
x := new(Int).New(test.x)
y := new(Int).New(test.y)
- q, r := new(Int).Div(x, y)
+ r := new(Int)
+ q, r := new(Int).DivMod(x, y, r)
expectedQ := new(Int).New(test.q)
expectedR := new(Int).New(test.r)
@@ -249,7 +250,8 @@
return true
}
- q, r := new(Int).Div(u, v)
+ r := new(Int)
+ q, r := new(Int).DivMod(u, v, r)
if r.Cmp(v) >= 0 {
return false
@@ -297,7 +299,8 @@
expectedQ, _ := new(Int).SetString(test.q, 10)
expectedR, _ := new(Int).SetString(test.r, 10)
- q, r := new(Int).Div(x, y)
+ r := new(Int)
+ q, r := new(Int).DivMod(x, y, r)
if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
@@ -313,7 +316,8 @@
u := &Int{false, []Word{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
v := &Int{false, []Word{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
- q, r := new(Int).Div(u, v)
+ r := new(Int)
+ q, r := new(Int).DivMod(u, v, r)
const expectedQ64 = "18446744073709551613"
const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
const expectedQ32 = "4294967293"
@@ -519,32 +523,32 @@
}
-type rshTest struct {
+type intShiftTest struct {
in string
- shift int
+ shift uint
out string
}
-var rshTests = []rshTest{
- rshTest{"0", 0, "0"},
- rshTest{"0", 1, "0"},
- rshTest{"0", 2, "0"},
- rshTest{"1", 0, "1"},
- rshTest{"1", 1, "0"},
- rshTest{"1", 2, "0"},
- rshTest{"2", 0, "2"},
- rshTest{"2", 1, "1"},
- rshTest{"2", 2, "0"},
- rshTest{"4294967296", 0, "4294967296"},
- rshTest{"4294967296", 1, "2147483648"},
- rshTest{"4294967296", 2, "1073741824"},
- rshTest{"18446744073709551616", 0, "18446744073709551616"},
- rshTest{"18446744073709551616", 1, "9223372036854775808"},
- rshTest{"18446744073709551616", 2, "4611686018427387904"},
- rshTest{"18446744073709551616", 64, "1"},
- rshTest{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
- rshTest{"340282366920938463463374607431768211456", 128, "1"},
+var rshTests = []intShiftTest{
+ intShiftTest{"0", 0, "0"},
+ intShiftTest{"0", 1, "0"},
+ intShiftTest{"0", 2, "0"},
+ intShiftTest{"1", 0, "1"},
+ intShiftTest{"1", 1, "0"},
+ intShiftTest{"1", 2, "0"},
+ intShiftTest{"2", 0, "2"},
+ intShiftTest{"2", 1, "1"},
+ intShiftTest{"2", 2, "0"},
+ intShiftTest{"4294967296", 0, "4294967296"},
+ intShiftTest{"4294967296", 1, "2147483648"},
+ intShiftTest{"4294967296", 2, "1073741824"},
+ intShiftTest{"18446744073709551616", 0, "18446744073709551616"},
+ intShiftTest{"18446744073709551616", 1, "9223372036854775808"},
+ intShiftTest{"18446744073709551616", 2, "4611686018427387904"},
+ intShiftTest{"18446744073709551616", 64, "1"},
+ intShiftTest{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
+ intShiftTest{"340282366920938463463374607431768211456", 128, "1"},
}
@@ -559,3 +563,112 @@
}
}
}
+
+
+func TestRshSelf(t *testing.T) {
+ for i, test := range rshTests {
+ z, _ := new(Int).SetString(test.in, 10)
+ expected, _ := new(Int).SetString(test.out, 10)
+ z.Rsh(z, test.shift)
+
+ if z.Cmp(expected) != 0 {
+ t.Errorf("#%d got %s want %s", i, z, expected)
+ }
+ }
+}
+
+
+var lshTests = []intShiftTest{
+ intShiftTest{"0", 0, "0"},
+ intShiftTest{"0", 1, "0"},
+ intShiftTest{"0", 2, "0"},
+ intShiftTest{"1", 0, "1"},
+ intShiftTest{"1", 1, "2"},
+ intShiftTest{"1", 2, "4"},
+ intShiftTest{"2", 0, "2"},
+ intShiftTest{"2", 1, "4"},
+ intShiftTest{"2", 2, "8"},
+ intShiftTest{"-87", 1, "-174"},
+ intShiftTest{"4294967296", 0, "4294967296"},
+ intShiftTest{"4294967296", 1, "8589934592"},
+ intShiftTest{"4294967296", 2, "17179869184"},
+ intShiftTest{"18446744073709551616", 0, "18446744073709551616"},
+ intShiftTest{"9223372036854775808", 1, "18446744073709551616"},
+ intShiftTest{"4611686018427387904", 2, "18446744073709551616"},
+ intShiftTest{"1", 64, "18446744073709551616"},
+ intShiftTest{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
+ intShiftTest{"1", 128, "340282366920938463463374607431768211456"},
+}
+
+
+func TestLsh(t *testing.T) {
+ for i, test := range lshTests {
+ in, _ := new(Int).SetString(test.in, 10)
+ expected, _ := new(Int).SetString(test.out, 10)
+ out := new(Int).Lsh(in, test.shift)
+
+ if out.Cmp(expected) != 0 {
+ t.Errorf("#%d got %s want %s", i, out, expected)
+ }
+ }
+}
+
+
+func TestLshSelf(t *testing.T) {
+ for i, test := range lshTests {
+ z, _ := new(Int).SetString(test.in, 10)
+ expected, _ := new(Int).SetString(test.out, 10)
+ z.Lsh(z, test.shift)
+
+ if z.Cmp(expected) != 0 {
+ t.Errorf("#%d got %s want %s", i, z, expected)
+ }
+ }
+}
+
+
+func TestLshRsh(t *testing.T) {
+ for i, test := range rshTests {
+ in, _ := new(Int).SetString(test.in, 10)
+ out := new(Int).Lsh(in, test.shift)
+ out = out.Rsh(out, test.shift)
+
+ if in.Cmp(out) != 0 {
+ t.Errorf("#%d got %s want %s", i, out, in)
+ }
+ }
+ for i, test := range lshTests {
+ in, _ := new(Int).SetString(test.in, 10)
+ out := new(Int).Lsh(in, test.shift)
+ out.Rsh(out, test.shift)
+
+ if in.Cmp(out) != 0 {
+ t.Errorf("#%d got %s want %s", i, out, in)
+ }
+ }
+}
+
+
+var int64Tests = []int64{
+ 0,
+ 1,
+ -1,
+ 4294967295,
+ -4294967295,
+ 4294967296,
+ -4294967296,
+ 9223372036854775807,
+ -9223372036854775807,
+ -9223372036854775808,
+}
+
+func TestInt64(t *testing.T) {
+ for i, testVal := range int64Tests {
+ in := NewInt(testVal)
+ out := in.Int64()
+
+ if out != testVal {
+ t.Errorf("#%d got %d want %d", i, out, testVal)
+ }
+ }
+}
diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index 0f4d4c3..f8d4a2d 100644
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -302,7 +302,7 @@
q = makeN(z, m+1, false)
// D1.
- shift := leadingZeroBits(v[n-1])
+ shift := uint(leadingZeroBits(v[n-1]))
shiftLeft(v, v, shift)
shiftLeft(u, uIn, shift)
u[len(uIn)] = uIn[len(uIn)-1] >> (_W - uint(shift))
@@ -530,31 +530,34 @@
}
-func shiftLeft(dst, src []Word, n int) {
+// To avoid losing the top n bits, dst should be sized so that
+// len(dst) == len(src) + 1.
+func shiftLeft(dst, src []Word, n uint) {
if len(src) == 0 {
return
}
- ñ := _W - uint(n)
- for i := len(src) - 1; i >= 1; i-- {
- dst[i] = src[i] << uint(n)
- dst[i] |= src[i-1] >> ñ
+ ñ := _W - n
+ if len(dst) > len(src) {
+ dst[len(src)] |= src[len(src)-1] >> ñ
}
- dst[0] = src[0] << uint(n)
+ for i := len(src) - 1; i >= 1; i-- {
+ dst[i] = src[i]<<n | src[i-1]>>ñ
+ }
+ dst[0] = src[0] << n
}
-func shiftRight(dst, src []Word, n int) {
+func shiftRight(dst, src []Word, n uint) {
if len(src) == 0 {
return
}
- ñ := _W - uint(n)
+ ñ := _W - n
for i := 0; i < len(src)-1; i++ {
- dst[i] = src[i] >> uint(n)
- dst[i] |= src[i+1] << ñ
+ dst[i] = src[i]>>n | src[i+1]<<ñ
}
- dst[len(src)-1] = src[len(src)-1] >> uint(n)
+ dst[len(src)-1] = src[len(src)-1] >> n
}
@@ -585,7 +588,7 @@
x := trailingZeroBits(n[zeroWords])
q = makeN(nil, len(n)-zeroWords, false)
- shiftRight(q, n[zeroWords:], x)
+ shiftRight(q, n[zeroWords:], uint(x))
q = normN(q)
k = Word(_W*zeroWords + x)
diff --git a/src/pkg/big/nat_test.go b/src/pkg/big/nat_test.go
index 1c993ba..8a06175 100644
--- a/src/pkg/big/nat_test.go
+++ b/src/pkg/big/nat_test.go
@@ -131,7 +131,7 @@
type shiftTest struct {
in []Word
- shift int
+ shift uint
out []Word
}
