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_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)
+ }
+ }
+}
