code review 6295076: math/big: correctly test for positive inputs in Int.GCD

math/big: correctly test for positive inputs in Int.GCD

Also: better GCD tests.

[gri, 2012-06-13 18:52:46]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go

[gri, 2012-06-13 18:57:44]

hold on - there's more bugs in the GCD code
- gri

On Wed, Jun 13, 2012 at 11:52 AM,  <gri@golang.org> wrote:
> Reviewers: rsc,
>
> Message:
> Hello rsc@golang.org (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> math/big: better GCD tests
>
> Please review this at http://codereview.appspot.com/6295076/
>
> Affected files:
>  M src/pkg/math/big/int_test.go
>
>
> Index: src/pkg/math/big/int_test.go
> ===================================================================
> --- a/src/pkg/math/big/int_test.go
> +++ b/src/pkg/math/big/int_test.go
> @@ -818,14 +818,12 @@
>  }
>
>  func checkGcd(aBytes, bBytes []byte) bool {
> +       x := new(Int)
> +       y := new(Int)
>        a := new(Int).SetBytes(aBytes)
>        b := new(Int).SetBytes(bBytes)
>
> -       x := new(Int)
> -       y := new(Int)
> -       d := new(Int)
> -
> -       d.GCD(x, y, a, b)
> +       d := new(Int).GCD(x, y, a, b)
>        x.Mul(x, a)
>        y.Mul(y, b)
>        x.Add(x, y)
> @@ -834,39 +832,73 @@
>  }
>
>  var gcdTests = []struct {
> -       a, b    int64
> -       d, x, y int64
> +       d, x, y, a, b string
>  }{
> -       {120, 23, 1, -9, 47},
> +       // a < 0 || b < 0
> +       {"0", "", "", "-77", "35"},
> +       {"0", "", "", "64515", "-24310"},
> +       {"0", "", "", "-64515", "-24310"},
> +       {"0", "", "0", "-77", "35"},
> +       {"0", "0", "", "64515", "-24310"},
> +       {"0", "0", "0", "-64515", "-24310"},
> +
> +       // x == nil && y == nil
> +       {"7", "", "", "77", "35"},
> +       {"935", "", "", "64515", "24310"},
> +       {"935000000000000000", "", "", "64515000000000000000",
> "24310000000000000000"},
> +       {"1", "", "",
>
"98920366548084643601728869055592650835572950932266967461790948584315647051443",
> "991"},
> +
> +       // x == nil || y == nil
> +       {"1", "", "47", "120", "23"},
> +       {"1", "-9", "", "120", "23"},
> +
> +       // x != nil && y != nil
> +       {"1", "-9", "47", "120", "23"},
> +       {"7", "1", "-2", "77", "35"},
> +       {"935", "-3", "8", "64515", "24310"},
> +       {"935000000000000000", "-3", "8", "64515000000000000000",
> "24310000000000000000"},
> +
> +       // test early exit (after one Euclidean iteration) in binaryGCD
> +       {"1", "", "", "1",
>
"98920366548084643601728869055592650835572950932266967461790948584315647051443"},
>  }
>
>  func TestGcd(t *testing.T) {
> -       for i, test := range gcdTests {
> -               a := NewInt(test.a)
> -               b := NewInt(test.b)
> +       for _, test := range gcdTests {
> +               d, _ := new(Int).SetString(test.d, 0)
> +               x, _ := new(Int).SetString(test.x, 0)
> +               y, _ := new(Int).SetString(test.y, 0)
> +               a, _ := new(Int).SetString(test.a, 0)
> +               b, _ := new(Int).SetString(test.b, 0)
>
> -               x := new(Int)
> -               y := new(Int)
> -               d := new(Int)
> -
> -               expectedX := NewInt(test.x)
> -               expectedY := NewInt(test.y)
> -               expectedD := NewInt(test.d)
> -
> -               d.GCD(x, y, a, b)
> -
> -               if expectedX.Cmp(x) != 0 ||
> -                       expectedY.Cmp(y) != 0 ||
> -                       expectedD.Cmp(d) != 0 {
> -                       t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x,
> y, d, expectedX, expectedY, expectedD)
> +               var X *Int
> +               if x != nil {
> +                       X = new(Int)
> +               }
> +               var Y *Int
> +               if y != nil {
> +                       Y = new(Int)
>                }
>
> -               d.binaryGCD(a, b)
> -
> -               if expectedD.Cmp(d) != 0 {
> -                       t.Errorf("#%d got (%s) want (%s)", i, d, expectedD)
> +               D := new(Int).GCD(X, Y, a, b)
> +               if D.Cmp(d) != 0 {
> +                       t.Errorf("GCD(%s, %s): got d = %s, want %s", a, b,
> D, d)
> +               }
> +               if x != nil && X.Cmp(x) != 0 {
> +                       t.Errorf("GCD(%s, %s): got x = %s, want %s", a, b,
> X, x)
> +               }
> +               if y != nil && Y.Cmp(y) != 0 {
> +                       t.Errorf("GCD(%s, %s): got y = %s, want %s", a, b,
> Y, y)
>                }
>
> +               // binaryGCD requires a > 0 && b > 0
> +               if a.Sign() < 0 || b.Sign() < 0 {
> +                       continue
> +               }
> +
> +               D.binaryGCD(a, b)
> +               if D.Cmp(d) != 0 {
> +                       t.Errorf("binaryGcd(%s, %s): got d = %s, want %s",
> a, b, D, d)
> +               }
>        }
>
>        quick.Check(checkGcd, nil)
>
>

[rsc, 2012-06-13 18:58:30]

LGTM

[rsc, 2012-06-13 18:59:47]

One way to expand the tests would be to make the test table lines
complete (no "") and then for every test try X,nil, nil,Y, X,Y, and
nil,nil.

Russ

[gri, 2012-06-13 20:28:39]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-06-13 20:46:17]

LGTM

[gri, 2012-06-13 20:54:48]

*** Submitted as http://code.google.com/p/go/source/detail?r=74d2ea85249e ***

math/big: correctly test for positive inputs in Int.GCD

Also: better GCD tests.

R=rsc
CC=golang-dev
http://codereview.appspot.com/6295076