libgo/go/big/int_test.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package big
   6
   7 import (
   8         "bytes"
   9         "encoding/hex"
  10         "fmt"
  11         "testing"
  12         "testing/quick"
  13 )
  14
  15
  16 func isNormalized(x *Int) bool {
  17         if len(x.abs) == 0 {
  18                 return !x.neg
  19         }
  20         // len(x.abs) > 0
  21         return x.abs[len(x.abs)-1] != 0
  22 }
  23
  24
  25 type funZZ func(z, x, y *Int) *Int
  26 type argZZ struct {
  27         z, x, y *Int
  28 }
  29
  30
  31 var sumZZ = []argZZ{
  32         {NewInt(0), NewInt(0), NewInt(0)},
  33         {NewInt(1), NewInt(1), NewInt(0)},
  34         {NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
  35         {NewInt(-1), NewInt(-1), NewInt(0)},
  36         {NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
  37         {NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
  38 }
  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
  50 func TestSignZ(t *testing.T) {
  51         var zero Int
  52         for _, a := range sumZZ {
  53                 s := a.z.Sign()
  54                 e := a.z.Cmp(&zero)
  55                 if s != e {
  56                         t.Errorf("got %d; want %d for z = %v", s, e, a.z)
  57                 }
  58         }
  59 }
  60
  61
  62 func TestSetZ(t *testing.T) {
  63         for _, a := range sumZZ {
  64                 var z Int
  65                 z.Set(a.z)
  66                 if !isNormalized(&z) {
  67                         t.Errorf("%v is not normalized", z)
  68                 }
  69                 if (&z).Cmp(a.z) != 0 {
  70                         t.Errorf("got z = %v; want %v", z, a.z)
  71                 }
  72         }
  73 }
  74
  75
  76 func TestAbsZ(t *testing.T) {
  77         var zero Int
  78         for _, a := range sumZZ {
  79                 var z Int
  80                 z.Abs(a.z)
  81                 var e Int
  82                 e.Set(a.z)
  83                 if e.Cmp(&zero) < 0 {
  84                         e.Sub(&zero, &e)
  85                 }
  86                 if z.Cmp(&e) != 0 {
  87                         t.Errorf("got z = %v; want %v", z, e)
  88                 }
  89         }
  90 }
  91
  92
  93 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
  94         var z Int
  95         f(&z, a.x, a.y)
  96         if !isNormalized(&z) {
  97                 t.Errorf("%s%v is not normalized", z, msg)
  98         }
  99         if (&z).Cmp(a.z) != 0 {
 100                 t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
 101         }
 102 }
 103
 104
 105 func TestSumZZ(t *testing.T) {
 106         AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
 107         SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
 108         for _, a := range sumZZ {
 109                 arg := a
 110                 testFunZZ(t, "AddZZ", AddZZ, arg)
 111
 112                 arg = argZZ{a.z, a.y, a.x}
 113                 testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
 114
 115                 arg = argZZ{a.x, a.z, a.y}
 116                 testFunZZ(t, "SubZZ", SubZZ, arg)
 117
 118                 arg = argZZ{a.y, a.z, a.x}
 119                 testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
 120         }
 121 }
 122
 123
 124 func TestProdZZ(t *testing.T) {
 125         MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
 126         for _, a := range prodZZ {
 127                 arg := a
 128                 testFunZZ(t, "MulZZ", MulZZ, arg)
 129
 130                 arg = argZZ{a.z, a.y, a.x}
 131                 testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
 132         }
 133 }
 134
 135
 136 // mulBytes returns x*y via grade school multiplication. Both inputs
 137 // and the result are assumed to be in big-endian representation (to
 138 // match the semantics of Int.Bytes and Int.SetBytes).
 139 func mulBytes(x, y []byte) []byte {
 140         z := make([]byte, len(x)+len(y))
 141
 142         // multiply
 143         k0 := len(z) - 1
 144         for j := len(y) - 1; j >= 0; j-- {
 145                 d := int(y[j])
 146                 if d != 0 {
 147                         k := k0
 148                         carry := 0
 149                         for i := len(x) - 1; i >= 0; i-- {
 150                                 t := int(z[k]) + int(x[i])*d + carry
 151                                 z[k], carry = byte(t), t>>8
 152                                 k--
 153                         }
 154                         z[k] = byte(carry)
 155                 }
 156                 k0--
 157         }
 158
 159         // normalize (remove leading 0's)
 160         i := 0
 161         for i < len(z) && z[i] == 0 {
 162                 i++
 163         }
 164
 165         return z[i:]
 166 }
 167
 168
 169 func checkMul(a, b []byte) bool {
 170         var x, y, z1 Int
 171         x.SetBytes(a)
 172         y.SetBytes(b)
 173         z1.Mul(&x, &y)
 174
 175         var z2 Int
 176         z2.SetBytes(mulBytes(a, b))
 177
 178         return z1.Cmp(&z2) == 0
 179 }
 180
 181
 182 func TestMul(t *testing.T) {
 183         if err := quick.Check(checkMul, nil); err != nil {
 184                 t.Error(err)
 185         }
 186 }
 187
 188
 189 var mulRangesZ = []struct {
 190         a, b int64
 191         prod string
 192 }{
 193         // entirely positive ranges are covered by mulRangesN
 194         {-1, 1, "0"},
 195         {-2, -1, "2"},
 196         {-3, -2, "6"},
 197         {-3, -1, "-6"},
 198         {1, 3, "6"},
 199         {-10, -10, "-10"},
 200         {0, -1, "1"},                      // empty range
 201         {-1, -100, "1"},                   // empty range
 202         {-1, 1, "0"},                      // range includes 0
 203         {-1e9, 0, "0"},                    // range includes 0
 204         {-1e9, 1e9, "0"},                  // range includes 0
 205         {-10, -1, "3628800"},              // 10!
 206         {-20, -2, "-2432902008176640000"}, // -20!
 207         {-99, -1,
 208                 "-933262154439441526816992388562667004907159682643816214685929" +
 209                         "638952175999932299156089414639761565182862536979208272237582" +
 210                         "511852109168640000000000000000000000", // -99!
 211         },
 212 }
 213
 214
 215 func TestMulRangeZ(t *testing.T) {
 216         var tmp Int
 217         // test entirely positive ranges
 218         for i, r := range mulRangesN {
 219                 prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
 220                 if prod != r.prod {
 221                         t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
 222                 }
 223         }
 224         // test other ranges
 225         for i, r := range mulRangesZ {
 226                 prod := tmp.MulRange(r.a, r.b).String()
 227                 if prod != r.prod {
 228                         t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
 229                 }
 230         }
 231 }
 232
 233
 234 var stringTests = []struct {
 235         in   string
 236         out  string
 237         base int
 238         val  int64
 239         ok   bool
 240 }{
 241         {in: "", ok: false},
 242         {in: "a", ok: false},
 243         {in: "z", ok: false},
 244         {in: "+", ok: false},
 245         {in: "-", ok: false},
 246         {in: "0b", ok: false},
 247         {in: "0x", ok: false},
 248         {in: "2", base: 2, ok: false},
 249         {in: "0b2", base: 0, ok: false},
 250         {in: "08", ok: false},
 251         {in: "8", base: 8, ok: false},
 252         {in: "0xg", base: 0, ok: false},
 253         {in: "g", base: 16, ok: false},
 254         {"0", "0", 0, 0, true},
 255         {"0", "0", 10, 0, true},
 256         {"0", "0", 16, 0, true},
 257         {"+0", "0", 0, 0, true},
 258         {"-0", "0", 0, 0, true},
 259         {"10", "10", 0, 10, true},
 260         {"10", "10", 10, 10, true},
 261         {"10", "10", 16, 16, true},
 262         {"-10", "-10", 16, -16, true},
 263         {"+10", "10", 16, 16, true},
 264         {"0x10", "16", 0, 16, true},
 265         {in: "0x10", base: 16, ok: false},
 266         {"-0x10", "-16", 0, -16, true},
 267         {"+0x10", "16", 0, 16, true},
 268         {"00", "0", 0, 0, true},
 269         {"0", "0", 8, 0, true},
 270         {"07", "7", 0, 7, true},
 271         {"7", "7", 8, 7, true},
 272         {"023", "19", 0, 19, true},
 273         {"23", "23", 8, 19, true},
 274         {"cafebabe", "cafebabe", 16, 0xcafebabe, true},
 275         {"0b0", "0", 0, 0, true},
 276         {"-111", "-111", 2, -7, true},
 277         {"-0b111", "-7", 0, -7, true},
 278         {"0b1001010111", "599", 0, 0x257, true},
 279         {"1001010111", "1001010111", 2, 0x257, true},
 280 }
 281
 282
 283 func format(base int) string {
 284         switch base {
 285         case 2:
 286                 return "%b"
 287         case 8:
 288                 return "%o"
 289         case 16:
 290                 return "%x"
 291         }
 292         return "%d"
 293 }
 294
 295
 296 func TestGetString(t *testing.T) {
 297         z := new(Int)
 298         for i, test := range stringTests {
 299                 if !test.ok {
 300                         continue
 301                 }
 302                 z.SetInt64(test.val)
 303
 304                 if test.base == 10 {
 305                         s := z.String()
 306                         if s != test.out {
 307                                 t.Errorf("#%da got %s; want %s", i, s, test.out)
 308                         }
 309                 }
 310
 311                 s := fmt.Sprintf(format(test.base), z)
 312                 if s != test.out {
 313                         t.Errorf("#%db got %s; want %s", i, s, test.out)
 314                 }
 315         }
 316 }
 317
 318
 319 func TestSetString(t *testing.T) {
 320         tmp := new(Int)
 321         for i, test := range stringTests {
 322                 n1, ok1 := new(Int).SetString(test.in, test.base)
 323                 n2, ok2 := tmp.SetString(test.in, test.base)
 324                 expected := NewInt(test.val)
 325                 if ok1 != test.ok || ok2 != test.ok {
 326                         t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
 327                         continue
 328                 }
 329                 if !ok1 || !ok2 {
 330                         continue
 331                 }
 332
 333                 if ok1 && !isNormalized(n1) {
 334                         t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
 335                 }
 336                 if ok2 && !isNormalized(n2) {
 337                         t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
 338                 }
 339
 340                 if n1.Cmp(expected) != 0 {
 341                         t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
 342                 }
 343                 if n2.Cmp(expected) != 0 {
 344                         t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
 345                 }
 346         }
 347 }
 348
 349
 350 // Examples from the Go Language Spec, section "Arithmetic operators"
 351 var divisionSignsTests = []struct {
 352         x, y int64
 353         q, r int64 // T-division
 354         d, m int64 // Euclidian division
 355 }{
 356         {5, 3, 1, 2, 1, 2},
 357         {-5, 3, -1, -2, -2, 1},
 358         {5, -3, -1, 2, -1, 2},
 359         {-5, -3, 1, -2, 2, 1},
 360         {1, 2, 0, 1, 0, 1},
 361         {8, 4, 2, 0, 2, 0},
 362 }
 363
 364
 365 func TestDivisionSigns(t *testing.T) {
 366         for i, test := range divisionSignsTests {
 367                 x := NewInt(test.x)
 368                 y := NewInt(test.y)
 369                 q := NewInt(test.q)
 370                 r := NewInt(test.r)
 371                 d := NewInt(test.d)
 372                 m := NewInt(test.m)
 373
 374                 q1 := new(Int).Quo(x, y)
 375                 r1 := new(Int).Rem(x, y)
 376                 if !isNormalized(q1) {
 377                         t.Errorf("#%d Quo: %v is not normalized", i, *q1)
 378                 }
 379                 if !isNormalized(r1) {
 380                         t.Errorf("#%d Rem: %v is not normalized", i, *r1)
 381                 }
 382                 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
 383                         t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
 384                 }
 385
 386                 q2, r2 := new(Int).QuoRem(x, y, new(Int))
 387                 if !isNormalized(q2) {
 388                         t.Errorf("#%d Quo: %v is not normalized", i, *q2)
 389                 }
 390                 if !isNormalized(r2) {
 391                         t.Errorf("#%d Rem: %v is not normalized", i, *r2)
 392                 }
 393                 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
 394                         t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
 395                 }
 396
 397                 d1 := new(Int).Div(x, y)
 398                 m1 := new(Int).Mod(x, y)
 399                 if !isNormalized(d1) {
 400                         t.Errorf("#%d Div: %v is not normalized", i, *d1)
 401                 }
 402                 if !isNormalized(m1) {
 403                         t.Errorf("#%d Mod: %v is not normalized", i, *m1)
 404                 }
 405                 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
 406                         t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
 407                 }
 408
 409                 d2, m2 := new(Int).DivMod(x, y, new(Int))
 410                 if !isNormalized(d2) {
 411                         t.Errorf("#%d Div: %v is not normalized", i, *d2)
 412                 }
 413                 if !isNormalized(m2) {
 414                         t.Errorf("#%d Mod: %v is not normalized", i, *m2)
 415                 }
 416                 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
 417                         t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
 418                 }
 419         }
 420 }
 421
 422
 423 func checkSetBytes(b []byte) bool {
 424         hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
 425         hex2 := hex.EncodeToString(b)
 426
 427         for len(hex1) < len(hex2) {
 428                 hex1 = "0" + hex1
 429         }
 430
 431         for len(hex1) > len(hex2) {
 432                 hex2 = "0" + hex2
 433         }
 434
 435         return hex1 == hex2
 436 }
 437
 438
 439 func TestSetBytes(t *testing.T) {
 440         if err := quick.Check(checkSetBytes, nil); err != nil {
 441                 t.Error(err)
 442         }
 443 }
 444
 445
 446 func checkBytes(b []byte) bool {
 447         b2 := new(Int).SetBytes(b).Bytes()
 448         return bytes.Compare(b, b2) == 0
 449 }
 450
 451
 452 func TestBytes(t *testing.T) {
 453         if err := quick.Check(checkSetBytes, nil); err != nil {
 454                 t.Error(err)
 455         }
 456 }
 457
 458
 459 func checkQuo(x, y []byte) bool {
 460         u := new(Int).SetBytes(x)
 461         v := new(Int).SetBytes(y)
 462
 463         if len(v.abs) == 0 {
 464                 return true
 465         }
 466
 467         r := new(Int)
 468         q, r := new(Int).QuoRem(u, v, r)
 469
 470         if r.Cmp(v) >= 0 {
 471                 return false
 472         }
 473
 474         uprime := new(Int).Set(q)
 475         uprime.Mul(uprime, v)
 476         uprime.Add(uprime, r)
 477
 478         return uprime.Cmp(u) == 0
 479 }
 480
 481
 482 var quoTests = []struct {
 483         x, y string
 484         q, r string
 485 }{
 486         {
 487                 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
 488                 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
 489                 "50911",
 490                 "1",
 491         },
 492         {
 493                 "11510768301994997771168",
 494                 "1328165573307167369775",
 495                 "8",
 496                 "885443715537658812968",
 497         },
 498 }
 499
 500
 501 func TestQuo(t *testing.T) {
 502         if err := quick.Check(checkQuo, nil); err != nil {
 503                 t.Error(err)
 504         }
 505
 506         for i, test := range quoTests {
 507                 x, _ := new(Int).SetString(test.x, 10)
 508                 y, _ := new(Int).SetString(test.y, 10)
 509                 expectedQ, _ := new(Int).SetString(test.q, 10)
 510                 expectedR, _ := new(Int).SetString(test.r, 10)
 511
 512                 r := new(Int)
 513                 q, r := new(Int).QuoRem(x, y, r)
 514
 515                 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
 516                         t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
 517                 }
 518         }
 519 }
 520
 521
 522 func TestQuoStepD6(t *testing.T) {
 523         // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
 524         // a code path which only triggers 1 in 10^{-19} cases.
 525
 526         u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
 527         v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
 528
 529         r := new(Int)
 530         q, r := new(Int).QuoRem(u, v, r)
 531         const expectedQ64 = "18446744073709551613"
 532         const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
 533         const expectedQ32 = "4294967293"
 534         const expectedR32 = "39614081266355540837921718287"
 535         if q.String() != expectedQ64 && q.String() != expectedQ32 ||
 536                 r.String() != expectedR64 && r.String() != expectedR32 {
 537                 t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
 538         }
 539 }
 540
 541
 542 var bitLenTests = []struct {
 543         in  string
 544         out int
 545 }{
 546         {"-1", 1},
 547         {"0", 0},
 548         {"1", 1},
 549         {"2", 2},
 550         {"4", 3},
 551         {"0xabc", 12},
 552         {"0x8000", 16},
 553         {"0x80000000", 32},
 554         {"0x800000000000", 48},
 555         {"0x8000000000000000", 64},
 556         {"0x80000000000000000000", 80},
 557         {"-0x4000000000000000000000", 87},
 558 }
 559
 560
 561 func TestBitLen(t *testing.T) {
 562         for i, test := range bitLenTests {
 563                 x, ok := new(Int).SetString(test.in, 0)
 564                 if !ok {
 565                         t.Errorf("#%d test input invalid: %s", i, test.in)
 566                         continue
 567                 }
 568
 569                 if n := x.BitLen(); n != test.out {
 570                         t.Errorf("#%d got %d want %d", i, n, test.out)
 571                 }
 572         }
 573 }
 574
 575
 576 var expTests = []struct {
 577         x, y, m string
 578         out     string
 579 }{
 580         {"5", "0", "", "1"},
 581         {"-5", "0", "", "-1"},
 582         {"5", "1", "", "5"},
 583         {"-5", "1", "", "-5"},
 584         {"-2", "3", "2", "0"},
 585         {"5", "2", "", "25"},
 586         {"1", "65537", "2", "1"},
 587         {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
 588         {"0x8000000000000000", "2", "6719", "4944"},
 589         {"0x8000000000000000", "3", "6719", "5447"},
 590         {"0x8000000000000000", "1000", "6719", "1603"},
 591         {"0x8000000000000000", "1000000", "6719", "3199"},
 592         {
 593                 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
 594                 "298472983472983471903246121093472394872319615612417471234712061",
 595                 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
 596                 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
 597         },
 598 }
 599
 600
 601 func TestExp(t *testing.T) {
 602         for i, test := range expTests {
 603                 x, ok1 := new(Int).SetString(test.x, 0)
 604                 y, ok2 := new(Int).SetString(test.y, 0)
 605                 out, ok3 := new(Int).SetString(test.out, 0)
 606
 607                 var ok4 bool
 608                 var m *Int
 609
 610                 if len(test.m) == 0 {
 611                         m, ok4 = nil, true
 612                 } else {
 613                         m, ok4 = new(Int).SetString(test.m, 0)
 614                 }
 615
 616                 if !ok1 || !ok2 || !ok3 || !ok4 {
 617                         t.Errorf("#%d: error in input", i)
 618                         continue
 619                 }
 620
 621                 z := y.Exp(x, y, m)
 622                 if !isNormalized(z) {
 623                         t.Errorf("#%d: %v is not normalized", i, *z)
 624                 }
 625                 if z.Cmp(out) != 0 {
 626                         t.Errorf("#%d: got %s want %s", i, z, out)
 627                 }
 628         }
 629 }
 630
 631
 632 func checkGcd(aBytes, bBytes []byte) bool {
 633         a := new(Int).SetBytes(aBytes)
 634         b := new(Int).SetBytes(bBytes)
 635
 636         x := new(Int)
 637         y := new(Int)
 638         d := new(Int)
 639
 640         GcdInt(d, x, y, a, b)
 641         x.Mul(x, a)
 642         y.Mul(y, b)
 643         x.Add(x, y)
 644
 645         return x.Cmp(d) == 0
 646 }
 647
 648
 649 var gcdTests = []struct {
 650         a, b    int64
 651         d, x, y int64
 652 }{
 653         {120, 23, 1, -9, 47},
 654 }
 655
 656
 657 func TestGcd(t *testing.T) {
 658         for i, test := range gcdTests {
 659                 a := NewInt(test.a)
 660                 b := NewInt(test.b)
 661
 662                 x := new(Int)
 663                 y := new(Int)
 664                 d := new(Int)
 665
 666                 expectedX := NewInt(test.x)
 667                 expectedY := NewInt(test.y)
 668                 expectedD := NewInt(test.d)
 669
 670                 GcdInt(d, x, y, a, b)
 671
 672                 if expectedX.Cmp(x) != 0 ||
 673                         expectedY.Cmp(y) != 0 ||
 674                         expectedD.Cmp(d) != 0 {
 675                         t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x, y, d, expectedX, expectedY, expectedD)
 676                 }
 677         }
 678
 679         quick.Check(checkGcd, nil)
 680 }
 681
 682
 683 var primes = []string{
 684         "2",
 685         "3",
 686         "5",
 687         "7",
 688         "11",
 689
 690         "13756265695458089029",
 691         "13496181268022124907",
 692         "10953742525620032441",
 693         "17908251027575790097",
 694
 695         // http://code.google.com/p/go/issues/detail?id=638
 696         "18699199384836356663",
 697
 698         "98920366548084643601728869055592650835572950932266967461790948584315647051443",
 699         "94560208308847015747498523884063394671606671904944666360068158221458669711639",
 700
 701         // http://primes.utm.edu/lists/small/small3.html
 702         "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
 703         "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
 704         "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
 705         "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
 706 }
 707
 708
 709 var composites = []string{
 710         "21284175091214687912771199898307297748211672914763848041968395774954376176754",
 711         "6084766654921918907427900243509372380954290099172559290432744450051395395951",
 712         "84594350493221918389213352992032324280367711247940675652888030554255915464401",
 713         "82793403787388584738507275144194252681",
 714 }
 715
 716
 717 func TestProbablyPrime(t *testing.T) {
 718         for i, s := range primes {
 719                 p, _ := new(Int).SetString(s, 10)
 720                 if !ProbablyPrime(p, 20) {
 721                         t.Errorf("#%d prime found to be non-prime (%s)", i, s)
 722                 }
 723         }
 724
 725         for i, s := range composites {
 726                 c, _ := new(Int).SetString(s, 10)
 727                 if ProbablyPrime(c, 20) {
 728                         t.Errorf("#%d composite found to be prime (%s)", i, s)
 729                 }
 730         }
 731 }
 732
 733
 734 type intShiftTest struct {
 735         in    string
 736         shift uint
 737         out   string
 738 }
 739
 740
 741 var rshTests = []intShiftTest{
 742         {"0", 0, "0"},
 743         {"-0", 0, "0"},
 744         {"0", 1, "0"},
 745         {"0", 2, "0"},
 746         {"1", 0, "1"},
 747         {"1", 1, "0"},
 748         {"1", 2, "0"},
 749         {"2", 0, "2"},
 750         {"2", 1, "1"},
 751         {"-1", 0, "-1"},
 752         {"-1", 1, "-1"},
 753         {"-1", 10, "-1"},
 754         {"-100", 2, "-25"},
 755         {"-100", 3, "-13"},
 756         {"-100", 100, "-1"},
 757         {"4294967296", 0, "4294967296"},
 758         {"4294967296", 1, "2147483648"},
 759         {"4294967296", 2, "1073741824"},
 760         {"18446744073709551616", 0, "18446744073709551616"},
 761         {"18446744073709551616", 1, "9223372036854775808"},
 762         {"18446744073709551616", 2, "4611686018427387904"},
 763         {"18446744073709551616", 64, "1"},
 764         {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
 765         {"340282366920938463463374607431768211456", 128, "1"},
 766 }
 767
 768
 769 func TestRsh(t *testing.T) {
 770         for i, test := range rshTests {
 771                 in, _ := new(Int).SetString(test.in, 10)
 772                 expected, _ := new(Int).SetString(test.out, 10)
 773                 out := new(Int).Rsh(in, test.shift)
 774
 775                 if !isNormalized(out) {
 776                         t.Errorf("#%d: %v is not normalized", i, *out)
 777                 }
 778                 if out.Cmp(expected) != 0 {
 779                         t.Errorf("#%d: got %s want %s", i, out, expected)
 780                 }
 781         }
 782 }
 783
 784
 785 func TestRshSelf(t *testing.T) {
 786         for i, test := range rshTests {
 787                 z, _ := new(Int).SetString(test.in, 10)
 788                 expected, _ := new(Int).SetString(test.out, 10)
 789                 z.Rsh(z, test.shift)
 790
 791                 if !isNormalized(z) {
 792                         t.Errorf("#%d: %v is not normalized", i, *z)
 793                 }
 794                 if z.Cmp(expected) != 0 {
 795                         t.Errorf("#%d: got %s want %s", i, z, expected)
 796                 }
 797         }
 798 }
 799
 800
 801 var lshTests = []intShiftTest{
 802         {"0", 0, "0"},
 803         {"0", 1, "0"},
 804         {"0", 2, "0"},
 805         {"1", 0, "1"},
 806         {"1", 1, "2"},
 807         {"1", 2, "4"},
 808         {"2", 0, "2"},
 809         {"2", 1, "4"},
 810         {"2", 2, "8"},
 811         {"-87", 1, "-174"},
 812         {"4294967296", 0, "4294967296"},
 813         {"4294967296", 1, "8589934592"},
 814         {"4294967296", 2, "17179869184"},
 815         {"18446744073709551616", 0, "18446744073709551616"},
 816         {"9223372036854775808", 1, "18446744073709551616"},
 817         {"4611686018427387904", 2, "18446744073709551616"},
 818         {"1", 64, "18446744073709551616"},
 819         {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
 820         {"1", 128, "340282366920938463463374607431768211456"},
 821 }
 822
 823
 824 func TestLsh(t *testing.T) {
 825         for i, test := range lshTests {
 826                 in, _ := new(Int).SetString(test.in, 10)
 827                 expected, _ := new(Int).SetString(test.out, 10)
 828                 out := new(Int).Lsh(in, test.shift)
 829
 830                 if !isNormalized(out) {
 831                         t.Errorf("#%d: %v is not normalized", i, *out)
 832                 }
 833                 if out.Cmp(expected) != 0 {
 834                         t.Errorf("#%d: got %s want %s", i, out, expected)
 835                 }
 836         }
 837 }
 838
 839
 840 func TestLshSelf(t *testing.T) {
 841         for i, test := range lshTests {
 842                 z, _ := new(Int).SetString(test.in, 10)
 843                 expected, _ := new(Int).SetString(test.out, 10)
 844                 z.Lsh(z, test.shift)
 845
 846                 if !isNormalized(z) {
 847                         t.Errorf("#%d: %v is not normalized", i, *z)
 848                 }
 849                 if z.Cmp(expected) != 0 {
 850                         t.Errorf("#%d: got %s want %s", i, z, expected)
 851                 }
 852         }
 853 }
 854
 855
 856 func TestLshRsh(t *testing.T) {
 857         for i, test := range rshTests {
 858                 in, _ := new(Int).SetString(test.in, 10)
 859                 out := new(Int).Lsh(in, test.shift)
 860                 out = out.Rsh(out, test.shift)
 861
 862                 if !isNormalized(out) {
 863                         t.Errorf("#%d: %v is not normalized", i, *out)
 864                 }
 865                 if in.Cmp(out) != 0 {
 866                         t.Errorf("#%d: got %s want %s", i, out, in)
 867                 }
 868         }
 869         for i, test := range lshTests {
 870                 in, _ := new(Int).SetString(test.in, 10)
 871                 out := new(Int).Lsh(in, test.shift)
 872                 out.Rsh(out, test.shift)
 873
 874                 if !isNormalized(out) {
 875                         t.Errorf("#%d: %v is not normalized", i, *out)
 876                 }
 877                 if in.Cmp(out) != 0 {
 878                         t.Errorf("#%d: got %s want %s", i, out, in)
 879                 }
 880         }
 881 }
 882
 883
 884 var int64Tests = []int64{
 885         0,
 886         1,
 887         -1,
 888         4294967295,
 889         -4294967295,
 890         4294967296,
 891         -4294967296,
 892         9223372036854775807,
 893         -9223372036854775807,
 894         -9223372036854775808,
 895 }
 896
 897
 898 func TestInt64(t *testing.T) {
 899         for i, testVal := range int64Tests {
 900                 in := NewInt(testVal)
 901                 out := in.Int64()
 902
 903                 if out != testVal {
 904                         t.Errorf("#%d got %d want %d", i, out, testVal)
 905                 }
 906         }
 907 }
 908
 909
 910 var bitwiseTests = []struct {
 911         x, y                 string
 912         and, or, xor, andNot string
 913 }{
 914         {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
 915         {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
 916         {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
 917         {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
 918         {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
 919         {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
 920         {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
 921         {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
 922         {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
 923         {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
 924         {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
 925         {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
 926         {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
 927         {
 928                 "0x1000009dc6e3d9822cba04129bcbe3401",
 929                 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
 930                 "0x1000001186210100001000009048c2001",
 931                 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
 932                 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
 933                 "0x8c40c2d8822caa04120b8321400",
 934         },
 935         {
 936                 "0x1000009dc6e3d9822cba04129bcbe3401",
 937                 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
 938                 "0x8c40c2d8822caa04120b8321401",
 939                 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
 940                 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
 941                 "0x1000001186210100001000009048c2000",
 942         },
 943         {
 944                 "-0x1000009dc6e3d9822cba04129bcbe3401",
 945                 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
 946                 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
 947                 "-0x1000001186210100001000009048c2001",
 948                 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
 949                 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
 950         },
 951 }
 952
 953
 954 type bitFun func(z, x, y *Int) *Int
 955
 956 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
 957         expected := new(Int)
 958         expected.SetString(exp, 0)
 959
 960         out := f(new(Int), x, y)
 961         if out.Cmp(expected) != 0 {
 962                 t.Errorf("%s: got %s want %s", msg, out, expected)
 963         }
 964 }
 965
 966
 967 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
 968         self := new(Int)
 969         self.Set(x)
 970         expected := new(Int)
 971         expected.SetString(exp, 0)
 972
 973         self = f(self, self, y)
 974         if self.Cmp(expected) != 0 {
 975                 t.Errorf("%s: got %s want %s", msg, self, expected)
 976         }
 977 }
 978
 979
 980 func TestBitwise(t *testing.T) {
 981         x := new(Int)
 982         y := new(Int)
 983         for _, test := range bitwiseTests {
 984                 x.SetString(test.x, 0)
 985                 y.SetString(test.y, 0)
 986
 987                 testBitFun(t, "and", (*Int).And, x, y, test.and)
 988                 testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
 989                 testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
 990                 testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
 991                 testBitFun(t, "or", (*Int).Or, x, y, test.or)
 992                 testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
 993                 testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
 994                 testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
 995         }
 996 }
 997
 998
 999 var notTests = []struct {
1000         in  string
1001         out string
1002 }{
1003         {"0", "-1"},
1004         {"1", "-2"},
1005         {"7", "-8"},
1006         {"0", "-1"},
1007         {"-81910", "81909"},
1008         {
1009                 "298472983472983471903246121093472394872319615612417471234712061",
1010                 "-298472983472983471903246121093472394872319615612417471234712062",
1011         },
1012 }
1013
1014 func TestNot(t *testing.T) {
1015         in := new(Int)
1016         out := new(Int)
1017         expected := new(Int)
1018         for i, test := range notTests {
1019                 in.SetString(test.in, 10)
1020                 expected.SetString(test.out, 10)
1021                 out = out.Not(in)
1022                 if out.Cmp(expected) != 0 {
1023                         t.Errorf("#%d: got %s want %s", i, out, expected)
1024                 }
1025                 out = out.Not(out)
1026                 if out.Cmp(in) != 0 {
1027                         t.Errorf("#%d: got %s want %s", i, out, in)
1028                 }
1029         }
1030 }
1031
1032
1033 var modInverseTests = []struct {
1034         element string
1035         prime   string
1036 }{
1037         {"1", "7"},
1038         {"1", "13"},
1039         {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1040 }
1041
1042 func TestModInverse(t *testing.T) {
1043         var element, prime Int
1044         one := NewInt(1)
1045         for i, test := range modInverseTests {
1046                 (&element).SetString(test.element, 10)
1047                 (&prime).SetString(test.prime, 10)
1048                 inverse := new(Int).ModInverse(&element, &prime)
1049                 inverse.Mul(inverse, &element)
1050                 inverse.Mod(inverse, &prime)
1051                 if inverse.Cmp(one) != 0 {
1052                         t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
1053                 }
1054         }
1055 }