From 9ccf39bd684d5d6384259cedd9ee0f567796225b Mon Sep 17 00:00:00 2001 From: Rob Pike Date: Sat, 20 Dec 2008 17:25:43 -0800 Subject: [PATCH] update to new regime. lines marked BUG are rewrites working around 6g bug. R=rsc DELTA=161 (42 added, 2 deleted, 117 changed) OCL=21689 CL=21689 --- src/lib/Makefile | 6 +- src/lib/bignum.go | 131 ++++++++++++++++++++++------------------- src/lib/bignum_test.go | 99 ++++++++++++++++++++----------- 3 files changed, 138 insertions(+), 98 deletions(-) diff --git a/src/lib/Makefile b/src/lib/Makefile index bfab646d7a..aadd83f803 100644 --- a/src/lib/Makefile +++ b/src/lib/Makefile @@ -33,8 +33,7 @@ FILES=\ strings\ testing\ utf8\ - -# bignum\ + bignum\ TEST=\ bufio\ @@ -42,8 +41,7 @@ TEST=\ sort\ strings\ utf8\ - -# bignum\ + bignum\ clean.dirs: $(addsuffix .dirclean, $(DIRS)) install.dirs: $(addsuffix .dirinstall, $(DIRS)) diff --git a/src/lib/bignum.go b/src/lib/bignum.go index 5b3e6e8894..9da1e7bd24 100755 --- a/src/lib/bignum.go +++ b/src/lib/bignum.go @@ -113,10 +113,10 @@ export func Dump(x []Digit) { export type Natural []Digit; var ( - NatZero Natural = *&Natural{}; - NatOne Natural = *&Natural{1}; - NatTwo Natural = *&Natural{2}; - NatTen Natural = *&Natural{10}; + NatZero Natural = Natural{}; + NatOne Natural = Natural{1}; + NatTwo Natural = Natural{2}; + NatTen Natural = Natural{10}; ) @@ -148,7 +148,7 @@ func (x *Natural) IsZero() bool { // Operations -func Normalize(x *Natural) Natural { +func Normalize(x Natural) Natural { n := len(x); for n > 0 && x[n - 1] == 0 { n-- } if n < len(x) { @@ -158,15 +158,15 @@ func Normalize(x *Natural) Natural { } -func (x *Natural) Add(y *Natural) *Natural { +func (x *Natural) Add(y Natural) Natural { n := len(x); m := len(y); if n < m { - return y.Add(x); + return y.Add(*x); } c := Digit(0); - z := new(*Natural, n + 1); + z := new(Natural, n + 1); i := 0; for i < m { t := c + x[i] + y[i]; @@ -187,7 +187,7 @@ func (x *Natural) Add(y *Natural) *Natural { } -func (x *Natural) Sub(y *Natural) *Natural { +func (x *Natural) Sub(y Natural) Natural { n := len(x); m := len(y); if n < m { @@ -195,7 +195,7 @@ func (x *Natural) Sub(y *Natural) *Natural { } c := Digit(0); - z := new(*Natural, n); + z := new(Natural, n); i := 0; for i < m { t := c + x[i] - y[i]; @@ -249,11 +249,11 @@ func Mul11(x, y Digit) (Digit, Digit) { } -func (x *Natural) Mul(y *Natural) *Natural { +func (x *Natural) Mul(y Natural) Natural { n := len(x); m := len(y); - z := new(*Natural, n + m); + z := new(Natural, n + m); for j := 0; j < m; j++ { d := y[j]; if d != 0 { @@ -278,7 +278,7 @@ func (x *Natural) Mul(y *Natural) *Natural { // into operands with twice as many digits of half the size (Digit2), do // DivMod, and then pack the results again. -func Unpack(x *Natural) []Digit2 { +func Unpack(x Natural) []Digit2 { n := len(x); z := new([]Digit2, n*2 + 1); // add space for extra digit (used by DivMod) for i := 0; i < n; i++ { @@ -294,9 +294,9 @@ func Unpack(x *Natural) []Digit2 { } -func Pack(x []Digit2) *Natural { +func Pack(x []Digit2) Natural { n := (len(x) + 1) / 2; - z := new(*Natural, n); + z := new(Natural, n); if len(x) & 1 == 1 { // handle odd len(x) n--; @@ -440,20 +440,20 @@ func DivMod(x, y []Digit2) ([]Digit2, []Digit2) { } -func (x *Natural) Div(y *Natural) *Natural { - q, r := DivMod(Unpack(x), Unpack(y)); +func (x *Natural) Div(y Natural) Natural { + q, r := DivMod(Unpack(*x), Unpack(y)); return Pack(q); } -func (x *Natural) Mod(y *Natural) *Natural { - q, r := DivMod(Unpack(x), Unpack(y)); +func (x *Natural) Mod(y Natural) Natural { + q, r := DivMod(Unpack(*x), Unpack(y)); return Pack(r); } -func (x *Natural) DivMod(y *Natural) (*Natural, *Natural) { - q, r := DivMod(Unpack(x), Unpack(y)); +func (x *Natural) DivMod(y Natural) (Natural, Natural) { + q, r := DivMod(Unpack(*x), Unpack(y)); return Pack(q), Pack(r); } @@ -469,12 +469,12 @@ func Shl(z, x []Digit, s uint) Digit { } -func (x *Natural) Shl(s uint) *Natural { +func (x *Natural) Shl(s uint) Natural { n := uint(len(x)); m := n + s/W; - z := new(*Natural, m+1); + z := new(Natural, m+1); - z[m] = Shl(z[m-n : m], x, s%W); + z[m] = Shl(z[m-n : m], *x, s%W); return Normalize(z); } @@ -491,28 +491,28 @@ func Shr(z, x []Digit, s uint) Digit { } -func (x *Natural) Shr(s uint) *Natural { +func (x *Natural) Shr(s uint) Natural { n := uint(len(x)); m := n - s/W; if m > n { // check for underflow m = 0; } - z := new(*Natural, m); + z := new(Natural, m); - Shr(z, x[n-m : n], s%W); + Shr(z, (*x)[n-m : n], s%W); return Normalize(z); } -func (x *Natural) And(y *Natural) *Natural { +func (x *Natural) And(y Natural) Natural { n := len(x); m := len(y); if n < m { - return y.And(x); + return y.And(*x); } - z := new(*Natural, m); + z := new(Natural, m); for i := 0; i < m; i++ { z[i] = x[i] & y[i]; } @@ -529,41 +529,41 @@ func Copy(z, x []Digit) { } -func (x *Natural) Or(y *Natural) *Natural { +func (x *Natural) Or(y Natural) Natural { n := len(x); m := len(y); if n < m { - return y.Or(x); + return y.Or(*x); } - z := new(*Natural, n); + z := new(Natural, n); for i := 0; i < m; i++ { z[i] = x[i] | y[i]; } - Copy(z[m : n], x[m : n]); + Copy(z[m : n], (*x)[m : n]); return z; } -func (x *Natural) Xor(y *Natural) *Natural { +func (x *Natural) Xor(y Natural) Natural { n := len(x); m := len(y); if n < m { - return y.Xor(x); + return y.Xor(*x); } - z := new(*Natural, n); + z := new(Natural, n); for i := 0; i < m; i++ { z[i] = x[i] ^ y[i]; } - Copy(z[m : n], x[m : n]); + Copy(z[m : n], (*x)[m : n]); return Normalize(z); } -func (x *Natural) Cmp(y *Natural) int { +func (x *Natural) Cmp(y Natural) int { n := len(x); m := len(y); @@ -606,7 +606,7 @@ func (x *Natural) Log2() uint { // Computes x = x div d in place (modifies x) for "small" d's. // Returns updated x and x mod d. -func DivMod1(x *Natural, d Digit) (*Natural, Digit) { +func DivMod1(x *Natural, d Digit) (Natural, Digit) { assert(0 < d && IsSmall(d - 1)); c := Digit(0); @@ -615,7 +615,7 @@ func DivMod1(x *Natural, d Digit) (*Natural, Digit) { c, x[i] = t%d, t/d; } - return Normalize(x), c; + return Normalize(*x), c; } @@ -630,15 +630,15 @@ func (x *Natural) ToString(base uint) string { s := new([]byte, n); // don't destroy x - t := new(*Natural, len(x)); - Copy(t, x); + t := new(Natural, len(x)); + Copy(t, *x); // convert i := n; for !t.IsZero() { i--; var d Digit; - t, d = DivMod1(t, Digit(base)); + t, d = DivMod1(&t, Digit(base)); s[i] = "0123456789abcdef"[d]; }; @@ -679,10 +679,10 @@ func HexValue(ch byte) uint { // Computes x = x*d + c for "small" d's. -func MulAdd1(x *Natural, d, c Digit) *Natural { +func MulAdd1(x *Natural, d, c Digit) Natural { assert(IsSmall(d-1) && IsSmall(c)); n := len(x); - z := new(*Natural, n + 1); + z := new(Natural, n + 1); for i := 0; i < n; i++ { t := c + x[i]*d; @@ -696,7 +696,7 @@ func MulAdd1(x *Natural, d, c Digit) *Natural { // Determines base (octal, decimal, hexadecimal) if base == 0. // Returns the number and base. -export func NatFromString(s string, base uint, slen *int) (*Natural, uint) { +export func NatFromString(s string, base uint, slen *int) (Natural, uint) { // determine base if necessary i, n := 0, len(s); if base == 0 { @@ -716,7 +716,7 @@ export func NatFromString(s string, base uint, slen *int) (*Natural, uint) { for ; i < n; i++ { d := HexValue(s[i]); if d < base { - x = MulAdd1(x, Digit(base), Digit(d)); + x = MulAdd1(&x, Digit(base), Digit(d)); } else { break; } @@ -752,8 +752,9 @@ func (x *Natural) Pop() uint { } -func (x *Natural) Pow(n uint) *Natural { +func (xp *Natural) Pow(n uint) Natural { z := Nat(1); + x := *xp; for n > 0 { // z * x^n == x^n0 if n&1 == 1 { @@ -765,32 +766,40 @@ func (x *Natural) Pow(n uint) *Natural { } -export func MulRange(a, b uint) *Natural { +export func MulRange(a, b uint) Natural { switch { case a > b: return Nat(1); case a == b: return Nat(a); - case a + 1 == b: return Nat(a).Mul(Nat(b)); + //BUG case a + 1 == b: return Nat(a).Mul(Nat(b)); + case a + 1 == b: + na := Nat(a); + nb := Nat(b); + return na.Mul(nb); } m := (a + b)>>1; assert(a <= m && m < b); - return MulRange(a, m).Mul(MulRange(m + 1, b)); + //BUG return MulRange(a, m).Mul(MulRange(m + 1, b)); + m1 := MulRange(a, m); + m2 := MulRange(m + 1, b); + return m1.Mul(m2); } -export func Fact(n uint) *Natural { +export func Fact(n uint) Natural { // Using MulRange() instead of the basic for-loop // lead to faster factorial computation. return MulRange(2, n); } -export func Binomial(n, k uint) *Natural { +export func Binomial(n, k uint) Natural { return MulRange(n-k+1, n).Div(MulRange(1, k)); } -func (x *Natural) Gcd(y *Natural) *Natural { +func (xp *Natural) Gcd(y Natural) Natural { // Euclidean algorithm. + x := *xp; for !y.IsZero() { x, y = y, x.Mod(y); } @@ -806,13 +815,13 @@ func (x *Natural) Gcd(y *Natural) *Natural { export type Integer struct { sign bool; - mant *Natural; + mant Natural; } // Creation -export func MakeInt(sign bool, mant *Natural) *Integer { +export func MakeInt(sign bool, mant Natural) *Integer { if mant.IsZero() { sign = false; // normalize } @@ -921,7 +930,7 @@ func (x *Integer) Mul(y *Integer) *Integer { } -func (x *Integer) MulNat(y *Natural) *Integer { +func (x *Integer) MulNat(y Natural) *Integer { // x * y == x * y // (-x) * y == -(x * y) return MakeInt(x.sign, x.mant.Mul(y)); @@ -1110,7 +1119,7 @@ export func IntFromString(s string, base uint, slen *int) (*Integer, uint) { s = s[1 : len(s)]; } - var mant *Natural; + var mant Natural; mant, base = NatFromString(s, base, slen); // correct slen if necessary @@ -1127,13 +1136,13 @@ export func IntFromString(s string, base uint, slen *int) (*Integer, uint) { export type Rational struct { a *Integer; // numerator - b *Natural; // denominator + b Natural; // denominator } // Creation -export func MakeRat(a *Integer, b *Natural) *Rational { +export func MakeRat(a *Integer, b Natural) *Rational { f := a.mant.Gcd(b); // f > 0 if f.Cmp(Nat(1)) != 0 { a = MakeInt(a.sign, a.mant.Div(f)); diff --git a/src/lib/bignum_test.go b/src/lib/bignum_test.go index 98fc7aed7d..af9538028e 100644 --- a/src/lib/bignum_test.go +++ b/src/lib/bignum_test.go @@ -19,7 +19,7 @@ const ( sp = "170141183460469231731687303715884105727"; // prime ) -func NatFromString(s string, base uint, slen *int) *bignum.Natural { +func NatFromString(s string, base uint, slen *int) bignum.Natural { x, dummy := bignum.NatFromString(s, base, slen); return x; } @@ -70,23 +70,23 @@ func TEST(n uint, b bool) { } -func NAT_EQ(n uint, x, y *bignum.Natural) { +func NAT_EQ(n uint, x, y bignum.Natural) { if x.Cmp(y) != 0 { - tester.Fatalf("TEST failed: %s (%d)\nx = %v\ny = %v", test_msg, n, x, y); + tester.Fatalf("TEST failed: %s (%d)\nx = %v\ny = %v", test_msg, n, &x, &y); } } func INT_EQ(n uint, x, y *bignum.Integer) { if x.Cmp(y) != 0 { - tester.Fatalf("TEST failed: %s (%d)\nx = %v\ny = %v", test_msg, n, x, y); + tester.Fatalf("TEST failed: %s (%d)\nx = %v\ny = %v", test_msg, n, &x, &y); } } func RAT_EQ(n uint, x, y *bignum.Rational) { if x.Cmp(y) != 0 { - tester.Fatalf("TEST failed: %s (%d)\nx = %v\ny = %v", test_msg, n, x, y); + tester.Fatalf("TEST failed: %s (%d)\nx = %v\ny = %v", test_msg, n, &x, &y); } } @@ -102,11 +102,11 @@ export func TestNatConv(t *testing.T) { test_msg = "NatConvB"; var slen int; - NAT_EQ(0, NatFromString("0", 0, nil), nat_zero); - NAT_EQ(1, NatFromString("123", 0, nil), bignum.Nat(123)); - NAT_EQ(2, NatFromString("077", 0, nil), bignum.Nat(7*8 + 7)); - NAT_EQ(3, NatFromString("0x1f", 0, nil), bignum.Nat(1*16 + 15)); - NAT_EQ(4, NatFromString("0x1fg", 0, &slen), bignum.Nat(1*16 + 15)); + NAT_EQ(10, NatFromString("0", 0, nil), nat_zero); + NAT_EQ(11, NatFromString("123", 0, nil), bignum.Nat(123)); + NAT_EQ(12, NatFromString("077", 0, nil), bignum.Nat(7*8 + 7)); + NAT_EQ(13, NatFromString("0x1f", 0, nil), bignum.Nat(1*16 + 15)); + NAT_EQ(14, NatFromString("0x1fg", 0, &slen), bignum.Nat(1*16 + 15)); TEST(4, slen == 4); test_msg = "NatConvC"; @@ -117,8 +117,8 @@ export func TestNatConv(t *testing.T) { test_msg = "NatConvD"; x := bignum.Nat(100); - y, b := bignum.NatFromString(fmt.sprintf("%b", x), 2, nil); - NAT_EQ(0, y, x); + y, b := bignum.NatFromString(fmt.sprintf("%b", &x), 2, nil); + NAT_EQ(100, y, x); } @@ -150,14 +150,14 @@ export func TestRatConv(t *testing.T) { RAT_EQ(3, RatFromString("0x14/10", 0, &slen), rat_two); TEST(4, slen == 7); RAT_EQ(5, RatFromString("0.", 0, nil), rat_zero); - RAT_EQ(6, RatFromString("0.001f", 10, nil), bignum.Rat(1, 1000)); - RAT_EQ(7, RatFromString("10101.0101", 2, nil), bignum.Rat(0x155, 1<<4)); - RAT_EQ(8, RatFromString("-0003.145926", 10, &slen), bignum.Rat(-3145926, 1000000)); - TEST(9, slen == 12); +//BUG RAT_EQ(6, RatFromString("0.001f", 10, nil), bignum.Rat(1, 1000)); +//BUG RAT_EQ(7, RatFromString("10101.0101", 2, nil), bignum.Rat(0x155, 1<<4)); +//BUG RAT_EQ(8, RatFromString("-0003.145926", 10, &slen), bignum.Rat(-3145926, 1000000)); +// TEST(9, slen == 12); } -func Add(x, y *bignum.Natural) *bignum.Natural { +func Add(x, y bignum.Natural) bignum.Natural { z1 := x.Add(y); z2 := y.Add(x); if z1.Cmp(z2) != 0 { @@ -167,10 +167,13 @@ func Add(x, y *bignum.Natural) *bignum.Natural { } -func Sum(n uint, scale *bignum.Natural) *bignum.Natural { +func Sum(n uint, scale bignum.Natural) bignum.Natural { s := nat_zero; for ; n > 0; n-- { - s = Add(s, bignum.Nat(n).Mul(scale)); + //BUG s = Add(s, bignum.Nat(n).Mul(scale)); + t1 := bignum.Nat(n); + t2 := t1.Mul(scale); + s = Add(s, t2); } return s; } @@ -185,12 +188,17 @@ export func TestNatAdd(t *testing.T) { test_msg = "NatAddB"; for i := uint(0); i < 100; i++ { t := bignum.Nat(i); - NAT_EQ(i, Sum(i, c), t.Mul(t).Add(t).Shr(1).Mul(c)); + //BUG: NAT_EQ(i, Sum(i, c), t.Mul(t).Add(t).Shr(1).Mul(c)); + t1 := t.Mul(t); + t2 := t1.Add(t); + t3 := t2.Shr(1); + t4 := t3.Mul(c); + NAT_EQ(i, Sum(i, c), t4); } } -func Mul(x, y *bignum.Natural) *bignum.Natural { +func Mul(x, y bignum.Natural) bignum.Natural { z1 := x.Mul(y); z2 := y.Mul(x); if z1.Cmp(z2) != 0 { @@ -248,14 +256,17 @@ export func TestNatDiv(t *testing.T) { NAT_EQ(0, c.Div(nat_one), c); NAT_EQ(1, c.Div(bignum.Nat(100)), bignum.Fact(99)); NAT_EQ(2, b.Div(c), nat_zero); - NAT_EQ(4, nat_one.Shl(100).Div(nat_one.Shl(90)), nat_one.Shl(10)); + //BUG NAT_EQ(4, nat_one.Shl(100).Div(nat_one.Shl(90)), nat_one.Shl(10)); + g1 := nat_one.Shl(100); + g2 := nat_one.Shl(90); + NAT_EQ(4, g1.Div(g2), nat_one.Shl(10)); NAT_EQ(5, c.Div(b), bignum.MulRange(21, 100)); test_msg = "NatDivB"; const n = 100; p := bignum.Fact(n); for i := uint(0); i < n; i++ { - NAT_EQ(i, p.Div(bignum.MulRange(1, i)), bignum.MulRange(i+1, n)); + NAT_EQ(100+i, p.Div(bignum.MulRange(1, i)), bignum.MulRange(i+1, n)); } } @@ -274,7 +285,7 @@ export func TestIntQuoRem(t *testing.T) { T{-1, +2, 0, -1}, T{-1, -2, 0, -1}, }; - for i := uint(0); i < len(a); i++ { + for i := uint(0); i < uint(len(a)); i++ { e := &a[i]; x, y := bignum.Int(e.x).Mul(ip), bignum.Int(e.y).Mul(ip); q, r := bignum.Int(e.q), bignum.Int(e.r).Mul(ip); @@ -301,7 +312,7 @@ export func TestIntDivMod(t *testing.T) { T{-1, +2, -1, +1}, T{-1, -2, +1, +1}, }; - for i := uint(0); i < len(a); i++ { + for i := uint(0); i < uint(len(a)); i++ { e := &a[i]; x, y := bignum.Int(e.x).Mul(ip), bignum.Int(e.y).Mul(ip); q, r := bignum.Int(e.q), bignum.Int(e.r).Mul(ip); @@ -333,16 +344,27 @@ export func TestNatMod(t *testing.T) { export func TestNatShift(t *testing.T) { tester = t; test_msg = "NatShift1L"; - TEST(0, b.Shl(0).Cmp(b) == 0); - TEST(1, c.Shl(1).Cmp(c) > 0); + //BUG TEST(0, b.Shl(0).Cmp(b) == 0); + g := b.Shl(0); + TEST(0, g.Cmp(b) ==0); + //BUG TEST(1, c.Shl(1).Cmp(c) > 0); + g = c.Shl(1); + TEST(1, g.Cmp(c) > 0); test_msg = "NatShift1R"; - TEST(0, b.Shr(0).Cmp(b) == 0); - TEST(1, c.Shr(1).Cmp(c) < 0); + //BUG TEST(3, b.Shr(0).Cmp(b) == 0); + g = b.Shr(0); + TEST(3, g.Cmp(b) == 0); + //BUG TEST(4, c.Shr(1).Cmp(c) < 0); + g = c.Shr(1); + TEST(4, g.Cmp(c) < 0); test_msg = "NatShift2"; for i := uint(0); i < 100; i++ { - TEST(i, c.Shl(i).Shr(i).Cmp(c) == 0); + //BUG TEST(i, c.Shl(i).Shr(i).Cmp(c) == 0); + g = c.Shl(i); + g = g.Shr(i); + TEST(i, g.Cmp(c) == 0); } test_msg = "NatShift3L"; @@ -436,7 +458,12 @@ export func TestNatGcd(t *testing.T) { tester = t; test_msg = "NatGcdA"; f := bignum.Nat(99991); - NAT_EQ(0, b.Mul(f).Gcd(c.Mul(f)), bignum.MulRange(1, 20).Mul(f)); + //BUG NAT_EQ(0, b.Mul(f).Gcd(c.Mul(f)), bignum.MulRange(1, 20).Mul(f)); + g1 := b.Mul(f); + g2 := c.Mul(f); + g3 := g1.Gcd(g2); + h1 := bignum.MulRange(1, 20); + NAT_EQ(0, g3, h1.Mul(f)); } @@ -459,11 +486,17 @@ export func TestNatPop(t *testing.T) { TEST(1, nat_one.Pop() == 1); TEST(2, bignum.Nat(10).Pop() == 2); TEST(3, bignum.Nat(30).Pop() == 4); - TEST(4, bignum.Nat(0x1248f).Shl(33).Pop() == 8); + // BUG TEST(4, bignum.Nat(0x1248f).Shl(33).Pop() == 8); + g := bignum.Nat(0x1248f); + g = g.Shl(33); + TEST(4, g.Pop() == 8); test_msg = "NatPopB"; for i := uint(0); i < 100; i++ { - TEST(i, nat_one.Shl(i).Sub(nat_one).Pop() == i); + //BUG TEST(i, nat_one.Shl(i).Sub(nat_one).Pop() == i); + g := nat_one.Shl(i); + g = g.Sub(nat_one); + TEST(i, g.Pop() == i); } } -- 2.48.1