Home | History | Annotate | Download | only in big 
      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 	"math/rand"
     12 	"strings"
     13 	"testing"
     14 	"testing/quick"
     15 )
     16 
     17 func isNormalized(x *Int) bool {
     18 	if len(x.abs) == 0 {
     19 		return !x.neg
     20 	}
     21 	// len(x.abs) > 0
     22 	return x.abs[len(x.abs)-1] != 0
     23 }
     24 
     25 type funZZ func(z, x, y *Int) *Int
     26 type argZZ struct {
     27 	z, x, y *Int
     28 }
     29 
     30 var sumZZ = []argZZ{
     31 	{NewInt(0), NewInt(0), NewInt(0)},
     32 	{NewInt(1), NewInt(1), NewInt(0)},
     33 	{NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
     34 	{NewInt(-1), NewInt(-1), NewInt(0)},
     35 	{NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
     36 	{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
     37 }
     38 
     39 var prodZZ = []argZZ{
     40 	{NewInt(0), NewInt(0), NewInt(0)},
     41 	{NewInt(0), NewInt(1), NewInt(0)},
     42 	{NewInt(1), NewInt(1), NewInt(1)},
     43 	{NewInt(-991 * 991), NewInt(991), NewInt(-991)},
     44 	// TODO(gri) add larger products
     45 }
     46 
     47 func TestSignZ(t *testing.T) {
     48 	var zero Int
     49 	for _, a := range sumZZ {
     50 		s := a.z.Sign()
     51 		e := a.z.Cmp(&zero)
     52 		if s != e {
     53 			t.Errorf("got %d; want %d for z = %v", s, e, a.z)
     54 		}
     55 	}
     56 }
     57 
     58 func TestSetZ(t *testing.T) {
     59 	for _, a := range sumZZ {
     60 		var z Int
     61 		z.Set(a.z)
     62 		if !isNormalized(&z) {
     63 			t.Errorf("%v is not normalized", z)
     64 		}
     65 		if (&z).Cmp(a.z) != 0 {
     66 			t.Errorf("got z = %v; want %v", z, a.z)
     67 		}
     68 	}
     69 }
     70 
     71 func TestAbsZ(t *testing.T) {
     72 	var zero Int
     73 	for _, a := range sumZZ {
     74 		var z Int
     75 		z.Abs(a.z)
     76 		var e Int
     77 		e.Set(a.z)
     78 		if e.Cmp(&zero) < 0 {
     79 			e.Sub(&zero, &e)
     80 		}
     81 		if z.Cmp(&e) != 0 {
     82 			t.Errorf("got z = %v; want %v", z, e)
     83 		}
     84 	}
     85 }
     86 
     87 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
     88 	var z Int
     89 	f(&z, a.x, a.y)
     90 	if !isNormalized(&z) {
     91 		t.Errorf("%s%v is not normalized", msg, z)
     92 	}
     93 	if (&z).Cmp(a.z) != 0 {
     94 		t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
     95 	}
     96 }
     97 
     98 func TestSumZZ(t *testing.T) {
     99 	AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
    100 	SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
    101 	for _, a := range sumZZ {
    102 		arg := a
    103 		testFunZZ(t, "AddZZ", AddZZ, arg)
    104 
    105 		arg = argZZ{a.z, a.y, a.x}
    106 		testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
    107 
    108 		arg = argZZ{a.x, a.z, a.y}
    109 		testFunZZ(t, "SubZZ", SubZZ, arg)
    110 
    111 		arg = argZZ{a.y, a.z, a.x}
    112 		testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
    113 	}
    114 }
    115 
    116 func TestProdZZ(t *testing.T) {
    117 	MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
    118 	for _, a := range prodZZ {
    119 		arg := a
    120 		testFunZZ(t, "MulZZ", MulZZ, arg)
    121 
    122 		arg = argZZ{a.z, a.y, a.x}
    123 		testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
    124 	}
    125 }
    126 
    127 // mulBytes returns x*y via grade school multiplication. Both inputs
    128 // and the result are assumed to be in big-endian representation (to
    129 // match the semantics of Int.Bytes and Int.SetBytes).
    130 func mulBytes(x, y []byte) []byte {
    131 	z := make([]byte, len(x)+len(y))
    132 
    133 	// multiply
    134 	k0 := len(z) - 1
    135 	for j := len(y) - 1; j >= 0; j-- {
    136 		d := int(y[j])
    137 		if d != 0 {
    138 			k := k0
    139 			carry := 0
    140 			for i := len(x) - 1; i >= 0; i-- {
    141 				t := int(z[k]) + int(x[i])*d + carry
    142 				z[k], carry = byte(t), t>>8
    143 				k--
    144 			}
    145 			z[k] = byte(carry)
    146 		}
    147 		k0--
    148 	}
    149 
    150 	// normalize (remove leading 0's)
    151 	i := 0
    152 	for i < len(z) && z[i] == 0 {
    153 		i++
    154 	}
    155 
    156 	return z[i:]
    157 }
    158 
    159 func checkMul(a, b []byte) bool {
    160 	var x, y, z1 Int
    161 	x.SetBytes(a)
    162 	y.SetBytes(b)
    163 	z1.Mul(&x, &y)
    164 
    165 	var z2 Int
    166 	z2.SetBytes(mulBytes(a, b))
    167 
    168 	return z1.Cmp(&z2) == 0
    169 }
    170 
    171 func TestMul(t *testing.T) {
    172 	if err := quick.Check(checkMul, nil); err != nil {
    173 		t.Error(err)
    174 	}
    175 }
    176 
    177 var mulRangesZ = []struct {
    178 	a, b int64
    179 	prod string
    180 }{
    181 	// entirely positive ranges are covered by mulRangesN
    182 	{-1, 1, "0"},
    183 	{-2, -1, "2"},
    184 	{-3, -2, "6"},
    185 	{-3, -1, "-6"},
    186 	{1, 3, "6"},
    187 	{-10, -10, "-10"},
    188 	{0, -1, "1"},                      // empty range
    189 	{-1, -100, "1"},                   // empty range
    190 	{-1, 1, "0"},                      // range includes 0
    191 	{-1e9, 0, "0"},                    // range includes 0
    192 	{-1e9, 1e9, "0"},                  // range includes 0
    193 	{-10, -1, "3628800"},              // 10!
    194 	{-20, -2, "-2432902008176640000"}, // -20!
    195 	{-99, -1,
    196 		"-933262154439441526816992388562667004907159682643816214685929" +
    197 			"638952175999932299156089414639761565182862536979208272237582" +
    198 			"511852109168640000000000000000000000", // -99!
    199 	},
    200 }
    201 
    202 func TestMulRangeZ(t *testing.T) {
    203 	var tmp Int
    204 	// test entirely positive ranges
    205 	for i, r := range mulRangesN {
    206 		prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
    207 		if prod != r.prod {
    208 			t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
    209 		}
    210 	}
    211 	// test other ranges
    212 	for i, r := range mulRangesZ {
    213 		prod := tmp.MulRange(r.a, r.b).String()
    214 		if prod != r.prod {
    215 			t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
    216 		}
    217 	}
    218 }
    219 
    220 func TestBinomial(t *testing.T) {
    221 	var z Int
    222 	for _, test := range []struct {
    223 		n, k int64
    224 		want string
    225 	}{
    226 		{0, 0, "1"},
    227 		{0, 1, "0"},
    228 		{1, 0, "1"},
    229 		{1, 1, "1"},
    230 		{1, 10, "0"},
    231 		{4, 0, "1"},
    232 		{4, 1, "4"},
    233 		{4, 2, "6"},
    234 		{4, 3, "4"},
    235 		{4, 4, "1"},
    236 		{10, 1, "10"},
    237 		{10, 9, "10"},
    238 		{10, 5, "252"},
    239 		{11, 5, "462"},
    240 		{11, 6, "462"},
    241 		{100, 10, "17310309456440"},
    242 		{100, 90, "17310309456440"},
    243 		{1000, 10, "263409560461970212832400"},
    244 		{1000, 990, "263409560461970212832400"},
    245 	} {
    246 		if got := z.Binomial(test.n, test.k).String(); got != test.want {
    247 			t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
    248 		}
    249 	}
    250 }
    251 
    252 func BenchmarkBinomial(b *testing.B) {
    253 	var z Int
    254 	for i := b.N - 1; i >= 0; i-- {
    255 		z.Binomial(1000, 990)
    256 	}
    257 }
    258 
    259 // Examples from the Go Language Spec, section "Arithmetic operators"
    260 var divisionSignsTests = []struct {
    261 	x, y int64
    262 	q, r int64 // T-division
    263 	d, m int64 // Euclidian division
    264 }{
    265 	{5, 3, 1, 2, 1, 2},
    266 	{-5, 3, -1, -2, -2, 1},
    267 	{5, -3, -1, 2, -1, 2},
    268 	{-5, -3, 1, -2, 2, 1},
    269 	{1, 2, 0, 1, 0, 1},
    270 	{8, 4, 2, 0, 2, 0},
    271 }
    272 
    273 func TestDivisionSigns(t *testing.T) {
    274 	for i, test := range divisionSignsTests {
    275 		x := NewInt(test.x)
    276 		y := NewInt(test.y)
    277 		q := NewInt(test.q)
    278 		r := NewInt(test.r)
    279 		d := NewInt(test.d)
    280 		m := NewInt(test.m)
    281 
    282 		q1 := new(Int).Quo(x, y)
    283 		r1 := new(Int).Rem(x, y)
    284 		if !isNormalized(q1) {
    285 			t.Errorf("#%d Quo: %v is not normalized", i, *q1)
    286 		}
    287 		if !isNormalized(r1) {
    288 			t.Errorf("#%d Rem: %v is not normalized", i, *r1)
    289 		}
    290 		if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
    291 			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
    292 		}
    293 
    294 		q2, r2 := new(Int).QuoRem(x, y, new(Int))
    295 		if !isNormalized(q2) {
    296 			t.Errorf("#%d Quo: %v is not normalized", i, *q2)
    297 		}
    298 		if !isNormalized(r2) {
    299 			t.Errorf("#%d Rem: %v is not normalized", i, *r2)
    300 		}
    301 		if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
    302 			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
    303 		}
    304 
    305 		d1 := new(Int).Div(x, y)
    306 		m1 := new(Int).Mod(x, y)
    307 		if !isNormalized(d1) {
    308 			t.Errorf("#%d Div: %v is not normalized", i, *d1)
    309 		}
    310 		if !isNormalized(m1) {
    311 			t.Errorf("#%d Mod: %v is not normalized", i, *m1)
    312 		}
    313 		if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
    314 			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
    315 		}
    316 
    317 		d2, m2 := new(Int).DivMod(x, y, new(Int))
    318 		if !isNormalized(d2) {
    319 			t.Errorf("#%d Div: %v is not normalized", i, *d2)
    320 		}
    321 		if !isNormalized(m2) {
    322 			t.Errorf("#%d Mod: %v is not normalized", i, *m2)
    323 		}
    324 		if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
    325 			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
    326 		}
    327 	}
    328 }
    329 
    330 func norm(x nat) nat {
    331 	i := len(x)
    332 	for i > 0 && x[i-1] == 0 {
    333 		i--
    334 	}
    335 	return x[:i]
    336 }
    337 
    338 func TestBits(t *testing.T) {
    339 	for _, test := range []nat{
    340 		nil,
    341 		{0},
    342 		{1},
    343 		{0, 1, 2, 3, 4},
    344 		{4, 3, 2, 1, 0},
    345 		{4, 3, 2, 1, 0, 0, 0, 0},
    346 	} {
    347 		var z Int
    348 		z.neg = true
    349 		got := z.SetBits(test)
    350 		want := norm(test)
    351 		if got.abs.cmp(want) != 0 {
    352 			t.Errorf("SetBits(%v) = %v; want %v", test, got.abs, want)
    353 		}
    354 
    355 		if got.neg {
    356 			t.Errorf("SetBits(%v): got negative result", test)
    357 		}
    358 
    359 		bits := nat(z.Bits())
    360 		if bits.cmp(want) != 0 {
    361 			t.Errorf("%v.Bits() = %v; want %v", z.abs, bits, want)
    362 		}
    363 	}
    364 }
    365 
    366 func checkSetBytes(b []byte) bool {
    367 	hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
    368 	hex2 := hex.EncodeToString(b)
    369 
    370 	for len(hex1) < len(hex2) {
    371 		hex1 = "0" + hex1
    372 	}
    373 
    374 	for len(hex1) > len(hex2) {
    375 		hex2 = "0" + hex2
    376 	}
    377 
    378 	return hex1 == hex2
    379 }
    380 
    381 func TestSetBytes(t *testing.T) {
    382 	if err := quick.Check(checkSetBytes, nil); err != nil {
    383 		t.Error(err)
    384 	}
    385 }
    386 
    387 func checkBytes(b []byte) bool {
    388 	// trim leading zero bytes since Bytes() won't return them
    389 	// (was issue 12231)
    390 	for len(b) > 0 && b[0] == 0 {
    391 		b = b[1:]
    392 	}
    393 	b2 := new(Int).SetBytes(b).Bytes()
    394 	return bytes.Equal(b, b2)
    395 }
    396 
    397 func TestBytes(t *testing.T) {
    398 	if err := quick.Check(checkBytes, nil); err != nil {
    399 		t.Error(err)
    400 	}
    401 }
    402 
    403 func checkQuo(x, y []byte) bool {
    404 	u := new(Int).SetBytes(x)
    405 	v := new(Int).SetBytes(y)
    406 
    407 	if len(v.abs) == 0 {
    408 		return true
    409 	}
    410 
    411 	r := new(Int)
    412 	q, r := new(Int).QuoRem(u, v, r)
    413 
    414 	if r.Cmp(v) >= 0 {
    415 		return false
    416 	}
    417 
    418 	uprime := new(Int).Set(q)
    419 	uprime.Mul(uprime, v)
    420 	uprime.Add(uprime, r)
    421 
    422 	return uprime.Cmp(u) == 0
    423 }
    424 
    425 var quoTests = []struct {
    426 	x, y string
    427 	q, r string
    428 }{
    429 	{
    430 		"476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
    431 		"9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
    432 		"50911",
    433 		"1",
    434 	},
    435 	{
    436 		"11510768301994997771168",
    437 		"1328165573307167369775",
    438 		"8",
    439 		"885443715537658812968",
    440 	},
    441 }
    442 
    443 func TestQuo(t *testing.T) {
    444 	if err := quick.Check(checkQuo, nil); err != nil {
    445 		t.Error(err)
    446 	}
    447 
    448 	for i, test := range quoTests {
    449 		x, _ := new(Int).SetString(test.x, 10)
    450 		y, _ := new(Int).SetString(test.y, 10)
    451 		expectedQ, _ := new(Int).SetString(test.q, 10)
    452 		expectedR, _ := new(Int).SetString(test.r, 10)
    453 
    454 		r := new(Int)
    455 		q, r := new(Int).QuoRem(x, y, r)
    456 
    457 		if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
    458 			t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
    459 		}
    460 	}
    461 }
    462 
    463 func TestQuoStepD6(t *testing.T) {
    464 	// See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
    465 	// a code path which only triggers 1 in 10^{-19} cases.
    466 
    467 	u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
    468 	v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
    469 
    470 	r := new(Int)
    471 	q, r := new(Int).QuoRem(u, v, r)
    472 	const expectedQ64 = "18446744073709551613"
    473 	const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
    474 	const expectedQ32 = "4294967293"
    475 	const expectedR32 = "39614081266355540837921718287"
    476 	if q.String() != expectedQ64 && q.String() != expectedQ32 ||
    477 		r.String() != expectedR64 && r.String() != expectedR32 {
    478 		t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
    479 	}
    480 }
    481 
    482 func BenchmarkQuoRem(b *testing.B) {
    483 	x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
    484 	y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
    485 	q := new(Int)
    486 	r := new(Int)
    487 
    488 	b.ResetTimer()
    489 	for i := 0; i < b.N; i++ {
    490 		q.QuoRem(y, x, r)
    491 	}
    492 }
    493 
    494 var bitLenTests = []struct {
    495 	in  string
    496 	out int
    497 }{
    498 	{"-1", 1},
    499 	{"0", 0},
    500 	{"1", 1},
    501 	{"2", 2},
    502 	{"4", 3},
    503 	{"0xabc", 12},
    504 	{"0x8000", 16},
    505 	{"0x80000000", 32},
    506 	{"0x800000000000", 48},
    507 	{"0x8000000000000000", 64},
    508 	{"0x80000000000000000000", 80},
    509 	{"-0x4000000000000000000000", 87},
    510 }
    511 
    512 func TestBitLen(t *testing.T) {
    513 	for i, test := range bitLenTests {
    514 		x, ok := new(Int).SetString(test.in, 0)
    515 		if !ok {
    516 			t.Errorf("#%d test input invalid: %s", i, test.in)
    517 			continue
    518 		}
    519 
    520 		if n := x.BitLen(); n != test.out {
    521 			t.Errorf("#%d got %d want %d", i, n, test.out)
    522 		}
    523 	}
    524 }
    525 
    526 var expTests = []struct {
    527 	x, y, m string
    528 	out     string
    529 }{
    530 	// y <= 0
    531 	{"0", "0", "", "1"},
    532 	{"1", "0", "", "1"},
    533 	{"-10", "0", "", "1"},
    534 	{"1234", "-1", "", "1"},
    535 
    536 	// m == 1
    537 	{"0", "0", "1", "0"},
    538 	{"1", "0", "1", "0"},
    539 	{"-10", "0", "1", "0"},
    540 	{"1234", "-1", "1", "0"},
    541 
    542 	// misc
    543 	{"5", "1", "3", "2"},
    544 	{"5", "-7", "", "1"},
    545 	{"-5", "-7", "", "1"},
    546 	{"5", "0", "", "1"},
    547 	{"-5", "0", "", "1"},
    548 	{"5", "1", "", "5"},
    549 	{"-5", "1", "", "-5"},
    550 	{"-5", "1", "7", "2"},
    551 	{"-2", "3", "2", "0"},
    552 	{"5", "2", "", "25"},
    553 	{"1", "65537", "2", "1"},
    554 	{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
    555 	{"0x8000000000000000", "2", "6719", "4944"},
    556 	{"0x8000000000000000", "3", "6719", "5447"},
    557 	{"0x8000000000000000", "1000", "6719", "1603"},
    558 	{"0x8000000000000000", "1000000", "6719", "3199"},
    559 	{"0x8000000000000000", "-1000000", "6719", "1"},
    560 
    561 	{"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
    562 
    563 	{
    564 		"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
    565 		"298472983472983471903246121093472394872319615612417471234712061",
    566 		"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
    567 		"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
    568 	},
    569 	// test case for issue 8822
    570 	{
    571 		"11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
    572 		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
    573 		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
    574 		"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
    575 	},
    576 	{
    577 		"-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
    578 		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
    579 		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
    580 		"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
    581 	},
    582 
    583 	// test cases for issue 13907
    584 	{"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
    585 	{"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
    586 	{"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
    587 	{"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
    588 
    589 	{
    590 		"2",
    591 		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
    592 		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", // odd
    593 		"0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
    594 	},
    595 	{
    596 		"2",
    597 		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
    598 		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", // even
    599 		"0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
    600 	},
    601 }
    602 
    603 func TestExp(t *testing.T) {
    604 	for i, test := range expTests {
    605 		x, ok1 := new(Int).SetString(test.x, 0)
    606 		y, ok2 := new(Int).SetString(test.y, 0)
    607 		out, ok3 := new(Int).SetString(test.out, 0)
    608 
    609 		var ok4 bool
    610 		var m *Int
    611 
    612 		if len(test.m) == 0 {
    613 			m, ok4 = nil, true
    614 		} else {
    615 			m, ok4 = new(Int).SetString(test.m, 0)
    616 		}
    617 
    618 		if !ok1 || !ok2 || !ok3 || !ok4 {
    619 			t.Errorf("#%d: error in input", i)
    620 			continue
    621 		}
    622 
    623 		z1 := new(Int).Exp(x, y, m)
    624 		if !isNormalized(z1) {
    625 			t.Errorf("#%d: %v is not normalized", i, *z1)
    626 		}
    627 		if z1.Cmp(out) != 0 {
    628 			t.Errorf("#%d: got %x want %x", i, z1, out)
    629 		}
    630 
    631 		if m == nil {
    632 			// The result should be the same as for m == 0;
    633 			// specifically, there should be no div-zero panic.
    634 			m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
    635 			z2 := new(Int).Exp(x, y, m)
    636 			if z2.Cmp(z1) != 0 {
    637 				t.Errorf("#%d: got %x want %x", i, z2, z1)
    638 			}
    639 		}
    640 	}
    641 }
    642 
    643 func BenchmarkExp(b *testing.B) {
    644 	x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
    645 	y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
    646 	n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
    647 	out := new(Int)
    648 	for i := 0; i < b.N; i++ {
    649 		out.Exp(x, y, n)
    650 	}
    651 }
    652 
    653 func BenchmarkExp2(b *testing.B) {
    654 	x, _ := new(Int).SetString("2", 0)
    655 	y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
    656 	n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
    657 	out := new(Int)
    658 	for i := 0; i < b.N; i++ {
    659 		out.Exp(x, y, n)
    660 	}
    661 }
    662 
    663 func checkGcd(aBytes, bBytes []byte) bool {
    664 	x := new(Int)
    665 	y := new(Int)
    666 	a := new(Int).SetBytes(aBytes)
    667 	b := new(Int).SetBytes(bBytes)
    668 
    669 	d := new(Int).GCD(x, y, a, b)
    670 	x.Mul(x, a)
    671 	y.Mul(y, b)
    672 	x.Add(x, y)
    673 
    674 	return x.Cmp(d) == 0
    675 }
    676 
    677 var gcdTests = []struct {
    678 	d, x, y, a, b string
    679 }{
    680 	// a <= 0 || b <= 0
    681 	{"0", "0", "0", "0", "0"},
    682 	{"0", "0", "0", "0", "7"},
    683 	{"0", "0", "0", "11", "0"},
    684 	{"0", "0", "0", "-77", "35"},
    685 	{"0", "0", "0", "64515", "-24310"},
    686 	{"0", "0", "0", "-64515", "-24310"},
    687 
    688 	{"1", "-9", "47", "120", "23"},
    689 	{"7", "1", "-2", "77", "35"},
    690 	{"935", "-3", "8", "64515", "24310"},
    691 	{"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
    692 	{"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
    693 
    694 	// test early exit (after one Euclidean iteration) in binaryGCD
    695 	{"1", "", "", "1", "98920366548084643601728869055592650835572950932266967461790948584315647051443"},
    696 }
    697 
    698 func testGcd(t *testing.T, d, x, y, a, b *Int) {
    699 	var X *Int
    700 	if x != nil {
    701 		X = new(Int)
    702 	}
    703 	var Y *Int
    704 	if y != nil {
    705 		Y = new(Int)
    706 	}
    707 
    708 	D := new(Int).GCD(X, Y, a, b)
    709 	if D.Cmp(d) != 0 {
    710 		t.Errorf("GCD(%s, %s): got d = %s, want %s", a, b, D, d)
    711 	}
    712 	if x != nil && X.Cmp(x) != 0 {
    713 		t.Errorf("GCD(%s, %s): got x = %s, want %s", a, b, X, x)
    714 	}
    715 	if y != nil && Y.Cmp(y) != 0 {
    716 		t.Errorf("GCD(%s, %s): got y = %s, want %s", a, b, Y, y)
    717 	}
    718 
    719 	// binaryGCD requires a > 0 && b > 0
    720 	if a.Sign() <= 0 || b.Sign() <= 0 {
    721 		return
    722 	}
    723 
    724 	D.binaryGCD(a, b)
    725 	if D.Cmp(d) != 0 {
    726 		t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, D, d)
    727 	}
    728 
    729 	// check results in presence of aliasing (issue #11284)
    730 	a2 := new(Int).Set(a)
    731 	b2 := new(Int).Set(b)
    732 	a2.binaryGCD(a2, b2) // result is same as 1st argument
    733 	if a2.Cmp(d) != 0 {
    734 		t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, a2, d)
    735 	}
    736 
    737 	a2 = new(Int).Set(a)
    738 	b2 = new(Int).Set(b)
    739 	b2.binaryGCD(a2, b2) // result is same as 2nd argument
    740 	if b2.Cmp(d) != 0 {
    741 		t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, b2, d)
    742 	}
    743 }
    744 
    745 func TestGcd(t *testing.T) {
    746 	for _, test := range gcdTests {
    747 		d, _ := new(Int).SetString(test.d, 0)
    748 		x, _ := new(Int).SetString(test.x, 0)
    749 		y, _ := new(Int).SetString(test.y, 0)
    750 		a, _ := new(Int).SetString(test.a, 0)
    751 		b, _ := new(Int).SetString(test.b, 0)
    752 
    753 		testGcd(t, d, nil, nil, a, b)
    754 		testGcd(t, d, x, nil, a, b)
    755 		testGcd(t, d, nil, y, a, b)
    756 		testGcd(t, d, x, y, a, b)
    757 	}
    758 
    759 	if err := quick.Check(checkGcd, nil); err != nil {
    760 		t.Error(err)
    761 	}
    762 }
    763 
    764 type intShiftTest struct {
    765 	in    string
    766 	shift uint
    767 	out   string
    768 }
    769 
    770 var rshTests = []intShiftTest{
    771 	{"0", 0, "0"},
    772 	{"-0", 0, "0"},
    773 	{"0", 1, "0"},
    774 	{"0", 2, "0"},
    775 	{"1", 0, "1"},
    776 	{"1", 1, "0"},
    777 	{"1", 2, "0"},
    778 	{"2", 0, "2"},
    779 	{"2", 1, "1"},
    780 	{"-1", 0, "-1"},
    781 	{"-1", 1, "-1"},
    782 	{"-1", 10, "-1"},
    783 	{"-100", 2, "-25"},
    784 	{"-100", 3, "-13"},
    785 	{"-100", 100, "-1"},
    786 	{"4294967296", 0, "4294967296"},
    787 	{"4294967296", 1, "2147483648"},
    788 	{"4294967296", 2, "1073741824"},
    789 	{"18446744073709551616", 0, "18446744073709551616"},
    790 	{"18446744073709551616", 1, "9223372036854775808"},
    791 	{"18446744073709551616", 2, "4611686018427387904"},
    792 	{"18446744073709551616", 64, "1"},
    793 	{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
    794 	{"340282366920938463463374607431768211456", 128, "1"},
    795 }
    796 
    797 func TestRsh(t *testing.T) {
    798 	for i, test := range rshTests {
    799 		in, _ := new(Int).SetString(test.in, 10)
    800 		expected, _ := new(Int).SetString(test.out, 10)
    801 		out := new(Int).Rsh(in, test.shift)
    802 
    803 		if !isNormalized(out) {
    804 			t.Errorf("#%d: %v is not normalized", i, *out)
    805 		}
    806 		if out.Cmp(expected) != 0 {
    807 			t.Errorf("#%d: got %s want %s", i, out, expected)
    808 		}
    809 	}
    810 }
    811 
    812 func TestRshSelf(t *testing.T) {
    813 	for i, test := range rshTests {
    814 		z, _ := new(Int).SetString(test.in, 10)
    815 		expected, _ := new(Int).SetString(test.out, 10)
    816 		z.Rsh(z, test.shift)
    817 
    818 		if !isNormalized(z) {
    819 			t.Errorf("#%d: %v is not normalized", i, *z)
    820 		}
    821 		if z.Cmp(expected) != 0 {
    822 			t.Errorf("#%d: got %s want %s", i, z, expected)
    823 		}
    824 	}
    825 }
    826 
    827 var lshTests = []intShiftTest{
    828 	{"0", 0, "0"},
    829 	{"0", 1, "0"},
    830 	{"0", 2, "0"},
    831 	{"1", 0, "1"},
    832 	{"1", 1, "2"},
    833 	{"1", 2, "4"},
    834 	{"2", 0, "2"},
    835 	{"2", 1, "4"},
    836 	{"2", 2, "8"},
    837 	{"-87", 1, "-174"},
    838 	{"4294967296", 0, "4294967296"},
    839 	{"4294967296", 1, "8589934592"},
    840 	{"4294967296", 2, "17179869184"},
    841 	{"18446744073709551616", 0, "18446744073709551616"},
    842 	{"9223372036854775808", 1, "18446744073709551616"},
    843 	{"4611686018427387904", 2, "18446744073709551616"},
    844 	{"1", 64, "18446744073709551616"},
    845 	{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
    846 	{"1", 128, "340282366920938463463374607431768211456"},
    847 }
    848 
    849 func TestLsh(t *testing.T) {
    850 	for i, test := range lshTests {
    851 		in, _ := new(Int).SetString(test.in, 10)
    852 		expected, _ := new(Int).SetString(test.out, 10)
    853 		out := new(Int).Lsh(in, test.shift)
    854 
    855 		if !isNormalized(out) {
    856 			t.Errorf("#%d: %v is not normalized", i, *out)
    857 		}
    858 		if out.Cmp(expected) != 0 {
    859 			t.Errorf("#%d: got %s want %s", i, out, expected)
    860 		}
    861 	}
    862 }
    863 
    864 func TestLshSelf(t *testing.T) {
    865 	for i, test := range lshTests {
    866 		z, _ := new(Int).SetString(test.in, 10)
    867 		expected, _ := new(Int).SetString(test.out, 10)
    868 		z.Lsh(z, test.shift)
    869 
    870 		if !isNormalized(z) {
    871 			t.Errorf("#%d: %v is not normalized", i, *z)
    872 		}
    873 		if z.Cmp(expected) != 0 {
    874 			t.Errorf("#%d: got %s want %s", i, z, expected)
    875 		}
    876 	}
    877 }
    878 
    879 func TestLshRsh(t *testing.T) {
    880 	for i, test := range rshTests {
    881 		in, _ := new(Int).SetString(test.in, 10)
    882 		out := new(Int).Lsh(in, test.shift)
    883 		out = out.Rsh(out, test.shift)
    884 
    885 		if !isNormalized(out) {
    886 			t.Errorf("#%d: %v is not normalized", i, *out)
    887 		}
    888 		if in.Cmp(out) != 0 {
    889 			t.Errorf("#%d: got %s want %s", i, out, in)
    890 		}
    891 	}
    892 	for i, test := range lshTests {
    893 		in, _ := new(Int).SetString(test.in, 10)
    894 		out := new(Int).Lsh(in, test.shift)
    895 		out.Rsh(out, test.shift)
    896 
    897 		if !isNormalized(out) {
    898 			t.Errorf("#%d: %v is not normalized", i, *out)
    899 		}
    900 		if in.Cmp(out) != 0 {
    901 			t.Errorf("#%d: got %s want %s", i, out, in)
    902 		}
    903 	}
    904 }
    905 
    906 var int64Tests = []int64{
    907 	0,
    908 	1,
    909 	-1,
    910 	4294967295,
    911 	-4294967295,
    912 	4294967296,
    913 	-4294967296,
    914 	9223372036854775807,
    915 	-9223372036854775807,
    916 	-9223372036854775808,
    917 }
    918 
    919 func TestInt64(t *testing.T) {
    920 	for i, testVal := range int64Tests {
    921 		in := NewInt(testVal)
    922 		out := in.Int64()
    923 
    924 		if out != testVal {
    925 			t.Errorf("#%d got %d want %d", i, out, testVal)
    926 		}
    927 	}
    928 }
    929 
    930 var uint64Tests = []uint64{
    931 	0,
    932 	1,
    933 	4294967295,
    934 	4294967296,
    935 	8589934591,
    936 	8589934592,
    937 	9223372036854775807,
    938 	9223372036854775808,
    939 	18446744073709551615, // 1<<64 - 1
    940 }
    941 
    942 func TestUint64(t *testing.T) {
    943 	in := new(Int)
    944 	for i, testVal := range uint64Tests {
    945 		in.SetUint64(testVal)
    946 		out := in.Uint64()
    947 
    948 		if out != testVal {
    949 			t.Errorf("#%d got %d want %d", i, out, testVal)
    950 		}
    951 
    952 		str := fmt.Sprint(testVal)
    953 		strOut := in.String()
    954 		if strOut != str {
    955 			t.Errorf("#%d.String got %s want %s", i, strOut, str)
    956 		}
    957 	}
    958 }
    959 
    960 var bitwiseTests = []struct {
    961 	x, y                 string
    962 	and, or, xor, andNot string
    963 }{
    964 	{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
    965 	{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
    966 	{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
    967 	{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
    968 	{"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
    969 	{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
    970 	{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
    971 	{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
    972 	{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
    973 	{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
    974 	{"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
    975 	{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
    976 	{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
    977 	{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
    978 	{
    979 		"0x1000009dc6e3d9822cba04129bcbe3401",
    980 		"0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
    981 		"0x1000001186210100001000009048c2001",
    982 		"0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
    983 		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
    984 		"0x8c40c2d8822caa04120b8321400",
    985 	},
    986 	{
    987 		"0x1000009dc6e3d9822cba04129bcbe3401",
    988 		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
    989 		"0x8c40c2d8822caa04120b8321401",
    990 		"-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
    991 		"-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
    992 		"0x1000001186210100001000009048c2000",
    993 	},
    994 	{
    995 		"-0x1000009dc6e3d9822cba04129bcbe3401",
    996 		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
    997 		"-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
    998 		"-0x1000001186210100001000009048c2001",
    999 		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
   1000 		"0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
   1001 	},
   1002 }
   1003 
   1004 type bitFun func(z, x, y *Int) *Int
   1005 
   1006 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
   1007 	expected := new(Int)
   1008 	expected.SetString(exp, 0)
   1009 
   1010 	out := f(new(Int), x, y)
   1011 	if out.Cmp(expected) != 0 {
   1012 		t.Errorf("%s: got %s want %s", msg, out, expected)
   1013 	}
   1014 }
   1015 
   1016 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
   1017 	self := new(Int)
   1018 	self.Set(x)
   1019 	expected := new(Int)
   1020 	expected.SetString(exp, 0)
   1021 
   1022 	self = f(self, self, y)
   1023 	if self.Cmp(expected) != 0 {
   1024 		t.Errorf("%s: got %s want %s", msg, self, expected)
   1025 	}
   1026 }
   1027 
   1028 func altBit(x *Int, i int) uint {
   1029 	z := new(Int).Rsh(x, uint(i))
   1030 	z = z.And(z, NewInt(1))
   1031 	if z.Cmp(new(Int)) != 0 {
   1032 		return 1
   1033 	}
   1034 	return 0
   1035 }
   1036 
   1037 func altSetBit(z *Int, x *Int, i int, b uint) *Int {
   1038 	one := NewInt(1)
   1039 	m := one.Lsh(one, uint(i))
   1040 	switch b {
   1041 	case 1:
   1042 		return z.Or(x, m)
   1043 	case 0:
   1044 		return z.AndNot(x, m)
   1045 	}
   1046 	panic("set bit is not 0 or 1")
   1047 }
   1048 
   1049 func testBitset(t *testing.T, x *Int) {
   1050 	n := x.BitLen()
   1051 	z := new(Int).Set(x)
   1052 	z1 := new(Int).Set(x)
   1053 	for i := 0; i < n+10; i++ {
   1054 		old := z.Bit(i)
   1055 		old1 := altBit(z1, i)
   1056 		if old != old1 {
   1057 			t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
   1058 		}
   1059 		z := new(Int).SetBit(z, i, 1)
   1060 		z1 := altSetBit(new(Int), z1, i, 1)
   1061 		if z.Bit(i) == 0 {
   1062 			t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
   1063 		}
   1064 		if z.Cmp(z1) != 0 {
   1065 			t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
   1066 		}
   1067 		z.SetBit(z, i, 0)
   1068 		altSetBit(z1, z1, i, 0)
   1069 		if z.Bit(i) != 0 {
   1070 			t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
   1071 		}
   1072 		if z.Cmp(z1) != 0 {
   1073 			t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
   1074 		}
   1075 		altSetBit(z1, z1, i, old)
   1076 		z.SetBit(z, i, old)
   1077 		if z.Cmp(z1) != 0 {
   1078 			t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
   1079 		}
   1080 	}
   1081 	if z.Cmp(x) != 0 {
   1082 		t.Errorf("bitset: got %s want %s", z, x)
   1083 	}
   1084 }
   1085 
   1086 var bitsetTests = []struct {
   1087 	x string
   1088 	i int
   1089 	b uint
   1090 }{
   1091 	{"0", 0, 0},
   1092 	{"0", 200, 0},
   1093 	{"1", 0, 1},
   1094 	{"1", 1, 0},
   1095 	{"-1", 0, 1},
   1096 	{"-1", 200, 1},
   1097 	{"0x2000000000000000000000000000", 108, 0},
   1098 	{"0x2000000000000000000000000000", 109, 1},
   1099 	{"0x2000000000000000000000000000", 110, 0},
   1100 	{"-0x2000000000000000000000000001", 108, 1},
   1101 	{"-0x2000000000000000000000000001", 109, 0},
   1102 	{"-0x2000000000000000000000000001", 110, 1},
   1103 }
   1104 
   1105 func TestBitSet(t *testing.T) {
   1106 	for _, test := range bitwiseTests {
   1107 		x := new(Int)
   1108 		x.SetString(test.x, 0)
   1109 		testBitset(t, x)
   1110 		x = new(Int)
   1111 		x.SetString(test.y, 0)
   1112 		testBitset(t, x)
   1113 	}
   1114 	for i, test := range bitsetTests {
   1115 		x := new(Int)
   1116 		x.SetString(test.x, 0)
   1117 		b := x.Bit(test.i)
   1118 		if b != test.b {
   1119 			t.Errorf("#%d got %v want %v", i, b, test.b)
   1120 		}
   1121 	}
   1122 	z := NewInt(1)
   1123 	z.SetBit(NewInt(0), 2, 1)
   1124 	if z.Cmp(NewInt(4)) != 0 {
   1125 		t.Errorf("destination leaked into result; got %s want 4", z)
   1126 	}
   1127 }
   1128 
   1129 func BenchmarkBitset(b *testing.B) {
   1130 	z := new(Int)
   1131 	z.SetBit(z, 512, 1)
   1132 	b.ResetTimer()
   1133 	b.StartTimer()
   1134 	for i := b.N - 1; i >= 0; i-- {
   1135 		z.SetBit(z, i&512, 1)
   1136 	}
   1137 }
   1138 
   1139 func BenchmarkBitsetNeg(b *testing.B) {
   1140 	z := NewInt(-1)
   1141 	z.SetBit(z, 512, 0)
   1142 	b.ResetTimer()
   1143 	b.StartTimer()
   1144 	for i := b.N - 1; i >= 0; i-- {
   1145 		z.SetBit(z, i&512, 0)
   1146 	}
   1147 }
   1148 
   1149 func BenchmarkBitsetOrig(b *testing.B) {
   1150 	z := new(Int)
   1151 	altSetBit(z, z, 512, 1)
   1152 	b.ResetTimer()
   1153 	b.StartTimer()
   1154 	for i := b.N - 1; i >= 0; i-- {
   1155 		altSetBit(z, z, i&512, 1)
   1156 	}
   1157 }
   1158 
   1159 func BenchmarkBitsetNegOrig(b *testing.B) {
   1160 	z := NewInt(-1)
   1161 	altSetBit(z, z, 512, 0)
   1162 	b.ResetTimer()
   1163 	b.StartTimer()
   1164 	for i := b.N - 1; i >= 0; i-- {
   1165 		altSetBit(z, z, i&512, 0)
   1166 	}
   1167 }
   1168 
   1169 // tri generates the trinomial 2**(n*2) - 2**n - 1, which is always 3 mod 4 and
   1170 // 7 mod 8, so that 2 is always a quadratic residue.
   1171 func tri(n uint) *Int {
   1172 	x := NewInt(1)
   1173 	x.Lsh(x, n)
   1174 	x2 := new(Int).Lsh(x, n)
   1175 	x2.Sub(x2, x)
   1176 	x2.Sub(x2, intOne)
   1177 	return x2
   1178 }
   1179 
   1180 func BenchmarkModSqrt225_Tonelli(b *testing.B) {
   1181 	p := tri(225)
   1182 	x := NewInt(2)
   1183 	for i := 0; i < b.N; i++ {
   1184 		x.SetUint64(2)
   1185 		x.modSqrtTonelliShanks(x, p)
   1186 	}
   1187 }
   1188 
   1189 func BenchmarkModSqrt224_3Mod4(b *testing.B) {
   1190 	p := tri(225)
   1191 	x := new(Int).SetUint64(2)
   1192 	for i := 0; i < b.N; i++ {
   1193 		x.SetUint64(2)
   1194 		x.modSqrt3Mod4Prime(x, p)
   1195 	}
   1196 }
   1197 
   1198 func BenchmarkModSqrt5430_Tonelli(b *testing.B) {
   1199 	if isRaceBuilder {
   1200 		b.Skip("skipping on race builder")
   1201 	}
   1202 	p := tri(5430)
   1203 	x := new(Int).SetUint64(2)
   1204 	for i := 0; i < b.N; i++ {
   1205 		x.SetUint64(2)
   1206 		x.modSqrtTonelliShanks(x, p)
   1207 	}
   1208 }
   1209 
   1210 func BenchmarkModSqrt5430_3Mod4(b *testing.B) {
   1211 	if isRaceBuilder {
   1212 		b.Skip("skipping on race builder")
   1213 	}
   1214 	p := tri(5430)
   1215 	x := new(Int).SetUint64(2)
   1216 	for i := 0; i < b.N; i++ {
   1217 		x.SetUint64(2)
   1218 		x.modSqrt3Mod4Prime(x, p)
   1219 	}
   1220 }
   1221 
   1222 func TestBitwise(t *testing.T) {
   1223 	x := new(Int)
   1224 	y := new(Int)
   1225 	for _, test := range bitwiseTests {
   1226 		x.SetString(test.x, 0)
   1227 		y.SetString(test.y, 0)
   1228 
   1229 		testBitFun(t, "and", (*Int).And, x, y, test.and)
   1230 		testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
   1231 		testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
   1232 		testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
   1233 		testBitFun(t, "or", (*Int).Or, x, y, test.or)
   1234 		testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
   1235 		testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
   1236 		testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
   1237 	}
   1238 }
   1239 
   1240 var notTests = []struct {
   1241 	in  string
   1242 	out string
   1243 }{
   1244 	{"0", "-1"},
   1245 	{"1", "-2"},
   1246 	{"7", "-8"},
   1247 	{"0", "-1"},
   1248 	{"-81910", "81909"},
   1249 	{
   1250 		"298472983472983471903246121093472394872319615612417471234712061",
   1251 		"-298472983472983471903246121093472394872319615612417471234712062",
   1252 	},
   1253 }
   1254 
   1255 func TestNot(t *testing.T) {
   1256 	in := new(Int)
   1257 	out := new(Int)
   1258 	expected := new(Int)
   1259 	for i, test := range notTests {
   1260 		in.SetString(test.in, 10)
   1261 		expected.SetString(test.out, 10)
   1262 		out = out.Not(in)
   1263 		if out.Cmp(expected) != 0 {
   1264 			t.Errorf("#%d: got %s want %s", i, out, expected)
   1265 		}
   1266 		out = out.Not(out)
   1267 		if out.Cmp(in) != 0 {
   1268 			t.Errorf("#%d: got %s want %s", i, out, in)
   1269 		}
   1270 	}
   1271 }
   1272 
   1273 var modInverseTests = []struct {
   1274 	element string
   1275 	modulus string
   1276 }{
   1277 	{"1234567", "458948883992"},
   1278 	{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
   1279 	{"-10", "13"}, // issue #16984
   1280 }
   1281 
   1282 func TestModInverse(t *testing.T) {
   1283 	var element, modulus, gcd, inverse Int
   1284 	one := NewInt(1)
   1285 	for i, test := range modInverseTests {
   1286 		(&element).SetString(test.element, 10)
   1287 		(&modulus).SetString(test.modulus, 10)
   1288 		(&inverse).ModInverse(&element, &modulus)
   1289 		(&inverse).Mul(&inverse, &element)
   1290 		(&inverse).Mod(&inverse, &modulus)
   1291 		if (&inverse).Cmp(one) != 0 {
   1292 			t.Errorf("#%d: failed (ee^(-1)=%s)", i, &inverse)
   1293 		}
   1294 	}
   1295 	// exhaustive test for small values
   1296 	for n := 2; n < 100; n++ {
   1297 		(&modulus).SetInt64(int64(n))
   1298 		for x := 1; x < n; x++ {
   1299 			(&element).SetInt64(int64(x))
   1300 			(&gcd).GCD(nil, nil, &element, &modulus)
   1301 			if (&gcd).Cmp(one) != 0 {
   1302 				continue
   1303 			}
   1304 			(&inverse).ModInverse(&element, &modulus)
   1305 			(&inverse).Mul(&inverse, &element)
   1306 			(&inverse).Mod(&inverse, &modulus)
   1307 			if (&inverse).Cmp(one) != 0 {
   1308 				t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
   1309 			}
   1310 		}
   1311 	}
   1312 }
   1313 
   1314 // testModSqrt is a helper for TestModSqrt,
   1315 // which checks that ModSqrt can compute a square-root of elt^2.
   1316 func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
   1317 	var sqChk, sqrtChk, sqrtsq Int
   1318 	sq.Mul(elt, elt)
   1319 	sq.Mod(sq, mod)
   1320 	z := sqrt.ModSqrt(sq, mod)
   1321 	if z != sqrt {
   1322 		t.Errorf("ModSqrt returned wrong value %s", z)
   1323 	}
   1324 
   1325 	// test ModSqrt arguments outside the range [0,mod)
   1326 	sqChk.Add(sq, mod)
   1327 	z = sqrtChk.ModSqrt(&sqChk, mod)
   1328 	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
   1329 		t.Errorf("ModSqrt returned inconsistent value %s", z)
   1330 	}
   1331 	sqChk.Sub(sq, mod)
   1332 	z = sqrtChk.ModSqrt(&sqChk, mod)
   1333 	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
   1334 		t.Errorf("ModSqrt returned inconsistent value %s", z)
   1335 	}
   1336 
   1337 	// make sure we actually got a square root
   1338 	if sqrt.Cmp(elt) == 0 {
   1339 		return true // we found the "desired" square root
   1340 	}
   1341 	sqrtsq.Mul(sqrt, sqrt) // make sure we found the "other" one
   1342 	sqrtsq.Mod(&sqrtsq, mod)
   1343 	return sq.Cmp(&sqrtsq) == 0
   1344 }
   1345 
   1346 func TestModSqrt(t *testing.T) {
   1347 	var elt, mod, modx4, sq, sqrt Int
   1348 	r := rand.New(rand.NewSource(9))
   1349 	for i, s := range primes[1:] { // skip 2, use only odd primes
   1350 		mod.SetString(s, 10)
   1351 		modx4.Lsh(&mod, 2)
   1352 
   1353 		// test a few random elements per prime
   1354 		for x := 1; x < 5; x++ {
   1355 			elt.Rand(r, &modx4)
   1356 			elt.Sub(&elt, &mod) // test range [-mod, 3*mod)
   1357 			if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
   1358 				t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
   1359 			}
   1360 		}
   1361 
   1362 		if testing.Short() && i > 2 {
   1363 			break
   1364 		}
   1365 	}
   1366 
   1367 	if testing.Short() {
   1368 		return
   1369 	}
   1370 
   1371 	// exhaustive test for small values
   1372 	for n := 3; n < 100; n++ {
   1373 		mod.SetInt64(int64(n))
   1374 		if !mod.ProbablyPrime(10) {
   1375 			continue
   1376 		}
   1377 		isSquare := make([]bool, n)
   1378 
   1379 		// test all the squares
   1380 		for x := 1; x < n; x++ {
   1381 			elt.SetInt64(int64(x))
   1382 			if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
   1383 				t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
   1384 			}
   1385 			isSquare[sq.Uint64()] = true
   1386 		}
   1387 
   1388 		// test all non-squares
   1389 		for x := 1; x < n; x++ {
   1390 			sq.SetInt64(int64(x))
   1391 			z := sqrt.ModSqrt(&sq, &mod)
   1392 			if !isSquare[x] && z != nil {
   1393 				t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
   1394 			}
   1395 		}
   1396 	}
   1397 }
   1398 
   1399 func TestJacobi(t *testing.T) {
   1400 	testCases := []struct {
   1401 		x, y   int64
   1402 		result int
   1403 	}{
   1404 		{0, 1, 1},
   1405 		{0, -1, 1},
   1406 		{1, 1, 1},
   1407 		{1, -1, 1},
   1408 		{0, 5, 0},
   1409 		{1, 5, 1},
   1410 		{2, 5, -1},
   1411 		{-2, 5, -1},
   1412 		{2, -5, -1},
   1413 		{-2, -5, 1},
   1414 		{3, 5, -1},
   1415 		{5, 5, 0},
   1416 		{-5, 5, 0},
   1417 		{6, 5, 1},
   1418 		{6, -5, 1},
   1419 		{-6, 5, 1},
   1420 		{-6, -5, -1},
   1421 	}
   1422 
   1423 	var x, y Int
   1424 
   1425 	for i, test := range testCases {
   1426 		x.SetInt64(test.x)
   1427 		y.SetInt64(test.y)
   1428 		expected := test.result
   1429 		actual := Jacobi(&x, &y)
   1430 		if actual != expected {
   1431 			t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
   1432 		}
   1433 	}
   1434 }
   1435 
   1436 func TestJacobiPanic(t *testing.T) {
   1437 	const failureMsg = "test failure"
   1438 	defer func() {
   1439 		msg := recover()
   1440 		if msg == nil || msg == failureMsg {
   1441 			panic(msg)
   1442 		}
   1443 		t.Log(msg)
   1444 	}()
   1445 	x := NewInt(1)
   1446 	y := NewInt(2)
   1447 	// Jacobi should panic when the second argument is even.
   1448 	Jacobi(x, y)
   1449 	panic(failureMsg)
   1450 }
   1451 
   1452 func TestIssue2607(t *testing.T) {
   1453 	// This code sequence used to hang.
   1454 	n := NewInt(10)
   1455 	n.Rand(rand.New(rand.NewSource(9)), n)
   1456 }
   1457 
   1458 func TestSqrt(t *testing.T) {
   1459 	root := 0
   1460 	r := new(Int)
   1461 	for i := 0; i < 10000; i++ {
   1462 		if (root+1)*(root+1) <= i {
   1463 			root++
   1464 		}
   1465 		n := NewInt(int64(i))
   1466 		r.SetInt64(-2)
   1467 		r.Sqrt(n)
   1468 		if r.Cmp(NewInt(int64(root))) != 0 {
   1469 			t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
   1470 		}
   1471 	}
   1472 
   1473 	for i := 0; i < 1000; i += 10 {
   1474 		n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10)
   1475 		r := new(Int).Sqrt(n)
   1476 		root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10)
   1477 		if r.Cmp(root) != 0 {
   1478 			t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
   1479 		}
   1480 	}
   1481 
   1482 	// Test aliasing.
   1483 	r.SetInt64(100)
   1484 	r.Sqrt(r)
   1485 	if r.Int64() != 10 {
   1486 		t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
   1487 	}
   1488 }
   1489 
   1490 func BenchmarkSqrt(b *testing.B) {
   1491 	n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10)
   1492 	b.ResetTimer()
   1493 	t := new(Int)
   1494 	for i := 0; i < b.N; i++ {
   1495 		t.Sqrt(n)
   1496 	}
   1497 }
   1498