Source file src/math/big/int_test.go

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package big
     6  
     7  import (
     8  	"bytes"
     9  	"encoding/hex"
    10  	"fmt"
    11  	"internal/testenv"
    12  	"math"
    13  	"math/rand"
    14  	"strconv"
    15  	"strings"
    16  	"testing"
    17  	"testing/quick"
    18  )
    19  
    20  func isNormalized(x *Int) bool {
    21  	if len(x.abs) == 0 {
    22  		return !x.neg
    23  	}
    24  	// len(x.abs) > 0
    25  	return x.abs[len(x.abs)-1] != 0
    26  }
    27  
    28  type funZZ func(z, x, y *Int) *Int
    29  type argZZ struct {
    30  	z, x, y *Int
    31  }
    32  
    33  var sumZZ = []argZZ{
    34  	{NewInt(0), NewInt(0), NewInt(0)},
    35  	{NewInt(1), NewInt(1), NewInt(0)},
    36  	{NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
    37  	{NewInt(-1), NewInt(-1), NewInt(0)},
    38  	{NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
    39  	{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
    40  }
    41  
    42  var prodZZ = []argZZ{
    43  	{NewInt(0), NewInt(0), NewInt(0)},
    44  	{NewInt(0), NewInt(1), NewInt(0)},
    45  	{NewInt(1), NewInt(1), NewInt(1)},
    46  	{NewInt(-991 * 991), NewInt(991), NewInt(-991)},
    47  	// TODO(gri) add larger products
    48  }
    49  
    50  func TestSignZ(t *testing.T) {
    51  	var zero Int
    52  	for _, a := range sumZZ {
    53  		s := a.z.Sign()
    54  		e := a.z.Cmp(&zero)
    55  		if s != e {
    56  			t.Errorf("got %d; want %d for z = %v", s, e, a.z)
    57  		}
    58  	}
    59  }
    60  
    61  func TestSetZ(t *testing.T) {
    62  	for _, a := range sumZZ {
    63  		var z Int
    64  		z.Set(a.z)
    65  		if !isNormalized(&z) {
    66  			t.Errorf("%v is not normalized", z)
    67  		}
    68  		if (&z).Cmp(a.z) != 0 {
    69  			t.Errorf("got z = %v; want %v", z, a.z)
    70  		}
    71  	}
    72  }
    73  
    74  func TestAbsZ(t *testing.T) {
    75  	var zero Int
    76  	for _, a := range sumZZ {
    77  		var z Int
    78  		z.Abs(a.z)
    79  		var e Int
    80  		e.Set(a.z)
    81  		if e.Cmp(&zero) < 0 {
    82  			e.Sub(&zero, &e)
    83  		}
    84  		if z.Cmp(&e) != 0 {
    85  			t.Errorf("got z = %v; want %v", z, e)
    86  		}
    87  	}
    88  }
    89  
    90  func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
    91  	var z Int
    92  	f(&z, a.x, a.y)
    93  	if !isNormalized(&z) {
    94  		t.Errorf("%s%v is not normalized", msg, z)
    95  	}
    96  	if (&z).Cmp(a.z) != 0 {
    97  		t.Errorf("%v %s %v\n\tgot z = %v; want %v", a.x, msg, a.y, &z, a.z)
    98  	}
    99  }
   100  
   101  func TestSumZZ(t *testing.T) {
   102  	AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
   103  	SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
   104  	for _, a := range sumZZ {
   105  		arg := a
   106  		testFunZZ(t, "AddZZ", AddZZ, arg)
   107  
   108  		arg = argZZ{a.z, a.y, a.x}
   109  		testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
   110  
   111  		arg = argZZ{a.x, a.z, a.y}
   112  		testFunZZ(t, "SubZZ", SubZZ, arg)
   113  
   114  		arg = argZZ{a.y, a.z, a.x}
   115  		testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
   116  	}
   117  }
   118  
   119  func TestProdZZ(t *testing.T) {
   120  	MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
   121  	for _, a := range prodZZ {
   122  		arg := a
   123  		testFunZZ(t, "MulZZ", MulZZ, arg)
   124  
   125  		arg = argZZ{a.z, a.y, a.x}
   126  		testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
   127  	}
   128  }
   129  
   130  // mulBytes returns x*y via grade school multiplication. Both inputs
   131  // and the result are assumed to be in big-endian representation (to
   132  // match the semantics of Int.Bytes and Int.SetBytes).
   133  func mulBytes(x, y []byte) []byte {
   134  	z := make([]byte, len(x)+len(y))
   135  
   136  	// multiply
   137  	k0 := len(z) - 1
   138  	for j := len(y) - 1; j >= 0; j-- {
   139  		d := int(y[j])
   140  		if d != 0 {
   141  			k := k0
   142  			carry := 0
   143  			for i := len(x) - 1; i >= 0; i-- {
   144  				t := int(z[k]) + int(x[i])*d + carry
   145  				z[k], carry = byte(t), t>>8
   146  				k--
   147  			}
   148  			z[k] = byte(carry)
   149  		}
   150  		k0--
   151  	}
   152  
   153  	// normalize (remove leading 0's)
   154  	i := 0
   155  	for i < len(z) && z[i] == 0 {
   156  		i++
   157  	}
   158  
   159  	return z[i:]
   160  }
   161  
   162  func checkMul(a, b []byte) bool {
   163  	var x, y, z1 Int
   164  	x.SetBytes(a)
   165  	y.SetBytes(b)
   166  	z1.Mul(&x, &y)
   167  
   168  	var z2 Int
   169  	z2.SetBytes(mulBytes(a, b))
   170  
   171  	return z1.Cmp(&z2) == 0
   172  }
   173  
   174  func TestMul(t *testing.T) {
   175  	if err := quick.Check(checkMul, nil); err != nil {
   176  		t.Error(err)
   177  	}
   178  }
   179  
   180  var mulRangesZ = []struct {
   181  	a, b int64
   182  	prod string
   183  }{
   184  	// entirely positive ranges are covered by mulRangesN
   185  	{-1, 1, "0"},
   186  	{-2, -1, "2"},
   187  	{-3, -2, "6"},
   188  	{-3, -1, "-6"},
   189  	{1, 3, "6"},
   190  	{-10, -10, "-10"},
   191  	{0, -1, "1"},                      // empty range
   192  	{-1, -100, "1"},                   // empty range
   193  	{-1, 1, "0"},                      // range includes 0
   194  	{-1e9, 0, "0"},                    // range includes 0
   195  	{-1e9, 1e9, "0"},                  // range includes 0
   196  	{-10, -1, "3628800"},              // 10!
   197  	{-20, -2, "-2432902008176640000"}, // -20!
   198  	{-99, -1,
   199  		"-933262154439441526816992388562667004907159682643816214685929" +
   200  			"638952175999932299156089414639761565182862536979208272237582" +
   201  			"511852109168640000000000000000000000", // -99!
   202  	},
   203  
   204  	// overflow situations
   205  	{math.MaxInt64 - 0, math.MaxInt64, "9223372036854775807"},
   206  	{math.MaxInt64 - 1, math.MaxInt64, "85070591730234615838173535747377725442"},
   207  	{math.MaxInt64 - 2, math.MaxInt64, "784637716923335094969050127519550606919189611815754530810"},
   208  	{math.MaxInt64 - 3, math.MaxInt64, "7237005577332262206126809393809643289012107973151163787181513908099760521240"},
   209  }
   210  
   211  func TestMulRangeZ(t *testing.T) {
   212  	var tmp Int
   213  	// test entirely positive ranges
   214  	for i, r := range mulRangesN {
   215  		// skip mulRangesN entries that overflow int64
   216  		if int64(r.a) < 0 || int64(r.b) < 0 {
   217  			continue
   218  		}
   219  		prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
   220  		if prod != r.prod {
   221  			t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
   222  		}
   223  	}
   224  	// test other ranges
   225  	for i, r := range mulRangesZ {
   226  		prod := tmp.MulRange(r.a, r.b).String()
   227  		if prod != r.prod {
   228  			t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
   229  		}
   230  	}
   231  }
   232  
   233  func TestBinomial(t *testing.T) {
   234  	var z Int
   235  	for _, test := range []struct {
   236  		n, k int64
   237  		want string
   238  	}{
   239  		{0, 0, "1"},
   240  		{0, 1, "0"},
   241  		{1, 0, "1"},
   242  		{1, 1, "1"},
   243  		{1, 10, "0"},
   244  		{4, 0, "1"},
   245  		{4, 1, "4"},
   246  		{4, 2, "6"},
   247  		{4, 3, "4"},
   248  		{4, 4, "1"},
   249  		{10, 1, "10"},
   250  		{10, 9, "10"},
   251  		{10, 5, "252"},
   252  		{11, 5, "462"},
   253  		{11, 6, "462"},
   254  		{100, 10, "17310309456440"},
   255  		{100, 90, "17310309456440"},
   256  		{1000, 10, "263409560461970212832400"},
   257  		{1000, 990, "263409560461970212832400"},
   258  	} {
   259  		if got := z.Binomial(test.n, test.k).String(); got != test.want {
   260  			t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
   261  		}
   262  	}
   263  }
   264  
   265  func BenchmarkBinomial(b *testing.B) {
   266  	var z Int
   267  	for i := 0; i < b.N; i++ {
   268  		z.Binomial(1000, 990)
   269  	}
   270  }
   271  
   272  // Examples from the Go Language Spec, section "Arithmetic operators"
   273  var divisionSignsTests = []struct {
   274  	x, y int64
   275  	q, r int64 // T-division
   276  	d, m int64 // Euclidean division
   277  }{
   278  	{5, 3, 1, 2, 1, 2},
   279  	{-5, 3, -1, -2, -2, 1},
   280  	{5, -3, -1, 2, -1, 2},
   281  	{-5, -3, 1, -2, 2, 1},
   282  	{1, 2, 0, 1, 0, 1},
   283  	{8, 4, 2, 0, 2, 0},
   284  }
   285  
   286  func TestDivisionSigns(t *testing.T) {
   287  	for i, test := range divisionSignsTests {
   288  		x := NewInt(test.x)
   289  		y := NewInt(test.y)
   290  		q := NewInt(test.q)
   291  		r := NewInt(test.r)
   292  		d := NewInt(test.d)
   293  		m := NewInt(test.m)
   294  
   295  		q1 := new(Int).Quo(x, y)
   296  		r1 := new(Int).Rem(x, y)
   297  		if !isNormalized(q1) {
   298  			t.Errorf("#%d Quo: %v is not normalized", i, *q1)
   299  		}
   300  		if !isNormalized(r1) {
   301  			t.Errorf("#%d Rem: %v is not normalized", i, *r1)
   302  		}
   303  		if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
   304  			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
   305  		}
   306  
   307  		q2, r2 := new(Int).QuoRem(x, y, new(Int))
   308  		if !isNormalized(q2) {
   309  			t.Errorf("#%d Quo: %v is not normalized", i, *q2)
   310  		}
   311  		if !isNormalized(r2) {
   312  			t.Errorf("#%d Rem: %v is not normalized", i, *r2)
   313  		}
   314  		if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
   315  			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
   316  		}
   317  
   318  		d1 := new(Int).Div(x, y)
   319  		m1 := new(Int).Mod(x, y)
   320  		if !isNormalized(d1) {
   321  			t.Errorf("#%d Div: %v is not normalized", i, *d1)
   322  		}
   323  		if !isNormalized(m1) {
   324  			t.Errorf("#%d Mod: %v is not normalized", i, *m1)
   325  		}
   326  		if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
   327  			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
   328  		}
   329  
   330  		d2, m2 := new(Int).DivMod(x, y, new(Int))
   331  		if !isNormalized(d2) {
   332  			t.Errorf("#%d Div: %v is not normalized", i, *d2)
   333  		}
   334  		if !isNormalized(m2) {
   335  			t.Errorf("#%d Mod: %v is not normalized", i, *m2)
   336  		}
   337  		if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
   338  			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
   339  		}
   340  	}
   341  }
   342  
   343  func norm(x nat) nat {
   344  	i := len(x)
   345  	for i > 0 && x[i-1] == 0 {
   346  		i--
   347  	}
   348  	return x[:i]
   349  }
   350  
   351  func TestBits(t *testing.T) {
   352  	for _, test := range []nat{
   353  		nil,
   354  		{0},
   355  		{1},
   356  		{0, 1, 2, 3, 4},
   357  		{4, 3, 2, 1, 0},
   358  		{4, 3, 2, 1, 0, 0, 0, 0},
   359  	} {
   360  		var z Int
   361  		z.neg = true
   362  		got := z.SetBits(test)
   363  		want := norm(test)
   364  		if got.abs.cmp(want) != 0 {
   365  			t.Errorf("SetBits(%v) = %v; want %v", test, got.abs, want)
   366  		}
   367  
   368  		if got.neg {
   369  			t.Errorf("SetBits(%v): got negative result", test)
   370  		}
   371  
   372  		bits := nat(z.Bits())
   373  		if bits.cmp(want) != 0 {
   374  			t.Errorf("%v.Bits() = %v; want %v", z.abs, bits, want)
   375  		}
   376  	}
   377  }
   378  
   379  func checkSetBytes(b []byte) bool {
   380  	hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
   381  	hex2 := hex.EncodeToString(b)
   382  
   383  	for len(hex1) < len(hex2) {
   384  		hex1 = "0" + hex1
   385  	}
   386  
   387  	for len(hex1) > len(hex2) {
   388  		hex2 = "0" + hex2
   389  	}
   390  
   391  	return hex1 == hex2
   392  }
   393  
   394  func TestSetBytes(t *testing.T) {
   395  	if err := quick.Check(checkSetBytes, nil); err != nil {
   396  		t.Error(err)
   397  	}
   398  }
   399  
   400  func checkBytes(b []byte) bool {
   401  	// trim leading zero bytes since Bytes() won't return them
   402  	// (was issue 12231)
   403  	for len(b) > 0 && b[0] == 0 {
   404  		b = b[1:]
   405  	}
   406  	b2 := new(Int).SetBytes(b).Bytes()
   407  	return bytes.Equal(b, b2)
   408  }
   409  
   410  func TestBytes(t *testing.T) {
   411  	if err := quick.Check(checkBytes, nil); err != nil {
   412  		t.Error(err)
   413  	}
   414  }
   415  
   416  func checkQuo(x, y []byte) bool {
   417  	u := new(Int).SetBytes(x)
   418  	v := new(Int).SetBytes(y)
   419  
   420  	if len(v.abs) == 0 {
   421  		return true
   422  	}
   423  
   424  	r := new(Int)
   425  	q, r := new(Int).QuoRem(u, v, r)
   426  
   427  	if r.Cmp(v) >= 0 {
   428  		return false
   429  	}
   430  
   431  	uprime := new(Int).Set(q)
   432  	uprime.Mul(uprime, v)
   433  	uprime.Add(uprime, r)
   434  
   435  	return uprime.Cmp(u) == 0
   436  }
   437  
   438  var quoTests = []struct {
   439  	x, y string
   440  	q, r string
   441  }{
   442  	{
   443  		"476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
   444  		"9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
   445  		"50911",
   446  		"1",
   447  	},
   448  	{
   449  		"11510768301994997771168",
   450  		"1328165573307167369775",
   451  		"8",
   452  		"885443715537658812968",
   453  	},
   454  }
   455  
   456  func TestQuo(t *testing.T) {
   457  	if err := quick.Check(checkQuo, nil); err != nil {
   458  		t.Error(err)
   459  	}
   460  
   461  	for i, test := range quoTests {
   462  		x, _ := new(Int).SetString(test.x, 10)
   463  		y, _ := new(Int).SetString(test.y, 10)
   464  		expectedQ, _ := new(Int).SetString(test.q, 10)
   465  		expectedR, _ := new(Int).SetString(test.r, 10)
   466  
   467  		r := new(Int)
   468  		q, r := new(Int).QuoRem(x, y, r)
   469  
   470  		if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
   471  			t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
   472  		}
   473  	}
   474  }
   475  
   476  func TestQuoStepD6(t *testing.T) {
   477  	// See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
   478  	// a code path which only triggers 1 in 10^{-19} cases.
   479  
   480  	u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
   481  	v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
   482  
   483  	r := new(Int)
   484  	q, r := new(Int).QuoRem(u, v, r)
   485  	const expectedQ64 = "18446744073709551613"
   486  	const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
   487  	const expectedQ32 = "4294967293"
   488  	const expectedR32 = "39614081266355540837921718287"
   489  	if q.String() != expectedQ64 && q.String() != expectedQ32 ||
   490  		r.String() != expectedR64 && r.String() != expectedR32 {
   491  		t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
   492  	}
   493  }
   494  
   495  func BenchmarkQuoRem(b *testing.B) {
   496  	x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
   497  	y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
   498  	q := new(Int)
   499  	r := new(Int)
   500  
   501  	b.ResetTimer()
   502  	for i := 0; i < b.N; i++ {
   503  		q.QuoRem(y, x, r)
   504  	}
   505  }
   506  
   507  var bitLenTests = []struct {
   508  	in  string
   509  	out int
   510  }{
   511  	{"-1", 1},
   512  	{"0", 0},
   513  	{"1", 1},
   514  	{"2", 2},
   515  	{"4", 3},
   516  	{"0xabc", 12},
   517  	{"0x8000", 16},
   518  	{"0x80000000", 32},
   519  	{"0x800000000000", 48},
   520  	{"0x8000000000000000", 64},
   521  	{"0x80000000000000000000", 80},
   522  	{"-0x4000000000000000000000", 87},
   523  }
   524  
   525  func TestBitLen(t *testing.T) {
   526  	for i, test := range bitLenTests {
   527  		x, ok := new(Int).SetString(test.in, 0)
   528  		if !ok {
   529  			t.Errorf("#%d test input invalid: %s", i, test.in)
   530  			continue
   531  		}
   532  
   533  		if n := x.BitLen(); n != test.out {
   534  			t.Errorf("#%d got %d want %d", i, n, test.out)
   535  		}
   536  	}
   537  }
   538  
   539  var expTests = []struct {
   540  	x, y, m string
   541  	out     string
   542  }{
   543  	// y <= 0
   544  	{"0", "0", "", "1"},
   545  	{"1", "0", "", "1"},
   546  	{"-10", "0", "", "1"},
   547  	{"1234", "-1", "", "1"},
   548  	{"1234", "-1", "0", "1"},
   549  	{"17", "-100", "1234", "865"},
   550  	{"2", "-100", "1234", ""},
   551  
   552  	// m == 1
   553  	{"0", "0", "1", "0"},
   554  	{"1", "0", "1", "0"},
   555  	{"-10", "0", "1", "0"},
   556  	{"1234", "-1", "1", "0"},
   557  
   558  	// misc
   559  	{"5", "1", "3", "2"},
   560  	{"5", "-7", "", "1"},
   561  	{"-5", "-7", "", "1"},
   562  	{"5", "0", "", "1"},
   563  	{"-5", "0", "", "1"},
   564  	{"5", "1", "", "5"},
   565  	{"-5", "1", "", "-5"},
   566  	{"-5", "1", "7", "2"},
   567  	{"-2", "3", "2", "0"},
   568  	{"5", "2", "", "25"},
   569  	{"1", "65537", "2", "1"},
   570  	{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
   571  	{"0x8000000000000000", "2", "6719", "4944"},
   572  	{"0x8000000000000000", "3", "6719", "5447"},
   573  	{"0x8000000000000000", "1000", "6719", "1603"},
   574  	{"0x8000000000000000", "1000000", "6719", "3199"},
   575  	{"0x8000000000000000", "-1000000", "6719", "3663"}, // 3663 = ModInverse(3199, 6719) Issue #25865
   576  
   577  	{"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
   578  
   579  	{
   580  		"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
   581  		"298472983472983471903246121093472394872319615612417471234712061",
   582  		"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
   583  		"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
   584  	},
   585  	// test case for issue 8822
   586  	{
   587  		"11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
   588  		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
   589  		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
   590  		"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
   591  	},
   592  	{
   593  		"-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
   594  		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
   595  		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
   596  		"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
   597  	},
   598  
   599  	// test cases for issue 13907
   600  	{"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
   601  	{"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
   602  	{"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
   603  	{"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
   604  
   605  	{
   606  		"2",
   607  		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
   608  		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", // odd
   609  		"0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
   610  	},
   611  	{
   612  		"2",
   613  		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
   614  		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", // even
   615  		"0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
   616  	},
   617  }
   618  
   619  func TestExp(t *testing.T) {
   620  	for i, test := range expTests {
   621  		x, ok1 := new(Int).SetString(test.x, 0)
   622  		y, ok2 := new(Int).SetString(test.y, 0)
   623  
   624  		var ok3, ok4 bool
   625  		var out, m *Int
   626  
   627  		if len(test.out) == 0 {
   628  			out, ok3 = nil, true
   629  		} else {
   630  			out, ok3 = new(Int).SetString(test.out, 0)
   631  		}
   632  
   633  		if len(test.m) == 0 {
   634  			m, ok4 = nil, true
   635  		} else {
   636  			m, ok4 = new(Int).SetString(test.m, 0)
   637  		}
   638  
   639  		if !ok1 || !ok2 || !ok3 || !ok4 {
   640  			t.Errorf("#%d: error in input", i)
   641  			continue
   642  		}
   643  
   644  		z1 := new(Int).Exp(x, y, m)
   645  		if z1 != nil && !isNormalized(z1) {
   646  			t.Errorf("#%d: %v is not normalized", i, *z1)
   647  		}
   648  		if !(z1 == nil && out == nil || z1.Cmp(out) == 0) {
   649  			t.Errorf("#%d: got %x want %x", i, z1, out)
   650  		}
   651  
   652  		if m == nil {
   653  			// The result should be the same as for m == 0;
   654  			// specifically, there should be no div-zero panic.
   655  			m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
   656  			z2 := new(Int).Exp(x, y, m)
   657  			if z2.Cmp(z1) != 0 {
   658  				t.Errorf("#%d: got %x want %x", i, z2, z1)
   659  			}
   660  		}
   661  	}
   662  }
   663  
   664  func BenchmarkExp(b *testing.B) {
   665  	x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
   666  	y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
   667  	n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
   668  	out := new(Int)
   669  	for i := 0; i < b.N; i++ {
   670  		out.Exp(x, y, n)
   671  	}
   672  }
   673  
   674  func BenchmarkExpMont(b *testing.B) {
   675  	x, _ := new(Int).SetString("297778224889315382157302278696111964193", 0)
   676  	y, _ := new(Int).SetString("2548977943381019743024248146923164919440527843026415174732254534318292492375775985739511369575861449426580651447974311336267954477239437734832604782764979371984246675241012538135715981292390886872929238062252506842498360562303324154310849745753254532852868768268023732398278338025070694508489163836616810661033068070127919590264734220833816416141878688318329193389865030063416339367925710474801991305827284114894677717927892032165200876093838921477120036402410731159852999623461591709308405270748511350289172153076023215", 0)
   677  	var mods = []struct {
   678  		name string
   679  		val  string
   680  	}{
   681  		{"Odd", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF"},
   682  		{"Even1", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FE"},
   683  		{"Even2", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FC"},
   684  		{"Even3", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F8"},
   685  		{"Even4", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F0"},
   686  		{"Even8", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B21828100"},
   687  		{"Even32", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B00000000"},
   688  		{"Even64", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FF0000000000000000"},
   689  		{"Even96", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828283000000000000000000000000"},
   690  		{"Even128", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF00000000000000000000000000000000"},
   691  		{"Even255", "0x82828282828200FFFF28FF2B218281FF8000000000000000000000000000000000000000000000000000000000000000"},
   692  		{"SmallEven1", "0x7E"},
   693  		{"SmallEven2", "0x7C"},
   694  		{"SmallEven3", "0x78"},
   695  		{"SmallEven4", "0x70"},
   696  	}
   697  	for _, mod := range mods {
   698  		n, _ := new(Int).SetString(mod.val, 0)
   699  		out := new(Int)
   700  		b.Run(mod.name, func(b *testing.B) {
   701  			b.ReportAllocs()
   702  			for i := 0; i < b.N; i++ {
   703  				out.Exp(x, y, n)
   704  			}
   705  		})
   706  	}
   707  }
   708  
   709  func BenchmarkExp2(b *testing.B) {
   710  	x, _ := new(Int).SetString("2", 0)
   711  	y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
   712  	n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
   713  	out := new(Int)
   714  	for i := 0; i < b.N; i++ {
   715  		out.Exp(x, y, n)
   716  	}
   717  }
   718  
   719  func checkGcd(aBytes, bBytes []byte) bool {
   720  	x := new(Int)
   721  	y := new(Int)
   722  	a := new(Int).SetBytes(aBytes)
   723  	b := new(Int).SetBytes(bBytes)
   724  
   725  	d := new(Int).GCD(x, y, a, b)
   726  	x.Mul(x, a)
   727  	y.Mul(y, b)
   728  	x.Add(x, y)
   729  
   730  	return x.Cmp(d) == 0
   731  }
   732  
   733  // euclidExtGCD is a reference implementation of Euclid's
   734  // extended GCD algorithm for testing against optimized algorithms.
   735  // Requirements: a, b > 0
   736  func euclidExtGCD(a, b *Int) (g, x, y *Int) {
   737  	A := new(Int).Set(a)
   738  	B := new(Int).Set(b)
   739  
   740  	// A = Ua*a + Va*b
   741  	// B = Ub*a + Vb*b
   742  	Ua := new(Int).SetInt64(1)
   743  	Va := new(Int)
   744  
   745  	Ub := new(Int)
   746  	Vb := new(Int).SetInt64(1)
   747  
   748  	q := new(Int)
   749  	temp := new(Int)
   750  
   751  	r := new(Int)
   752  	for len(B.abs) > 0 {
   753  		q, r = q.QuoRem(A, B, r)
   754  
   755  		A, B, r = B, r, A
   756  
   757  		// Ua, Ub = Ub, Ua-q*Ub
   758  		temp.Set(Ub)
   759  		Ub.Mul(Ub, q)
   760  		Ub.Sub(Ua, Ub)
   761  		Ua.Set(temp)
   762  
   763  		// Va, Vb = Vb, Va-q*Vb
   764  		temp.Set(Vb)
   765  		Vb.Mul(Vb, q)
   766  		Vb.Sub(Va, Vb)
   767  		Va.Set(temp)
   768  	}
   769  	return A, Ua, Va
   770  }
   771  
   772  func checkLehmerGcd(aBytes, bBytes []byte) bool {
   773  	a := new(Int).SetBytes(aBytes)
   774  	b := new(Int).SetBytes(bBytes)
   775  
   776  	if a.Sign() <= 0 || b.Sign() <= 0 {
   777  		return true // can only test positive arguments
   778  	}
   779  
   780  	d := new(Int).lehmerGCD(nil, nil, a, b)
   781  	d0, _, _ := euclidExtGCD(a, b)
   782  
   783  	return d.Cmp(d0) == 0
   784  }
   785  
   786  func checkLehmerExtGcd(aBytes, bBytes []byte) bool {
   787  	a := new(Int).SetBytes(aBytes)
   788  	b := new(Int).SetBytes(bBytes)
   789  	x := new(Int)
   790  	y := new(Int)
   791  
   792  	if a.Sign() <= 0 || b.Sign() <= 0 {
   793  		return true // can only test positive arguments
   794  	}
   795  
   796  	d := new(Int).lehmerGCD(x, y, a, b)
   797  	d0, x0, y0 := euclidExtGCD(a, b)
   798  
   799  	return d.Cmp(d0) == 0 && x.Cmp(x0) == 0 && y.Cmp(y0) == 0
   800  }
   801  
   802  var gcdTests = []struct {
   803  	d, x, y, a, b string
   804  }{
   805  	// a <= 0 || b <= 0
   806  	{"0", "0", "0", "0", "0"},
   807  	{"7", "0", "1", "0", "7"},
   808  	{"7", "0", "-1", "0", "-7"},
   809  	{"11", "1", "0", "11", "0"},
   810  	{"7", "-1", "-2", "-77", "35"},
   811  	{"935", "-3", "8", "64515", "24310"},
   812  	{"935", "-3", "-8", "64515", "-24310"},
   813  	{"935", "3", "-8", "-64515", "-24310"},
   814  
   815  	{"1", "-9", "47", "120", "23"},
   816  	{"7", "1", "-2", "77", "35"},
   817  	{"935", "-3", "8", "64515", "24310"},
   818  	{"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
   819  	{"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
   820  }
   821  
   822  func testGcd(t *testing.T, d, x, y, a, b *Int) {
   823  	var X *Int
   824  	if x != nil {
   825  		X = new(Int)
   826  	}
   827  	var Y *Int
   828  	if y != nil {
   829  		Y = new(Int)
   830  	}
   831  
   832  	D := new(Int).GCD(X, Y, a, b)
   833  	if D.Cmp(d) != 0 {
   834  		t.Errorf("GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
   835  	}
   836  	if x != nil && X.Cmp(x) != 0 {
   837  		t.Errorf("GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
   838  	}
   839  	if y != nil && Y.Cmp(y) != 0 {
   840  		t.Errorf("GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
   841  	}
   842  
   843  	// check results in presence of aliasing (issue #11284)
   844  	a2 := new(Int).Set(a)
   845  	b2 := new(Int).Set(b)
   846  	a2.GCD(X, Y, a2, b2) // result is same as 1st argument
   847  	if a2.Cmp(d) != 0 {
   848  		t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, a2, d)
   849  	}
   850  	if x != nil && X.Cmp(x) != 0 {
   851  		t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
   852  	}
   853  	if y != nil && Y.Cmp(y) != 0 {
   854  		t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
   855  	}
   856  
   857  	a2 = new(Int).Set(a)
   858  	b2 = new(Int).Set(b)
   859  	b2.GCD(X, Y, a2, b2) // result is same as 2nd argument
   860  	if b2.Cmp(d) != 0 {
   861  		t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, b2, d)
   862  	}
   863  	if x != nil && X.Cmp(x) != 0 {
   864  		t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
   865  	}
   866  	if y != nil && Y.Cmp(y) != 0 {
   867  		t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
   868  	}
   869  
   870  	a2 = new(Int).Set(a)
   871  	b2 = new(Int).Set(b)
   872  	D = new(Int).GCD(a2, b2, a2, b2) // x = a, y = b
   873  	if D.Cmp(d) != 0 {
   874  		t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
   875  	}
   876  	if x != nil && a2.Cmp(x) != 0 {
   877  		t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, a2, x)
   878  	}
   879  	if y != nil && b2.Cmp(y) != 0 {
   880  		t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, b2, y)
   881  	}
   882  
   883  	a2 = new(Int).Set(a)
   884  	b2 = new(Int).Set(b)
   885  	D = new(Int).GCD(b2, a2, a2, b2) // x = b, y = a
   886  	if D.Cmp(d) != 0 {
   887  		t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
   888  	}
   889  	if x != nil && b2.Cmp(x) != 0 {
   890  		t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, b2, x)
   891  	}
   892  	if y != nil && a2.Cmp(y) != 0 {
   893  		t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, a2, y)
   894  	}
   895  }
   896  
   897  func TestGcd(t *testing.T) {
   898  	for _, test := range gcdTests {
   899  		d, _ := new(Int).SetString(test.d, 0)
   900  		x, _ := new(Int).SetString(test.x, 0)
   901  		y, _ := new(Int).SetString(test.y, 0)
   902  		a, _ := new(Int).SetString(test.a, 0)
   903  		b, _ := new(Int).SetString(test.b, 0)
   904  
   905  		testGcd(t, d, nil, nil, a, b)
   906  		testGcd(t, d, x, nil, a, b)
   907  		testGcd(t, d, nil, y, a, b)
   908  		testGcd(t, d, x, y, a, b)
   909  	}
   910  
   911  	if err := quick.Check(checkGcd, nil); err != nil {
   912  		t.Error(err)
   913  	}
   914  
   915  	if err := quick.Check(checkLehmerGcd, nil); err != nil {
   916  		t.Error(err)
   917  	}
   918  
   919  	if err := quick.Check(checkLehmerExtGcd, nil); err != nil {
   920  		t.Error(err)
   921  	}
   922  }
   923  
   924  type intShiftTest struct {
   925  	in    string
   926  	shift uint
   927  	out   string
   928  }
   929  
   930  var rshTests = []intShiftTest{
   931  	{"0", 0, "0"},
   932  	{"-0", 0, "0"},
   933  	{"0", 1, "0"},
   934  	{"0", 2, "0"},
   935  	{"1", 0, "1"},
   936  	{"1", 1, "0"},
   937  	{"1", 2, "0"},
   938  	{"2", 0, "2"},
   939  	{"2", 1, "1"},
   940  	{"-1", 0, "-1"},
   941  	{"-1", 1, "-1"},
   942  	{"-1", 10, "-1"},
   943  	{"-100", 2, "-25"},
   944  	{"-100", 3, "-13"},
   945  	{"-100", 100, "-1"},
   946  	{"4294967296", 0, "4294967296"},
   947  	{"4294967296", 1, "2147483648"},
   948  	{"4294967296", 2, "1073741824"},
   949  	{"18446744073709551616", 0, "18446744073709551616"},
   950  	{"18446744073709551616", 1, "9223372036854775808"},
   951  	{"18446744073709551616", 2, "4611686018427387904"},
   952  	{"18446744073709551616", 64, "1"},
   953  	{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
   954  	{"340282366920938463463374607431768211456", 128, "1"},
   955  }
   956  
   957  func TestRsh(t *testing.T) {
   958  	for i, test := range rshTests {
   959  		in, _ := new(Int).SetString(test.in, 10)
   960  		expected, _ := new(Int).SetString(test.out, 10)
   961  		out := new(Int).Rsh(in, test.shift)
   962  
   963  		if !isNormalized(out) {
   964  			t.Errorf("#%d: %v is not normalized", i, *out)
   965  		}
   966  		if out.Cmp(expected) != 0 {
   967  			t.Errorf("#%d: got %s want %s", i, out, expected)
   968  		}
   969  	}
   970  }
   971  
   972  func TestRshSelf(t *testing.T) {
   973  	for i, test := range rshTests {
   974  		z, _ := new(Int).SetString(test.in, 10)
   975  		expected, _ := new(Int).SetString(test.out, 10)
   976  		z.Rsh(z, test.shift)
   977  
   978  		if !isNormalized(z) {
   979  			t.Errorf("#%d: %v is not normalized", i, *z)
   980  		}
   981  		if z.Cmp(expected) != 0 {
   982  			t.Errorf("#%d: got %s want %s", i, z, expected)
   983  		}
   984  	}
   985  }
   986  
   987  var lshTests = []intShiftTest{
   988  	{"0", 0, "0"},
   989  	{"0", 1, "0"},
   990  	{"0", 2, "0"},
   991  	{"1", 0, "1"},
   992  	{"1", 1, "2"},
   993  	{"1", 2, "4"},
   994  	{"2", 0, "2"},
   995  	{"2", 1, "4"},
   996  	{"2", 2, "8"},
   997  	{"-87", 1, "-174"},
   998  	{"4294967296", 0, "4294967296"},
   999  	{"4294967296", 1, "8589934592"},
  1000  	{"4294967296", 2, "17179869184"},
  1001  	{"18446744073709551616", 0, "18446744073709551616"},
  1002  	{"9223372036854775808", 1, "18446744073709551616"},
  1003  	{"4611686018427387904", 2, "18446744073709551616"},
  1004  	{"1", 64, "18446744073709551616"},
  1005  	{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
  1006  	{"1", 128, "340282366920938463463374607431768211456"},
  1007  }
  1008  
  1009  func TestLsh(t *testing.T) {
  1010  	for i, test := range lshTests {
  1011  		in, _ := new(Int).SetString(test.in, 10)
  1012  		expected, _ := new(Int).SetString(test.out, 10)
  1013  		out := new(Int).Lsh(in, test.shift)
  1014  
  1015  		if !isNormalized(out) {
  1016  			t.Errorf("#%d: %v is not normalized", i, *out)
  1017  		}
  1018  		if out.Cmp(expected) != 0 {
  1019  			t.Errorf("#%d: got %s want %s", i, out, expected)
  1020  		}
  1021  	}
  1022  }
  1023  
  1024  func TestLshSelf(t *testing.T) {
  1025  	for i, test := range lshTests {
  1026  		z, _ := new(Int).SetString(test.in, 10)
  1027  		expected, _ := new(Int).SetString(test.out, 10)
  1028  		z.Lsh(z, test.shift)
  1029  
  1030  		if !isNormalized(z) {
  1031  			t.Errorf("#%d: %v is not normalized", i, *z)
  1032  		}
  1033  		if z.Cmp(expected) != 0 {
  1034  			t.Errorf("#%d: got %s want %s", i, z, expected)
  1035  		}
  1036  	}
  1037  }
  1038  
  1039  func TestLshRsh(t *testing.T) {
  1040  	for i, test := range rshTests {
  1041  		in, _ := new(Int).SetString(test.in, 10)
  1042  		out := new(Int).Lsh(in, test.shift)
  1043  		out = out.Rsh(out, test.shift)
  1044  
  1045  		if !isNormalized(out) {
  1046  			t.Errorf("#%d: %v is not normalized", i, *out)
  1047  		}
  1048  		if in.Cmp(out) != 0 {
  1049  			t.Errorf("#%d: got %s want %s", i, out, in)
  1050  		}
  1051  	}
  1052  	for i, test := range lshTests {
  1053  		in, _ := new(Int).SetString(test.in, 10)
  1054  		out := new(Int).Lsh(in, test.shift)
  1055  		out.Rsh(out, test.shift)
  1056  
  1057  		if !isNormalized(out) {
  1058  			t.Errorf("#%d: %v is not normalized", i, *out)
  1059  		}
  1060  		if in.Cmp(out) != 0 {
  1061  			t.Errorf("#%d: got %s want %s", i, out, in)
  1062  		}
  1063  	}
  1064  }
  1065  
  1066  // Entries must be sorted by value in ascending order.
  1067  var cmpAbsTests = []string{
  1068  	"0",
  1069  	"1",
  1070  	"2",
  1071  	"10",
  1072  	"10000000",
  1073  	"2783678367462374683678456387645876387564783686583485",
  1074  	"2783678367462374683678456387645876387564783686583486",
  1075  	"32957394867987420967976567076075976570670947609750670956097509670576075067076027578341538",
  1076  }
  1077  
  1078  func TestCmpAbs(t *testing.T) {
  1079  	values := make([]*Int, len(cmpAbsTests))
  1080  	var prev *Int
  1081  	for i, s := range cmpAbsTests {
  1082  		x, ok := new(Int).SetString(s, 0)
  1083  		if !ok {
  1084  			t.Fatalf("SetString(%s, 0) failed", s)
  1085  		}
  1086  		if prev != nil && prev.Cmp(x) >= 0 {
  1087  			t.Fatal("cmpAbsTests entries not sorted in ascending order")
  1088  		}
  1089  		values[i] = x
  1090  		prev = x
  1091  	}
  1092  
  1093  	for i, x := range values {
  1094  		for j, y := range values {
  1095  			// try all combinations of signs for x, y
  1096  			for k := 0; k < 4; k++ {
  1097  				var a, b Int
  1098  				a.Set(x)
  1099  				b.Set(y)
  1100  				if k&1 != 0 {
  1101  					a.Neg(&a)
  1102  				}
  1103  				if k&2 != 0 {
  1104  					b.Neg(&b)
  1105  				}
  1106  
  1107  				got := a.CmpAbs(&b)
  1108  				want := 0
  1109  				switch {
  1110  				case i > j:
  1111  					want = 1
  1112  				case i < j:
  1113  					want = -1
  1114  				}
  1115  				if got != want {
  1116  					t.Errorf("absCmp |%s|, |%s|: got %d; want %d", &a, &b, got, want)
  1117  				}
  1118  			}
  1119  		}
  1120  	}
  1121  }
  1122  
  1123  func TestIntCmpSelf(t *testing.T) {
  1124  	for _, s := range cmpAbsTests {
  1125  		x, ok := new(Int).SetString(s, 0)
  1126  		if !ok {
  1127  			t.Fatalf("SetString(%s, 0) failed", s)
  1128  		}
  1129  		got := x.Cmp(x)
  1130  		want := 0
  1131  		if got != want {
  1132  			t.Errorf("x = %s: x.Cmp(x): got %d; want %d", x, got, want)
  1133  		}
  1134  	}
  1135  }
  1136  
  1137  var int64Tests = []string{
  1138  	// int64
  1139  	"0",
  1140  	"1",
  1141  	"-1",
  1142  	"4294967295",
  1143  	"-4294967295",
  1144  	"4294967296",
  1145  	"-4294967296",
  1146  	"9223372036854775807",
  1147  	"-9223372036854775807",
  1148  	"-9223372036854775808",
  1149  
  1150  	// not int64
  1151  	"0x8000000000000000",
  1152  	"-0x8000000000000001",
  1153  	"38579843757496759476987459679745",
  1154  	"-38579843757496759476987459679745",
  1155  }
  1156  
  1157  func TestInt64(t *testing.T) {
  1158  	for _, s := range int64Tests {
  1159  		var x Int
  1160  		_, ok := x.SetString(s, 0)
  1161  		if !ok {
  1162  			t.Errorf("SetString(%s, 0) failed", s)
  1163  			continue
  1164  		}
  1165  
  1166  		want, err := strconv.ParseInt(s, 0, 64)
  1167  		if err != nil {
  1168  			if err.(*strconv.NumError).Err == strconv.ErrRange {
  1169  				if x.IsInt64() {
  1170  					t.Errorf("IsInt64(%s) succeeded unexpectedly", s)
  1171  				}
  1172  			} else {
  1173  				t.Errorf("ParseInt(%s) failed", s)
  1174  			}
  1175  			continue
  1176  		}
  1177  
  1178  		if !x.IsInt64() {
  1179  			t.Errorf("IsInt64(%s) failed unexpectedly", s)
  1180  		}
  1181  
  1182  		got := x.Int64()
  1183  		if got != want {
  1184  			t.Errorf("Int64(%s) = %d; want %d", s, got, want)
  1185  		}
  1186  	}
  1187  }
  1188  
  1189  var uint64Tests = []string{
  1190  	// uint64
  1191  	"0",
  1192  	"1",
  1193  	"4294967295",
  1194  	"4294967296",
  1195  	"8589934591",
  1196  	"8589934592",
  1197  	"9223372036854775807",
  1198  	"9223372036854775808",
  1199  	"0x08000000000000000",
  1200  
  1201  	// not uint64
  1202  	"0x10000000000000000",
  1203  	"-0x08000000000000000",
  1204  	"-1",
  1205  }
  1206  
  1207  func TestUint64(t *testing.T) {
  1208  	for _, s := range uint64Tests {
  1209  		var x Int
  1210  		_, ok := x.SetString(s, 0)
  1211  		if !ok {
  1212  			t.Errorf("SetString(%s, 0) failed", s)
  1213  			continue
  1214  		}
  1215  
  1216  		want, err := strconv.ParseUint(s, 0, 64)
  1217  		if err != nil {
  1218  			// check for sign explicitly (ErrRange doesn't cover signed input)
  1219  			if s[0] == '-' || err.(*strconv.NumError).Err == strconv.ErrRange {
  1220  				if x.IsUint64() {
  1221  					t.Errorf("IsUint64(%s) succeeded unexpectedly", s)
  1222  				}
  1223  			} else {
  1224  				t.Errorf("ParseUint(%s) failed", s)
  1225  			}
  1226  			continue
  1227  		}
  1228  
  1229  		if !x.IsUint64() {
  1230  			t.Errorf("IsUint64(%s) failed unexpectedly", s)
  1231  		}
  1232  
  1233  		got := x.Uint64()
  1234  		if got != want {
  1235  			t.Errorf("Uint64(%s) = %d; want %d", s, got, want)
  1236  		}
  1237  	}
  1238  }
  1239  
  1240  var bitwiseTests = []struct {
  1241  	x, y                 string
  1242  	and, or, xor, andNot string
  1243  }{
  1244  	{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
  1245  	{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
  1246  	{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
  1247  	{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
  1248  	{"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
  1249  	{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
  1250  	{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
  1251  	{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
  1252  	{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
  1253  	{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
  1254  	{"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
  1255  	{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
  1256  	{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
  1257  	{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
  1258  	{
  1259  		"0x1000009dc6e3d9822cba04129bcbe3401",
  1260  		"0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
  1261  		"0x1000001186210100001000009048c2001",
  1262  		"0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
  1263  		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
  1264  		"0x8c40c2d8822caa04120b8321400",
  1265  	},
  1266  	{
  1267  		"0x1000009dc6e3d9822cba04129bcbe3401",
  1268  		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
  1269  		"0x8c40c2d8822caa04120b8321401",
  1270  		"-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
  1271  		"-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
  1272  		"0x1000001186210100001000009048c2000",
  1273  	},
  1274  	{
  1275  		"-0x1000009dc6e3d9822cba04129bcbe3401",
  1276  		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
  1277  		"-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
  1278  		"-0x1000001186210100001000009048c2001",
  1279  		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
  1280  		"0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
  1281  	},
  1282  }
  1283  
  1284  type bitFun func(z, x, y *Int) *Int
  1285  
  1286  func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
  1287  	expected := new(Int)
  1288  	expected.SetString(exp, 0)
  1289  
  1290  	out := f(new(Int), x, y)
  1291  	if out.Cmp(expected) != 0 {
  1292  		t.Errorf("%s: got %s want %s", msg, out, expected)
  1293  	}
  1294  }
  1295  
  1296  func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
  1297  	self := new(Int)
  1298  	self.Set(x)
  1299  	expected := new(Int)
  1300  	expected.SetString(exp, 0)
  1301  
  1302  	self = f(self, self, y)
  1303  	if self.Cmp(expected) != 0 {
  1304  		t.Errorf("%s: got %s want %s", msg, self, expected)
  1305  	}
  1306  }
  1307  
  1308  func altBit(x *Int, i int) uint {
  1309  	z := new(Int).Rsh(x, uint(i))
  1310  	z = z.And(z, NewInt(1))
  1311  	if z.Cmp(new(Int)) != 0 {
  1312  		return 1
  1313  	}
  1314  	return 0
  1315  }
  1316  
  1317  func altSetBit(z *Int, x *Int, i int, b uint) *Int {
  1318  	one := NewInt(1)
  1319  	m := one.Lsh(one, uint(i))
  1320  	switch b {
  1321  	case 1:
  1322  		return z.Or(x, m)
  1323  	case 0:
  1324  		return z.AndNot(x, m)
  1325  	}
  1326  	panic("set bit is not 0 or 1")
  1327  }
  1328  
  1329  func testBitset(t *testing.T, x *Int) {
  1330  	n := x.BitLen()
  1331  	z := new(Int).Set(x)
  1332  	z1 := new(Int).Set(x)
  1333  	for i := 0; i < n+10; i++ {
  1334  		old := z.Bit(i)
  1335  		old1 := altBit(z1, i)
  1336  		if old != old1 {
  1337  			t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
  1338  		}
  1339  		z := new(Int).SetBit(z, i, 1)
  1340  		z1 := altSetBit(new(Int), z1, i, 1)
  1341  		if z.Bit(i) == 0 {
  1342  			t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
  1343  		}
  1344  		if z.Cmp(z1) != 0 {
  1345  			t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
  1346  		}
  1347  		z.SetBit(z, i, 0)
  1348  		altSetBit(z1, z1, i, 0)
  1349  		if z.Bit(i) != 0 {
  1350  			t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
  1351  		}
  1352  		if z.Cmp(z1) != 0 {
  1353  			t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
  1354  		}
  1355  		altSetBit(z1, z1, i, old)
  1356  		z.SetBit(z, i, old)
  1357  		if z.Cmp(z1) != 0 {
  1358  			t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
  1359  		}
  1360  	}
  1361  	if z.Cmp(x) != 0 {
  1362  		t.Errorf("bitset: got %s want %s", z, x)
  1363  	}
  1364  }
  1365  
  1366  var bitsetTests = []struct {
  1367  	x string
  1368  	i int
  1369  	b uint
  1370  }{
  1371  	{"0", 0, 0},
  1372  	{"0", 200, 0},
  1373  	{"1", 0, 1},
  1374  	{"1", 1, 0},
  1375  	{"-1", 0, 1},
  1376  	{"-1", 200, 1},
  1377  	{"0x2000000000000000000000000000", 108, 0},
  1378  	{"0x2000000000000000000000000000", 109, 1},
  1379  	{"0x2000000000000000000000000000", 110, 0},
  1380  	{"-0x2000000000000000000000000001", 108, 1},
  1381  	{"-0x2000000000000000000000000001", 109, 0},
  1382  	{"-0x2000000000000000000000000001", 110, 1},
  1383  }
  1384  
  1385  func TestBitSet(t *testing.T) {
  1386  	for _, test := range bitwiseTests {
  1387  		x := new(Int)
  1388  		x.SetString(test.x, 0)
  1389  		testBitset(t, x)
  1390  		x = new(Int)
  1391  		x.SetString(test.y, 0)
  1392  		testBitset(t, x)
  1393  	}
  1394  	for i, test := range bitsetTests {
  1395  		x := new(Int)
  1396  		x.SetString(test.x, 0)
  1397  		b := x.Bit(test.i)
  1398  		if b != test.b {
  1399  			t.Errorf("#%d got %v want %v", i, b, test.b)
  1400  		}
  1401  	}
  1402  	z := NewInt(1)
  1403  	z.SetBit(NewInt(0), 2, 1)
  1404  	if z.Cmp(NewInt(4)) != 0 {
  1405  		t.Errorf("destination leaked into result; got %s want 4", z)
  1406  	}
  1407  }
  1408  
  1409  var tzbTests = []struct {
  1410  	in  string
  1411  	out uint
  1412  }{
  1413  	{"0", 0},
  1414  	{"1", 0},
  1415  	{"-1", 0},
  1416  	{"4", 2},
  1417  	{"-8", 3},
  1418  	{"0x4000000000000000000", 74},
  1419  	{"-0x8000000000000000000", 75},
  1420  }
  1421  
  1422  func TestTrailingZeroBits(t *testing.T) {
  1423  	for i, test := range tzbTests {
  1424  		in, _ := new(Int).SetString(test.in, 0)
  1425  		want := test.out
  1426  		got := in.TrailingZeroBits()
  1427  
  1428  		if got != want {
  1429  			t.Errorf("#%d: got %v want %v", i, got, want)
  1430  		}
  1431  	}
  1432  }
  1433  
  1434  func BenchmarkBitset(b *testing.B) {
  1435  	z := new(Int)
  1436  	z.SetBit(z, 512, 1)
  1437  	b.ResetTimer()
  1438  	for i := b.N - 1; i >= 0; i-- {
  1439  		z.SetBit(z, i&512, 1)
  1440  	}
  1441  }
  1442  
  1443  func BenchmarkBitsetNeg(b *testing.B) {
  1444  	z := NewInt(-1)
  1445  	z.SetBit(z, 512, 0)
  1446  	b.ResetTimer()
  1447  	for i := b.N - 1; i >= 0; i-- {
  1448  		z.SetBit(z, i&512, 0)
  1449  	}
  1450  }
  1451  
  1452  func BenchmarkBitsetOrig(b *testing.B) {
  1453  	z := new(Int)
  1454  	altSetBit(z, z, 512, 1)
  1455  	b.ResetTimer()
  1456  	for i := b.N - 1; i >= 0; i-- {
  1457  		altSetBit(z, z, i&512, 1)
  1458  	}
  1459  }
  1460  
  1461  func BenchmarkBitsetNegOrig(b *testing.B) {
  1462  	z := NewInt(-1)
  1463  	altSetBit(z, z, 512, 0)
  1464  	b.ResetTimer()
  1465  	for i := b.N - 1; i >= 0; i-- {
  1466  		altSetBit(z, z, i&512, 0)
  1467  	}
  1468  }
  1469  
  1470  // tri generates the trinomial 2**(n*2) - 2**n - 1, which is always 3 mod 4 and
  1471  // 7 mod 8, so that 2 is always a quadratic residue.
  1472  func tri(n uint) *Int {
  1473  	x := NewInt(1)
  1474  	x.Lsh(x, n)
  1475  	x2 := new(Int).Lsh(x, n)
  1476  	x2.Sub(x2, x)
  1477  	x2.Sub(x2, intOne)
  1478  	return x2
  1479  }
  1480  
  1481  func BenchmarkModSqrt225_Tonelli(b *testing.B) {
  1482  	p := tri(225)
  1483  	x := NewInt(2)
  1484  	for i := 0; i < b.N; i++ {
  1485  		x.SetUint64(2)
  1486  		x.modSqrtTonelliShanks(x, p)
  1487  	}
  1488  }
  1489  
  1490  func BenchmarkModSqrt225_3Mod4(b *testing.B) {
  1491  	p := tri(225)
  1492  	x := new(Int).SetUint64(2)
  1493  	for i := 0; i < b.N; i++ {
  1494  		x.SetUint64(2)
  1495  		x.modSqrt3Mod4Prime(x, p)
  1496  	}
  1497  }
  1498  
  1499  func BenchmarkModSqrt231_Tonelli(b *testing.B) {
  1500  	p := tri(231)
  1501  	p.Sub(p, intOne)
  1502  	p.Sub(p, intOne) // tri(231) - 2 is a prime == 5 mod 8
  1503  	x := new(Int).SetUint64(7)
  1504  	for i := 0; i < b.N; i++ {
  1505  		x.SetUint64(7)
  1506  		x.modSqrtTonelliShanks(x, p)
  1507  	}
  1508  }
  1509  
  1510  func BenchmarkModSqrt231_5Mod8(b *testing.B) {
  1511  	p := tri(231)
  1512  	p.Sub(p, intOne)
  1513  	p.Sub(p, intOne) // tri(231) - 2 is a prime == 5 mod 8
  1514  	x := new(Int).SetUint64(7)
  1515  	for i := 0; i < b.N; i++ {
  1516  		x.SetUint64(7)
  1517  		x.modSqrt5Mod8Prime(x, p)
  1518  	}
  1519  }
  1520  
  1521  func TestBitwise(t *testing.T) {
  1522  	x := new(Int)
  1523  	y := new(Int)
  1524  	for _, test := range bitwiseTests {
  1525  		x.SetString(test.x, 0)
  1526  		y.SetString(test.y, 0)
  1527  
  1528  		testBitFun(t, "and", (*Int).And, x, y, test.and)
  1529  		testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
  1530  		testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
  1531  		testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
  1532  		testBitFun(t, "or", (*Int).Or, x, y, test.or)
  1533  		testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
  1534  		testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
  1535  		testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
  1536  	}
  1537  }
  1538  
  1539  var notTests = []struct {
  1540  	in  string
  1541  	out string
  1542  }{
  1543  	{"0", "-1"},
  1544  	{"1", "-2"},
  1545  	{"7", "-8"},
  1546  	{"0", "-1"},
  1547  	{"-81910", "81909"},
  1548  	{
  1549  		"298472983472983471903246121093472394872319615612417471234712061",
  1550  		"-298472983472983471903246121093472394872319615612417471234712062",
  1551  	},
  1552  }
  1553  
  1554  func TestNot(t *testing.T) {
  1555  	in := new(Int)
  1556  	out := new(Int)
  1557  	expected := new(Int)
  1558  	for i, test := range notTests {
  1559  		in.SetString(test.in, 10)
  1560  		expected.SetString(test.out, 10)
  1561  		out = out.Not(in)
  1562  		if out.Cmp(expected) != 0 {
  1563  			t.Errorf("#%d: got %s want %s", i, out, expected)
  1564  		}
  1565  		out = out.Not(out)
  1566  		if out.Cmp(in) != 0 {
  1567  			t.Errorf("#%d: got %s want %s", i, out, in)
  1568  		}
  1569  	}
  1570  }
  1571  
  1572  var modInverseTests = []struct {
  1573  	element string
  1574  	modulus string
  1575  }{
  1576  	{"1234567", "458948883992"},
  1577  	{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
  1578  	{"-10", "13"}, // issue #16984
  1579  	{"10", "-13"},
  1580  	{"-17", "-13"},
  1581  }
  1582  
  1583  func TestModInverse(t *testing.T) {
  1584  	var element, modulus, gcd, inverse Int
  1585  	one := NewInt(1)
  1586  	for _, test := range modInverseTests {
  1587  		(&element).SetString(test.element, 10)
  1588  		(&modulus).SetString(test.modulus, 10)
  1589  		(&inverse).ModInverse(&element, &modulus)
  1590  		(&inverse).Mul(&inverse, &element)
  1591  		(&inverse).Mod(&inverse, &modulus)
  1592  		if (&inverse).Cmp(one) != 0 {
  1593  			t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
  1594  		}
  1595  	}
  1596  	// exhaustive test for small values
  1597  	for n := 2; n < 100; n++ {
  1598  		(&modulus).SetInt64(int64(n))
  1599  		for x := 1; x < n; x++ {
  1600  			(&element).SetInt64(int64(x))
  1601  			(&gcd).GCD(nil, nil, &element, &modulus)
  1602  			if (&gcd).Cmp(one) != 0 {
  1603  				continue
  1604  			}
  1605  			(&inverse).ModInverse(&element, &modulus)
  1606  			(&inverse).Mul(&inverse, &element)
  1607  			(&inverse).Mod(&inverse, &modulus)
  1608  			if (&inverse).Cmp(one) != 0 {
  1609  				t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
  1610  			}
  1611  		}
  1612  	}
  1613  }
  1614  
  1615  func BenchmarkModInverse(b *testing.B) {
  1616  	p := new(Int).SetInt64(1) // Mersenne prime 2**1279 -1
  1617  	p.abs = p.abs.shl(p.abs, 1279)
  1618  	p.Sub(p, intOne)
  1619  	x := new(Int).Sub(p, intOne)
  1620  	z := new(Int)
  1621  	for i := 0; i < b.N; i++ {
  1622  		z.ModInverse(x, p)
  1623  	}
  1624  }
  1625  
  1626  // testModSqrt is a helper for TestModSqrt,
  1627  // which checks that ModSqrt can compute a square-root of elt^2.
  1628  func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
  1629  	var sqChk, sqrtChk, sqrtsq Int
  1630  	sq.Mul(elt, elt)
  1631  	sq.Mod(sq, mod)
  1632  	z := sqrt.ModSqrt(sq, mod)
  1633  	if z != sqrt {
  1634  		t.Errorf("ModSqrt returned wrong value %s", z)
  1635  	}
  1636  
  1637  	// test ModSqrt arguments outside the range [0,mod)
  1638  	sqChk.Add(sq, mod)
  1639  	z = sqrtChk.ModSqrt(&sqChk, mod)
  1640  	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
  1641  		t.Errorf("ModSqrt returned inconsistent value %s", z)
  1642  	}
  1643  	sqChk.Sub(sq, mod)
  1644  	z = sqrtChk.ModSqrt(&sqChk, mod)
  1645  	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
  1646  		t.Errorf("ModSqrt returned inconsistent value %s", z)
  1647  	}
  1648  
  1649  	// test x aliasing z
  1650  	z = sqrtChk.ModSqrt(sqrtChk.Set(sq), mod)
  1651  	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
  1652  		t.Errorf("ModSqrt returned inconsistent value %s", z)
  1653  	}
  1654  
  1655  	// make sure we actually got a square root
  1656  	if sqrt.Cmp(elt) == 0 {
  1657  		return true // we found the "desired" square root
  1658  	}
  1659  	sqrtsq.Mul(sqrt, sqrt) // make sure we found the "other" one
  1660  	sqrtsq.Mod(&sqrtsq, mod)
  1661  	return sq.Cmp(&sqrtsq) == 0
  1662  }
  1663  
  1664  func TestModSqrt(t *testing.T) {
  1665  	var elt, mod, modx4, sq, sqrt Int
  1666  	r := rand.New(rand.NewSource(9))
  1667  	for i, s := range primes[1:] { // skip 2, use only odd primes
  1668  		mod.SetString(s, 10)
  1669  		modx4.Lsh(&mod, 2)
  1670  
  1671  		// test a few random elements per prime
  1672  		for x := 1; x < 5; x++ {
  1673  			elt.Rand(r, &modx4)
  1674  			elt.Sub(&elt, &mod) // test range [-mod, 3*mod)
  1675  			if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
  1676  				t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
  1677  			}
  1678  		}
  1679  
  1680  		if testing.Short() && i > 2 {
  1681  			break
  1682  		}
  1683  	}
  1684  
  1685  	if testing.Short() {
  1686  		return
  1687  	}
  1688  
  1689  	// exhaustive test for small values
  1690  	for n := 3; n < 100; n++ {
  1691  		mod.SetInt64(int64(n))
  1692  		if !mod.ProbablyPrime(10) {
  1693  			continue
  1694  		}
  1695  		isSquare := make([]bool, n)
  1696  
  1697  		// test all the squares
  1698  		for x := 1; x < n; x++ {
  1699  			elt.SetInt64(int64(x))
  1700  			if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
  1701  				t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
  1702  			}
  1703  			isSquare[sq.Uint64()] = true
  1704  		}
  1705  
  1706  		// test all non-squares
  1707  		for x := 1; x < n; x++ {
  1708  			sq.SetInt64(int64(x))
  1709  			z := sqrt.ModSqrt(&sq, &mod)
  1710  			if !isSquare[x] && z != nil {
  1711  				t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
  1712  			}
  1713  		}
  1714  	}
  1715  }
  1716  
  1717  func TestJacobi(t *testing.T) {
  1718  	testCases := []struct {
  1719  		x, y   int64
  1720  		result int
  1721  	}{
  1722  		{0, 1, 1},
  1723  		{0, -1, 1},
  1724  		{1, 1, 1},
  1725  		{1, -1, 1},
  1726  		{0, 5, 0},
  1727  		{1, 5, 1},
  1728  		{2, 5, -1},
  1729  		{-2, 5, -1},
  1730  		{2, -5, -1},
  1731  		{-2, -5, 1},
  1732  		{3, 5, -1},
  1733  		{5, 5, 0},
  1734  		{-5, 5, 0},
  1735  		{6, 5, 1},
  1736  		{6, -5, 1},
  1737  		{-6, 5, 1},
  1738  		{-6, -5, -1},
  1739  	}
  1740  
  1741  	var x, y Int
  1742  
  1743  	for i, test := range testCases {
  1744  		x.SetInt64(test.x)
  1745  		y.SetInt64(test.y)
  1746  		expected := test.result
  1747  		actual := Jacobi(&x, &y)
  1748  		if actual != expected {
  1749  			t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
  1750  		}
  1751  	}
  1752  }
  1753  
  1754  func TestJacobiPanic(t *testing.T) {
  1755  	const failureMsg = "test failure"
  1756  	defer func() {
  1757  		msg := recover()
  1758  		if msg == nil || msg == failureMsg {
  1759  			panic(msg)
  1760  		}
  1761  		t.Log(msg)
  1762  	}()
  1763  	x := NewInt(1)
  1764  	y := NewInt(2)
  1765  	// Jacobi should panic when the second argument is even.
  1766  	Jacobi(x, y)
  1767  	panic(failureMsg)
  1768  }
  1769  
  1770  func TestIssue2607(t *testing.T) {
  1771  	// This code sequence used to hang.
  1772  	n := NewInt(10)
  1773  	n.Rand(rand.New(rand.NewSource(9)), n)
  1774  }
  1775  
  1776  func TestSqrt(t *testing.T) {
  1777  	root := 0
  1778  	r := new(Int)
  1779  	for i := 0; i < 10000; i++ {
  1780  		if (root+1)*(root+1) <= i {
  1781  			root++
  1782  		}
  1783  		n := NewInt(int64(i))
  1784  		r.SetInt64(-2)
  1785  		r.Sqrt(n)
  1786  		if r.Cmp(NewInt(int64(root))) != 0 {
  1787  			t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
  1788  		}
  1789  	}
  1790  
  1791  	for i := 0; i < 1000; i += 10 {
  1792  		n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10)
  1793  		r := new(Int).Sqrt(n)
  1794  		root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10)
  1795  		if r.Cmp(root) != 0 {
  1796  			t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
  1797  		}
  1798  	}
  1799  
  1800  	// Test aliasing.
  1801  	r.SetInt64(100)
  1802  	r.Sqrt(r)
  1803  	if r.Int64() != 10 {
  1804  		t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
  1805  	}
  1806  }
  1807  
  1808  // We can't test this together with the other Exp tests above because
  1809  // it requires a different receiver setup.
  1810  func TestIssue22830(t *testing.T) {
  1811  	one := new(Int).SetInt64(1)
  1812  	base, _ := new(Int).SetString("84555555300000000000", 10)
  1813  	mod, _ := new(Int).SetString("66666670001111111111", 10)
  1814  	want, _ := new(Int).SetString("17888885298888888889", 10)
  1815  
  1816  	var tests = []int64{
  1817  		0, 1, -1,
  1818  	}
  1819  
  1820  	for _, n := range tests {
  1821  		m := NewInt(n)
  1822  		if got := m.Exp(base, one, mod); got.Cmp(want) != 0 {
  1823  			t.Errorf("(%v).Exp(%s, 1, %s) = %s, want %s", n, base, mod, got, want)
  1824  		}
  1825  	}
  1826  }
  1827  
  1828  func BenchmarkSqrt(b *testing.B) {
  1829  	n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10)
  1830  	b.ResetTimer()
  1831  	t := new(Int)
  1832  	for i := 0; i < b.N; i++ {
  1833  		t.Sqrt(n)
  1834  	}
  1835  }
  1836  
  1837  func benchmarkIntSqr(b *testing.B, nwords int) {
  1838  	x := new(Int)
  1839  	x.abs = rndNat(nwords)
  1840  	t := new(Int)
  1841  	b.ResetTimer()
  1842  	for i := 0; i < b.N; i++ {
  1843  		t.Mul(x, x)
  1844  	}
  1845  }
  1846  
  1847  func BenchmarkIntSqr(b *testing.B) {
  1848  	for _, n := range sqrBenchSizes {
  1849  		if isRaceBuilder && n > 1e3 {
  1850  			continue
  1851  		}
  1852  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
  1853  			benchmarkIntSqr(b, n)
  1854  		})
  1855  	}
  1856  }
  1857  
  1858  func benchmarkDiv(b *testing.B, aSize, bSize int) {
  1859  	var r = rand.New(rand.NewSource(1234))
  1860  	aa := randInt(r, uint(aSize))
  1861  	bb := randInt(r, uint(bSize))
  1862  	if aa.Cmp(bb) < 0 {
  1863  		aa, bb = bb, aa
  1864  	}
  1865  	x := new(Int)
  1866  	y := new(Int)
  1867  
  1868  	b.ResetTimer()
  1869  	for i := 0; i < b.N; i++ {
  1870  		x.DivMod(aa, bb, y)
  1871  	}
  1872  }
  1873  
  1874  func BenchmarkDiv(b *testing.B) {
  1875  	sizes := []int{
  1876  		10, 20, 50, 100, 200, 500, 1000,
  1877  		1e4, 1e5, 1e6, 1e7,
  1878  	}
  1879  	for _, i := range sizes {
  1880  		j := 2 * i
  1881  		b.Run(fmt.Sprintf("%d/%d", j, i), func(b *testing.B) {
  1882  			benchmarkDiv(b, j, i)
  1883  		})
  1884  	}
  1885  }
  1886  
  1887  func TestFillBytes(t *testing.T) {
  1888  	checkResult := func(t *testing.T, buf []byte, want *Int) {
  1889  		t.Helper()
  1890  		got := new(Int).SetBytes(buf)
  1891  		if got.CmpAbs(want) != 0 {
  1892  			t.Errorf("got 0x%x, want 0x%x: %x", got, want, buf)
  1893  		}
  1894  	}
  1895  	panics := func(f func()) (panic bool) {
  1896  		defer func() { panic = recover() != nil }()
  1897  		f()
  1898  		return
  1899  	}
  1900  
  1901  	for _, n := range []string{
  1902  		"0",
  1903  		"1000",
  1904  		"0xffffffff",
  1905  		"-0xffffffff",
  1906  		"0xffffffffffffffff",
  1907  		"0x10000000000000000",
  1908  		"0xabababababababababababababababababababababababababa",
  1909  		"0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
  1910  	} {
  1911  		t.Run(n, func(t *testing.T) {
  1912  			t.Log(n)
  1913  			x, ok := new(Int).SetString(n, 0)
  1914  			if !ok {
  1915  				panic("invalid test entry")
  1916  			}
  1917  
  1918  			// Perfectly sized buffer.
  1919  			byteLen := (x.BitLen() + 7) / 8
  1920  			buf := make([]byte, byteLen)
  1921  			checkResult(t, x.FillBytes(buf), x)
  1922  
  1923  			// Way larger, checking all bytes get zeroed.
  1924  			buf = make([]byte, 100)
  1925  			for i := range buf {
  1926  				buf[i] = 0xff
  1927  			}
  1928  			checkResult(t, x.FillBytes(buf), x)
  1929  
  1930  			// Too small.
  1931  			if byteLen > 0 {
  1932  				buf = make([]byte, byteLen-1)
  1933  				if !panics(func() { x.FillBytes(buf) }) {
  1934  					t.Errorf("expected panic for small buffer and value %x", x)
  1935  				}
  1936  			}
  1937  		})
  1938  	}
  1939  }
  1940  
  1941  func TestNewIntMinInt64(t *testing.T) {
  1942  	// Test for uint64 cast in NewInt.
  1943  	want := int64(math.MinInt64)
  1944  	if got := NewInt(want).Int64(); got != want {
  1945  		t.Fatalf("wanted %d, got %d", want, got)
  1946  	}
  1947  }
  1948  
  1949  func TestNewIntAllocs(t *testing.T) {
  1950  	testenv.SkipIfOptimizationOff(t)
  1951  	for _, n := range []int64{0, 7, -7, 1 << 30, -1 << 30, 1 << 50, -1 << 50} {
  1952  		x := NewInt(3)
  1953  		got := testing.AllocsPerRun(100, func() {
  1954  			// NewInt should inline, and all its allocations
  1955  			// can happen on the stack. Passing the result of NewInt
  1956  			// to Add should not cause any of those allocations to escape.
  1957  			x.Add(x, NewInt(n))
  1958  		})
  1959  		if got != 0 {
  1960  			t.Errorf("x.Add(x, NewInt(%d)), wanted 0 allocations, got %f", n, got)
  1961  		}
  1962  	}
  1963  }
  1964  
  1965  func TestFloat64(t *testing.T) {
  1966  	for _, test := range []struct {
  1967  		istr string
  1968  		f    float64
  1969  		acc  Accuracy
  1970  	}{
  1971  		{"-1000000000000000000000000000000000000000000000000000000", -1000000000000000078291540404596243842305360299886116864.000000, Below},
  1972  		{"-9223372036854775809", math.MinInt64, Above},
  1973  		{"-9223372036854775808", -9223372036854775808, Exact}, // -2^63
  1974  		{"-9223372036854775807", -9223372036854775807, Below},
  1975  		{"-18014398509481985", -18014398509481984.000000, Above},
  1976  		{"-18014398509481984", -18014398509481984.000000, Exact}, // -2^54
  1977  		{"-18014398509481983", -18014398509481984.000000, Below},
  1978  		{"-9007199254740993", -9007199254740992.000000, Above},
  1979  		{"-9007199254740992", -9007199254740992.000000, Exact}, // -2^53
  1980  		{"-9007199254740991", -9007199254740991.000000, Exact},
  1981  		{"-4503599627370497", -4503599627370497.000000, Exact},
  1982  		{"-4503599627370496", -4503599627370496.000000, Exact}, // -2^52
  1983  		{"-4503599627370495", -4503599627370495.000000, Exact},
  1984  		{"-12345", -12345, Exact},
  1985  		{"-1", -1, Exact},
  1986  		{"0", 0, Exact},
  1987  		{"1", 1, Exact},
  1988  		{"12345", 12345, Exact},
  1989  		{"0x1010000000000000", 0x1010000000000000, Exact}, // >2^53 but exact nonetheless
  1990  		{"9223372036854775807", 9223372036854775808, Above},
  1991  		{"9223372036854775808", 9223372036854775808, Exact}, // +2^63
  1992  		{"1000000000000000000000000000000000000000000000000000000", 1000000000000000078291540404596243842305360299886116864.000000, Above},
  1993  	} {
  1994  		i, ok := new(Int).SetString(test.istr, 0)
  1995  		if !ok {
  1996  			t.Errorf("SetString(%s) failed", test.istr)
  1997  			continue
  1998  		}
  1999  
  2000  		// Test against expectation.
  2001  		f, acc := i.Float64()
  2002  		if f != test.f || acc != test.acc {
  2003  			t.Errorf("%s: got %f (%s); want %f (%s)", test.istr, f, acc, test.f, test.acc)
  2004  		}
  2005  
  2006  		// Cross-check the fast path against the big.Float implementation.
  2007  		f2, acc2 := new(Float).SetInt(i).Float64()
  2008  		if f != f2 || acc != acc2 {
  2009  			t.Errorf("%s: got %f (%s); Float.Float64 gives %f (%s)", test.istr, f, acc, f2, acc2)
  2010  		}
  2011  	}
  2012  }
  2013  

View as plain text