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