bigint_go1.14_test.go

Documentation: github.com/cockroachdb/apd/v3

     1  // Copyright 2022 The Cockroach Authors.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
    12  // implied. See the License for the specific language governing
    13  // permissions and limitations under the License.
    14  
    15  //go:build go1.14
    16  // +build go1.14
    17  
    18  package apd
    19  
    20  import (
    21  	"testing"
    22  	"testing/quick"
    23  )
    24  
    25  //////////////////////////////////////////////////////////////////////////////////
    26  // The following tests were copied from the standard library's math/big package //
    27  //////////////////////////////////////////////////////////////////////////////////
    28  
    29  func checkGcd(aBytes, bBytes []byte) bool {
    30  	x := new(BigInt)
    31  	y := new(BigInt)
    32  	a := new(BigInt).SetBytes(aBytes)
    33  	b := new(BigInt).SetBytes(bBytes)
    34  
    35  	d := new(BigInt).GCD(x, y, a, b)
    36  	x.Mul(x, a)
    37  	y.Mul(y, b)
    38  	x.Add(x, y)
    39  
    40  	return x.Cmp(d) == 0
    41  }
    42  
    43  var gcdTests = []struct {
    44  	d, x, y, a, b string
    45  }{
    46  	// a <= 0 || b <= 0
    47  	{"0", "0", "0", "0", "0"},
    48  	{"7", "0", "1", "0", "7"},
    49  	{"7", "0", "-1", "0", "-7"},
    50  	{"11", "1", "0", "11", "0"},
    51  	{"7", "-1", "-2", "-77", "35"},
    52  	{"935", "-3", "8", "64515", "24310"},
    53  	{"935", "-3", "-8", "64515", "-24310"},
    54  	{"935", "3", "-8", "-64515", "-24310"},
    55  
    56  	{"1", "-9", "47", "120", "23"},
    57  	{"7", "1", "-2", "77", "35"},
    58  	{"935", "-3", "8", "64515", "24310"},
    59  	{"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
    60  	{"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
    61  }
    62  
    63  func testGcd(t *testing.T, d, x, y, a, b *BigInt) {
    64  	var X *BigInt
    65  	if x != nil {
    66  		X = new(BigInt)
    67  	}
    68  	var Y *BigInt
    69  	if y != nil {
    70  		Y = new(BigInt)
    71  	}
    72  
    73  	D := new(BigInt).GCD(X, Y, a, b)
    74  	if D.Cmp(d) != 0 {
    75  		t.Errorf("GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
    76  	}
    77  	if x != nil && X.Cmp(x) != 0 {
    78  		t.Errorf("GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
    79  	}
    80  	if y != nil && Y.Cmp(y) != 0 {
    81  		t.Errorf("GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
    82  	}
    83  
    84  	// check results in presence of aliasing (issue #11284)
    85  	a2 := new(BigInt).Set(a)
    86  	b2 := new(BigInt).Set(b)
    87  	a2.GCD(X, Y, a2, b2) // result is same as 1st argument
    88  	if a2.Cmp(d) != 0 {
    89  		t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, a2, d)
    90  	}
    91  	if x != nil && X.Cmp(x) != 0 {
    92  		t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
    93  	}
    94  	if y != nil && Y.Cmp(y) != 0 {
    95  		t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
    96  	}
    97  
    98  	a2 = new(BigInt).Set(a)
    99  	b2 = new(BigInt).Set(b)
   100  	b2.GCD(X, Y, a2, b2) // result is same as 2nd argument
   101  	if b2.Cmp(d) != 0 {
   102  		t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, b2, d)
   103  	}
   104  	if x != nil && X.Cmp(x) != 0 {
   105  		t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
   106  	}
   107  	if y != nil && Y.Cmp(y) != 0 {
   108  		t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
   109  	}
   110  
   111  	a2 = new(BigInt).Set(a)
   112  	b2 = new(BigInt).Set(b)
   113  	D = new(BigInt).GCD(a2, b2, a2, b2) // x = a, y = b
   114  	if D.Cmp(d) != 0 {
   115  		t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
   116  	}
   117  	if x != nil && a2.Cmp(x) != 0 {
   118  		t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, a2, x)
   119  	}
   120  	if y != nil && b2.Cmp(y) != 0 {
   121  		t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, b2, y)
   122  	}
   123  
   124  	a2 = new(BigInt).Set(a)
   125  	b2 = new(BigInt).Set(b)
   126  	D = new(BigInt).GCD(b2, a2, a2, b2) // x = b, y = a
   127  	if D.Cmp(d) != 0 {
   128  		t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
   129  	}
   130  	if x != nil && b2.Cmp(x) != 0 {
   131  		t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, b2, x)
   132  	}
   133  	if y != nil && a2.Cmp(y) != 0 {
   134  		t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, a2, y)
   135  	}
   136  }
   137  
   138  // This was not supported in go1.13. See https://go.dev/doc/go1.14:
   139  // > The GCD method now allows the inputs a and b to be zero or negative.
   140  func TestBigIntGcd(t *testing.T) {
   141  	for _, test := range gcdTests {
   142  		d, _ := new(BigInt).SetString(test.d, 0)
   143  		x, _ := new(BigInt).SetString(test.x, 0)
   144  		y, _ := new(BigInt).SetString(test.y, 0)
   145  		a, _ := new(BigInt).SetString(test.a, 0)
   146  		b, _ := new(BigInt).SetString(test.b, 0)
   147  
   148  		testGcd(t, d, nil, nil, a, b)
   149  		testGcd(t, d, x, nil, a, b)
   150  		testGcd(t, d, nil, y, a, b)
   151  		testGcd(t, d, x, y, a, b)
   152  	}
   153  
   154  	if err := quick.Check(checkGcd, nil); err != nil {
   155  		t.Error(err)
   156  	}
   157  }
   158
View as plain text