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