diff options
| -rw-r--r-- | src/pkg/big/int.go | 75 | ||||
| -rw-r--r-- | src/pkg/big/int_test.go | 163 | ||||
| -rw-r--r-- | src/pkg/big/nat.go | 27 | ||||
| -rw-r--r-- | src/pkg/big/nat_test.go | 2 | ||||
| -rw-r--r-- | test/bench/pidigits.go | 50 |
5 files changed, 239 insertions, 78 deletions
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go index 8f776b5f3..ca94c5a42 100644 --- a/src/pkg/big/int.go +++ b/src/pkg/big/int.go @@ -100,21 +100,26 @@ func (z *Int) Mul(x, y *Int) *Int { } -// 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 @@ func (z *Int) String() string { } +// 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 @@ func GcdInt(d, x, y, a, b *Int) { 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 GcdInt(d, x, y, a, b *Int) { 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 70dbe5900..1e9c0e000 100644 --- a/src/pkg/big/int_test.go +++ b/src/pkg/big/int_test.go @@ -192,7 +192,8 @@ func TestDivSigns(t *testing.T) { 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 @@ func checkDiv(x, y []byte) bool { 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 @@ func TestDiv(t *testing.T) { 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 @@ func TestDivStepD6(t *testing.T) { 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 @@ func TestProbablyPrime(t *testing.T) { } -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 TestRsh(t *testing.T) { } } } + + +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 0f4d4c37e..f8d4a2d43 100644 --- a/src/pkg/big/nat.go +++ b/src/pkg/big/nat.go @@ -302,7 +302,7 @@ func divLargeNN(z, z2, uIn, v []Word) (q, r []Word) { 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 trailingZeroBits(x Word) int { } -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) + ñ := _W - n + if len(dst) > len(src) { + dst[len(src)] |= src[len(src)-1] >> ñ + } for i := len(src) - 1; i >= 1; i-- { - dst[i] = src[i] << uint(n) - dst[i] |= src[i-1] >> ñ + dst[i] = src[i]<<n | src[i-1]>>ñ } - dst[0] = src[0] << uint(n) + 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 @@ func powersOfTwoDecompose(n []Word) (q []Word, k Word) { 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 1c993bad1..8a0617578 100644 --- a/src/pkg/big/nat_test.go +++ b/src/pkg/big/nat_test.go @@ -131,7 +131,7 @@ func TestLeadingZeroBits(t *testing.T) { type shiftTest struct { in []Word - shift int + shift uint out []Word } diff --git a/test/bench/pidigits.go b/test/bench/pidigits.go index aaa9f53a5..a05515028 100644 --- a/test/bench/pidigits.go +++ b/test/bench/pidigits.go @@ -38,7 +38,7 @@ POSSIBILITY OF SUCH DAMAGE. package main import ( - "bignum" + "big" "flag" "fmt" ) @@ -47,11 +47,14 @@ var n = flag.Int("n", 27, "number of digits") var silent = flag.Bool("s", false, "don't print result") var ( - tmp1 *bignum.Integer - tmp2 *bignum.Integer - numer = bignum.Int(1) - accum = bignum.Int(0) - denom = bignum.Int(1) + tmp1 = big.NewInt(0) + tmp2 = big.NewInt(0) + y2 = big.NewInt(0) + bigk = big.NewInt(0) + numer = big.NewInt(1) + accum = big.NewInt(0) + denom = big.NewInt(1) + ten = big.NewInt(10) ) func extract_digit() int64 { @@ -60,36 +63,39 @@ func extract_digit() int64 { } // Compute (numer * 3 + accum) / denom - tmp1 = numer.Shl(1) - bignum.Iadd(tmp1, tmp1, numer) - bignum.Iadd(tmp1, tmp1, accum) - tmp1, tmp2 := tmp1.QuoRem(denom) + tmp1.Lsh(numer, 1) + tmp1.Add(tmp1, numer) + tmp1.Add(tmp1, accum) + tmp1.DivMod(tmp1, denom, tmp2) // Now, if (numer * 4 + accum) % denom... - bignum.Iadd(tmp2, tmp2, numer) + tmp2.Add(tmp2, numer) // ... is normalized, then the two divisions have the same result. if tmp2.Cmp(denom) >= 0 { return -1 } - return tmp1.Value() + return tmp1.Int64() } func next_term(k int64) { - y2 := k*2 + 1 - - tmp1 = numer.Shl(1) - bignum.Iadd(accum, accum, tmp1) - bignum.Iscale(accum, y2) - bignum.Iscale(numer, k) - bignum.Iscale(denom, y2) + // TODO(eds) If big.Int ever gets a Scale method, y2 and bigk could be int64 + y2.New(k*2 + 1) + bigk.New(k) + + tmp1.Lsh(numer, 1) + accum.Add(accum, tmp1) + accum.Mul(accum, y2) + numer.Mul(numer, bigk) + denom.Mul(denom, y2) } func eliminate_digit(d int64) { - bignum.Isub(accum, accum, denom.Mul1(d)) - bignum.Iscale(accum, 10) - bignum.Iscale(numer, 10) + tmp := big.NewInt(0).Set(denom) + accum.Sub(accum, tmp.Mul(tmp, big.NewInt(d))) + accum.Mul(accum, ten) + numer.Mul(numer, ten) } func printf(s string, arg ...interface{}) { |