Index: src/pkg/bignum/nrdiv_test.go |
=================================================================== |
--- a/src/pkg/bignum/nrdiv_test.go |
+++ b/src/pkg/bignum/nrdiv_test.go |
@@ -21,8 +21,8 @@ |
// value of an fpNat x is x.m * 2^x.e . |
// |
type fpNat struct { |
- m Natural; |
- e int; |
+ m Natural |
+ e int |
} |
@@ -34,16 +34,16 @@ |
case d > 0: |
return fpNat{x.m.Shl(uint(d)).Sub(y.m), y.e} |
} |
- return fpNat{x.m.Sub(y.m), x.e}; |
+ return fpNat{x.m.Sub(y.m), x.e} |
} |
// mul2 computes x*2. |
-func (x fpNat) mul2() fpNat { return fpNat{x.m, x.e + 1} } |
+func (x fpNat) mul2() fpNat { return fpNat{x.m, x.e + 1} } |
// mul computes x*y. |
-func (x fpNat) mul(y fpNat) fpNat { return fpNat{x.m.Mul(y.m), x.e + y.e} } |
+func (x fpNat) mul(y fpNat) fpNat { return fpNat{x.m.Mul(y.m), x.e + y.e} } |
// mant computes the (possibly truncated) Natural representation |
@@ -56,7 +56,7 @@ |
case x.e < 0: |
return x.m.Shr(uint(-x.e)) |
} |
- return x.m; |
+ return x.m |
} |
@@ -65,8 +65,8 @@ |
// |
func nrDivEst(x0, y0 Natural) Natural { |
if y0.IsZero() { |
- panic("division by zero"); |
- return nil; |
+ panic("division by zero") |
+ return nil |
} |
// y0 > 0 |
@@ -84,78 +84,78 @@ |
// x0 > y0 > 1 |
// Determine maximum result length. |
- maxLen := int(x0.Log2() - y0.Log2() + 1); |
+ maxLen := int(x0.Log2() - y0.Log2() + 1) |
// In the following, each number x is represented |
// as a mantissa x.m and an exponent x.e such that |
// x = xm * 2^x.e. |
- x := fpNat{x0, 0}; |
- y := fpNat{y0, 0}; |
+ x := fpNat{x0, 0} |
+ y := fpNat{y0, 0} |
// Determine a scale factor f = 2^e such that |
// 0.5 <= y/f == y*(2^-e) < 1.0 |
// and scale y accordingly. |
- e := int(y.m.Log2()) + 1; |
- y.e -= e; |
+ e := int(y.m.Log2()) + 1 |
+ y.e -= e |
// t1 |
- var c = 2.9142; |
- const n = 14; |
- t1 := fpNat{Nat(uint64(c * (1 << n))), -n}; |
+ var c = 2.9142 |
+ const n = 14 |
+ t1 := fpNat{Nat(uint64(c * (1 << n))), -n} |
// Compute initial value r0 for the reciprocal of y/f. |
// r0 = t1 - 2*y |
- r := t1.sub(y.mul2()); |
- two := fpNat{Nat(2), 0}; |
+ r := t1.sub(y.mul2()) |
+ two := fpNat{Nat(2), 0} |
// Newton-Raphson iteration |
- p := Nat(0); |
+ p := Nat(0) |
for i := 0; ; i++ { |
// check if we are done |
// TODO: Need to come up with a better test here |
// as it will reduce computation time significantly. |
// q = x*r/f |
- q := x.mul(r); |
- q.e -= e; |
- res := q.mant(); |
+ q := x.mul(r) |
+ q.e -= e |
+ res := q.mant() |
if res.Cmp(p) == 0 { |
return res |
} |
- p = res; |
+ p = res |
// r' = r*(2 - y*r) |
- r = r.mul(two.sub(y.mul(r))); |
+ r = r.mul(two.sub(y.mul(r))) |
// reduce mantissa size |
// TODO: Find smaller bound as it will reduce |
// computation time massively. |
- d := int(r.m.Log2()+1) - maxLen; |
+ d := int(r.m.Log2()+1) - maxLen |
if d > 0 { |
r = fpNat{r.m.Shr(uint(d)), r.e + d} |
} |
} |
- panic("unreachable"); |
- return nil; |
+ panic("unreachable") |
+ return nil |
} |
func nrdiv(x, y Natural) (q, r Natural) { |
- q = nrDivEst(x, y); |
- r = x.Sub(y.Mul(q)); |
+ q = nrDivEst(x, y) |
+ r = x.Sub(y.Mul(q)) |
// if r is too large, correct q and r |
// (usually one iteration) |
for r.Cmp(y) >= 0 { |
- q = q.Add(Nat(1)); |
- r = r.Sub(y); |
+ q = q.Add(Nat(1)) |
+ r = r.Sub(y) |
} |
- return; |
+ return |
} |
func div(t *testing.T, x, y Natural) { |
- q, r := nrdiv(x, y); |
- qx, rx := x.DivMod(y); |
+ q, r := nrdiv(x, y) |
+ qx, rx := x.DivMod(y) |
if q.Cmp(qx) != 0 { |
t.Errorf("x = %s, y = %s, got q = %s, want q = %s", x, y, q, qx) |
} |
@@ -165,24 +165,24 @@ |
} |
-func idiv(t *testing.T, x0, y0 uint64) { div(t, Nat(x0), Nat(y0)) } |
+func idiv(t *testing.T, x0, y0 uint64) { div(t, Nat(x0), Nat(y0)) } |
func TestNRDiv(t *testing.T) { |
- idiv(t, 17, 18); |
- idiv(t, 17, 17); |
- idiv(t, 17, 1); |
- idiv(t, 17, 16); |
- idiv(t, 17, 10); |
- idiv(t, 17, 9); |
- idiv(t, 17, 8); |
- idiv(t, 17, 5); |
- idiv(t, 17, 3); |
- idiv(t, 1025, 512); |
- idiv(t, 7489595, 2); |
- idiv(t, 5404679459, 78495); |
- idiv(t, 7484890589595, 7484890589594); |
- div(t, Fact(100), Fact(91)); |
- div(t, Fact(1000), Fact(991)); |
+ idiv(t, 17, 18) |
+ idiv(t, 17, 17) |
+ idiv(t, 17, 1) |
+ idiv(t, 17, 16) |
+ idiv(t, 17, 10) |
+ idiv(t, 17, 9) |
+ idiv(t, 17, 8) |
+ idiv(t, 17, 5) |
+ idiv(t, 17, 3) |
+ idiv(t, 1025, 512) |
+ idiv(t, 7489595, 2) |
+ idiv(t, 5404679459, 78495) |
+ idiv(t, 7484890589595, 7484890589594) |
+ div(t, Fact(100), Fact(91)) |
+ div(t, Fact(1000), Fact(991)) |
//div(t, Fact(10000), Fact(9991)); // takes too long - disabled for now |
} |