libgo/go/math/big/int_test.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package big
   6
   7 import (
   8         "bytes"
   9         "encoding/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 var stringTests = []struct {
 223         in   string
 224         out  string
 225         base int
 226         val  int64
 227         ok   bool
 228 }{
 229         {in: "", ok: false},
 230         {in: "a", ok: false},
 231         {in: "z", ok: false},
 232         {in: "+", ok: false},
 233         {in: "-", ok: false},
 234         {in: "0b", ok: false},
 235         {in: "0x", ok: false},
 236         {in: "2", base: 2, ok: false},
 237         {in: "0b2", base: 0, ok: false},
 238         {in: "08", ok: false},
 239         {in: "8", base: 8, ok: false},
 240         {in: "0xg", base: 0, ok: false},
 241         {in: "g", base: 16, ok: false},
 242         {"0", "0", 0, 0, true},
 243         {"0", "0", 10, 0, true},
 244         {"0", "0", 16, 0, true},
 245         {"+0", "0", 0, 0, true},
 246         {"-0", "0", 0, 0, true},
 247         {"10", "10", 0, 10, true},
 248         {"10", "10", 10, 10, true},
 249         {"10", "10", 16, 16, true},
 250         {"-10", "-10", 16, -16, true},
 251         {"+10", "10", 16, 16, true},
 252         {"0x10", "16", 0, 16, true},
 253         {in: "0x10", base: 16, ok: false},
 254         {"-0x10", "-16", 0, -16, true},
 255         {"+0x10", "16", 0, 16, true},
 256         {"00", "0", 0, 0, true},
 257         {"0", "0", 8, 0, true},
 258         {"07", "7", 0, 7, true},
 259         {"7", "7", 8, 7, true},
 260         {"023", "19", 0, 19, true},
 261         {"23", "23", 8, 19, true},
 262         {"cafebabe", "cafebabe", 16, 0xcafebabe, true},
 263         {"0b0", "0", 0, 0, true},
 264         {"-111", "-111", 2, -7, true},
 265         {"-0b111", "-7", 0, -7, true},
 266         {"0b1001010111", "599", 0, 0x257, true},
 267         {"1001010111", "1001010111", 2, 0x257, true},
 268 }
 269
 270 func format(base int) string {
 271         switch base {
 272         case 2:
 273                 return "%b"
 274         case 8:
 275                 return "%o"
 276         case 16:
 277                 return "%x"
 278         }
 279         return "%d"
 280 }
 281
 282 func TestGetString(t *testing.T) {
 283         z := new(Int)
 284         for i, test := range stringTests {
 285                 if !test.ok {
 286                         continue
 287                 }
 288                 z.SetInt64(test.val)
 289
 290                 if test.base == 10 {
 291                         s := z.String()
 292                         if s != test.out {
 293                                 t.Errorf("#%da got %s; want %s", i, s, test.out)
 294                         }
 295                 }
 296
 297                 s := fmt.Sprintf(format(test.base), z)
 298                 if s != test.out {
 299                         t.Errorf("#%db got %s; want %s", i, s, test.out)
 300                 }
 301         }
 302 }
 303
 304 func TestSetString(t *testing.T) {
 305         tmp := new(Int)
 306         for i, test := range stringTests {
 307                 // initialize to a non-zero value so that issues with parsing
 308                 // 0 are detected
 309                 tmp.SetInt64(1234567890)
 310                 n1, ok1 := new(Int).SetString(test.in, test.base)
 311                 n2, ok2 := tmp.SetString(test.in, test.base)
 312                 expected := NewInt(test.val)
 313                 if ok1 != test.ok || ok2 != test.ok {
 314                         t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
 315                         continue
 316                 }
 317                 if !ok1 {
 318                         if n1 != nil {
 319                                 t.Errorf("#%d (input '%s') n1 != nil", i, test.in)
 320                         }
 321                         continue
 322                 }
 323                 if !ok2 {
 324                         if n2 != nil {
 325                                 t.Errorf("#%d (input '%s') n2 != nil", i, test.in)
 326                         }
 327                         continue
 328                 }
 329
 330                 if ok1 && !isNormalized(n1) {
 331                         t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
 332                 }
 333                 if ok2 && !isNormalized(n2) {
 334                         t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
 335                 }
 336
 337                 if n1.Cmp(expected) != 0 {
 338                         t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
 339                 }
 340                 if n2.Cmp(expected) != 0 {
 341                         t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
 342                 }
 343         }
 344 }
 345
 346 var formatTests = []struct {
 347         input  string
 348         format string
 349         output string
 350 }{
 351         {"<nil>", "%x", "<nil>"},
 352         {"<nil>", "%#x", "<nil>"},
 353         {"<nil>", "%#y", "%!y(big.Int=<nil>)"},
 354
 355         {"10", "%b", "1010"},
 356         {"10", "%o", "12"},
 357         {"10", "%d", "10"},
 358         {"10", "%v", "10"},
 359         {"10", "%x", "a"},
 360         {"10", "%X", "A"},
 361         {"-10", "%X", "-A"},
 362         {"10", "%y", "%!y(big.Int=10)"},
 363         {"-10", "%y", "%!y(big.Int=-10)"},
 364
 365         {"10", "%#b", "1010"},
 366         {"10", "%#o", "012"},
 367         {"10", "%#d", "10"},
 368         {"10", "%#v", "10"},
 369         {"10", "%#x", "0xa"},
 370         {"10", "%#X", "0XA"},
 371         {"-10", "%#X", "-0XA"},
 372         {"10", "%#y", "%!y(big.Int=10)"},
 373         {"-10", "%#y", "%!y(big.Int=-10)"},
 374
 375         {"1234", "%d", "1234"},
 376         {"1234", "%3d", "1234"},
 377         {"1234", "%4d", "1234"},
 378         {"-1234", "%d", "-1234"},
 379         {"1234", "% 5d", " 1234"},
 380         {"1234", "%+5d", "+1234"},
 381         {"1234", "%-5d", "1234 "},
 382         {"1234", "%x", "4d2"},
 383         {"1234", "%X", "4D2"},
 384         {"-1234", "%3x", "-4d2"},
 385         {"-1234", "%4x", "-4d2"},
 386         {"-1234", "%5x", " -4d2"},
 387         {"-1234", "%-5x", "-4d2 "},
 388         {"1234", "%03d", "1234"},
 389         {"1234", "%04d", "1234"},
 390         {"1234", "%05d", "01234"},
 391         {"1234", "%06d", "001234"},
 392         {"-1234", "%06d", "-01234"},
 393         {"1234", "%+06d", "+01234"},
 394         {"1234", "% 06d", " 01234"},
 395         {"1234", "%-6d", "1234  "},
 396         {"1234", "%-06d", "1234  "},
 397         {"-1234", "%-06d", "-1234 "},
 398
 399         {"1234", "%.3d", "1234"},
 400         {"1234", "%.4d", "1234"},
 401         {"1234", "%.5d", "01234"},
 402         {"1234", "%.6d", "001234"},
 403         {"-1234", "%.3d", "-1234"},
 404         {"-1234", "%.4d", "-1234"},
 405         {"-1234", "%.5d", "-01234"},
 406         {"-1234", "%.6d", "-001234"},
 407
 408         {"1234", "%8.3d", "    1234"},
 409         {"1234", "%8.4d", "    1234"},
 410         {"1234", "%8.5d", "   01234"},
 411         {"1234", "%8.6d", "  001234"},
 412         {"-1234", "%8.3d", "   -1234"},
 413         {"-1234", "%8.4d", "   -1234"},
 414         {"-1234", "%8.5d", "  -01234"},
 415         {"-1234", "%8.6d", " -001234"},
 416
 417         {"1234", "%+8.3d", "   +1234"},
 418         {"1234", "%+8.4d", "   +1234"},
 419         {"1234", "%+8.5d", "  +01234"},
 420         {"1234", "%+8.6d", " +001234"},
 421         {"-1234", "%+8.3d", "   -1234"},
 422         {"-1234", "%+8.4d", "   -1234"},
 423         {"-1234", "%+8.5d", "  -01234"},
 424         {"-1234", "%+8.6d", " -001234"},
 425
 426         {"1234", "% 8.3d", "    1234"},
 427         {"1234", "% 8.4d", "    1234"},
 428         {"1234", "% 8.5d", "   01234"},
 429         {"1234", "% 8.6d", "  001234"},
 430         {"-1234", "% 8.3d", "   -1234"},
 431         {"-1234", "% 8.4d", "   -1234"},
 432         {"-1234", "% 8.5d", "  -01234"},
 433         {"-1234", "% 8.6d", " -001234"},
 434
 435         {"1234", "%.3x", "4d2"},
 436         {"1234", "%.4x", "04d2"},
 437         {"1234", "%.5x", "004d2"},
 438         {"1234", "%.6x", "0004d2"},
 439         {"-1234", "%.3x", "-4d2"},
 440         {"-1234", "%.4x", "-04d2"},
 441         {"-1234", "%.5x", "-004d2"},
 442         {"-1234", "%.6x", "-0004d2"},
 443
 444         {"1234", "%8.3x", "     4d2"},
 445         {"1234", "%8.4x", "    04d2"},
 446         {"1234", "%8.5x", "   004d2"},
 447         {"1234", "%8.6x", "  0004d2"},
 448         {"-1234", "%8.3x", "    -4d2"},
 449         {"-1234", "%8.4x", "   -04d2"},
 450         {"-1234", "%8.5x", "  -004d2"},
 451         {"-1234", "%8.6x", " -0004d2"},
 452
 453         {"1234", "%+8.3x", "    +4d2"},
 454         {"1234", "%+8.4x", "   +04d2"},
 455         {"1234", "%+8.5x", "  +004d2"},
 456         {"1234", "%+8.6x", " +0004d2"},
 457         {"-1234", "%+8.3x", "    -4d2"},
 458         {"-1234", "%+8.4x", "   -04d2"},
 459         {"-1234", "%+8.5x", "  -004d2"},
 460         {"-1234", "%+8.6x", " -0004d2"},
 461
 462         {"1234", "% 8.3x", "     4d2"},
 463         {"1234", "% 8.4x", "    04d2"},
 464         {"1234", "% 8.5x", "   004d2"},
 465         {"1234", "% 8.6x", "  0004d2"},
 466         {"1234", "% 8.7x", " 00004d2"},
 467         {"1234", "% 8.8x", " 000004d2"},
 468         {"-1234", "% 8.3x", "    -4d2"},
 469         {"-1234", "% 8.4x", "   -04d2"},
 470         {"-1234", "% 8.5x", "  -004d2"},
 471         {"-1234", "% 8.6x", " -0004d2"},
 472         {"-1234", "% 8.7x", "-00004d2"},
 473         {"-1234", "% 8.8x", "-000004d2"},
 474
 475         {"1234", "%-8.3d", "1234    "},
 476         {"1234", "%-8.4d", "1234    "},
 477         {"1234", "%-8.5d", "01234   "},
 478         {"1234", "%-8.6d", "001234  "},
 479         {"1234", "%-8.7d", "0001234 "},
 480         {"1234", "%-8.8d", "00001234"},
 481         {"-1234", "%-8.3d", "-1234   "},
 482         {"-1234", "%-8.4d", "-1234   "},
 483         {"-1234", "%-8.5d", "-01234  "},
 484         {"-1234", "%-8.6d", "-001234 "},
 485         {"-1234", "%-8.7d", "-0001234"},
 486         {"-1234", "%-8.8d", "-00001234"},
 487
 488         {"16777215", "%b", "111111111111111111111111"}, // 2**24 - 1
 489
 490         {"0", "%.d", ""},
 491         {"0", "%.0d", ""},
 492         {"0", "%3.d", ""},
 493 }
 494
 495 func TestFormat(t *testing.T) {
 496         for i, test := range formatTests {
 497                 var x *Int
 498                 if test.input != "<nil>" {
 499                         var ok bool
 500                         x, ok = new(Int).SetString(test.input, 0)
 501                         if !ok {
 502                                 t.Errorf("#%d failed reading input %s", i, test.input)
 503                         }
 504                 }
 505                 output := fmt.Sprintf(test.format, x)
 506                 if output != test.output {
 507                         t.Errorf("#%d got %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, test.output)
 508                 }
 509         }
 510 }
 511
 512 var scanTests = []struct {
 513         input     string
 514         format    string
 515         output    string
 516         remaining int
 517 }{
 518         {"1010", "%b", "10", 0},
 519         {"0b1010", "%v", "10", 0},
 520         {"12", "%o", "10", 0},
 521         {"012", "%v", "10", 0},
 522         {"10", "%d", "10", 0},
 523         {"10", "%v", "10", 0},
 524         {"a", "%x", "10", 0},
 525         {"0xa", "%v", "10", 0},
 526         {"A", "%X", "10", 0},
 527         {"-A", "%X", "-10", 0},
 528         {"+0b1011001", "%v", "89", 0},
 529         {"0xA", "%v", "10", 0},
 530         {"0 ", "%v", "0", 1},
 531         {"2+3", "%v", "2", 2},
 532         {"0XABC 12", "%v", "2748", 3},
 533 }
 534
 535 func TestScan(t *testing.T) {
 536         var buf bytes.Buffer
 537         for i, test := range scanTests {
 538                 x := new(Int)
 539                 buf.Reset()
 540                 buf.WriteString(test.input)
 541                 if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
 542                         t.Errorf("#%d error: %s", i, err)
 543                 }
 544                 if x.String() != test.output {
 545                         t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
 546                 }
 547                 if buf.Len() != test.remaining {
 548                         t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
 549                 }
 550         }
 551 }
 552
 553 // Examples from the Go Language Spec, section "Arithmetic operators"
 554 var divisionSignsTests = []struct {
 555         x, y int64
 556         q, r int64 // T-division
 557         d, m int64 // Euclidian division
 558 }{
 559         {5, 3, 1, 2, 1, 2},
 560         {-5, 3, -1, -2, -2, 1},
 561         {5, -3, -1, 2, -1, 2},
 562         {-5, -3, 1, -2, 2, 1},
 563         {1, 2, 0, 1, 0, 1},
 564         {8, 4, 2, 0, 2, 0},
 565 }
 566
 567 func TestDivisionSigns(t *testing.T) {
 568         for i, test := range divisionSignsTests {
 569                 x := NewInt(test.x)
 570                 y := NewInt(test.y)
 571                 q := NewInt(test.q)
 572                 r := NewInt(test.r)
 573                 d := NewInt(test.d)
 574                 m := NewInt(test.m)
 575
 576                 q1 := new(Int).Quo(x, y)
 577                 r1 := new(Int).Rem(x, y)
 578                 if !isNormalized(q1) {
 579                         t.Errorf("#%d Quo: %v is not normalized", i, *q1)
 580                 }
 581                 if !isNormalized(r1) {
 582                         t.Errorf("#%d Rem: %v is not normalized", i, *r1)
 583                 }
 584                 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
 585                         t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
 586                 }
 587
 588                 q2, r2 := new(Int).QuoRem(x, y, new(Int))
 589                 if !isNormalized(q2) {
 590                         t.Errorf("#%d Quo: %v is not normalized", i, *q2)
 591                 }
 592                 if !isNormalized(r2) {
 593                         t.Errorf("#%d Rem: %v is not normalized", i, *r2)
 594                 }
 595                 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
 596                         t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
 597                 }
 598
 599                 d1 := new(Int).Div(x, y)
 600                 m1 := new(Int).Mod(x, y)
 601                 if !isNormalized(d1) {
 602                         t.Errorf("#%d Div: %v is not normalized", i, *d1)
 603                 }
 604                 if !isNormalized(m1) {
 605                         t.Errorf("#%d Mod: %v is not normalized", i, *m1)
 606                 }
 607                 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
 608                         t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
 609                 }
 610
 611                 d2, m2 := new(Int).DivMod(x, y, new(Int))
 612                 if !isNormalized(d2) {
 613                         t.Errorf("#%d Div: %v is not normalized", i, *d2)
 614                 }
 615                 if !isNormalized(m2) {
 616                         t.Errorf("#%d Mod: %v is not normalized", i, *m2)
 617                 }
 618                 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
 619                         t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
 620                 }
 621         }
 622 }
 623
 624 func checkSetBytes(b []byte) bool {
 625         hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
 626         hex2 := hex.EncodeToString(b)
 627
 628         for len(hex1) < len(hex2) {
 629                 hex1 = "0" + hex1
 630         }
 631
 632         for len(hex1) > len(hex2) {
 633                 hex2 = "0" + hex2
 634         }
 635
 636         return hex1 == hex2
 637 }
 638
 639 func TestSetBytes(t *testing.T) {
 640         if err := quick.Check(checkSetBytes, nil); err != nil {
 641                 t.Error(err)
 642         }
 643 }
 644
 645 func checkBytes(b []byte) bool {
 646         b2 := new(Int).SetBytes(b).Bytes()
 647         return bytes.Equal(b, b2)
 648 }
 649
 650 func TestBytes(t *testing.T) {
 651         if err := quick.Check(checkSetBytes, nil); err != nil {
 652                 t.Error(err)
 653         }
 654 }
 655
 656 func checkQuo(x, y []byte) bool {
 657         u := new(Int).SetBytes(x)
 658         v := new(Int).SetBytes(y)
 659
 660         if len(v.abs) == 0 {
 661                 return true
 662         }
 663
 664         r := new(Int)
 665         q, r := new(Int).QuoRem(u, v, r)
 666
 667         if r.Cmp(v) >= 0 {
 668                 return false
 669         }
 670
 671         uprime := new(Int).Set(q)
 672         uprime.Mul(uprime, v)
 673         uprime.Add(uprime, r)
 674
 675         return uprime.Cmp(u) == 0
 676 }
 677
 678 var quoTests = []struct {
 679         x, y string
 680         q, r string
 681 }{
 682         {
 683                 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
 684                 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
 685                 "50911",
 686                 "1",
 687         },
 688         {
 689                 "11510768301994997771168",
 690                 "1328165573307167369775",
 691                 "8",
 692                 "885443715537658812968",
 693         },
 694 }
 695
 696 func TestQuo(t *testing.T) {
 697         if err := quick.Check(checkQuo, nil); err != nil {
 698                 t.Error(err)
 699         }
 700
 701         for i, test := range quoTests {
 702                 x, _ := new(Int).SetString(test.x, 10)
 703                 y, _ := new(Int).SetString(test.y, 10)
 704                 expectedQ, _ := new(Int).SetString(test.q, 10)
 705                 expectedR, _ := new(Int).SetString(test.r, 10)
 706
 707                 r := new(Int)
 708                 q, r := new(Int).QuoRem(x, y, r)
 709
 710                 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
 711                         t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
 712                 }
 713         }
 714 }
 715
 716 func TestQuoStepD6(t *testing.T) {
 717         // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
 718         // a code path which only triggers 1 in 10^{-19} cases.
 719
 720         u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
 721         v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
 722
 723         r := new(Int)
 724         q, r := new(Int).QuoRem(u, v, r)
 725         const expectedQ64 = "18446744073709551613"
 726         const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
 727         const expectedQ32 = "4294967293"
 728         const expectedR32 = "39614081266355540837921718287"
 729         if q.String() != expectedQ64 && q.String() != expectedQ32 ||
 730                 r.String() != expectedR64 && r.String() != expectedR32 {
 731                 t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
 732         }
 733 }
 734
 735 var bitLenTests = []struct {
 736         in  string
 737         out int
 738 }{
 739         {"-1", 1},
 740         {"0", 0},
 741         {"1", 1},
 742         {"2", 2},
 743         {"4", 3},
 744         {"0xabc", 12},
 745         {"0x8000", 16},
 746         {"0x80000000", 32},
 747         {"0x800000000000", 48},
 748         {"0x8000000000000000", 64},
 749         {"0x80000000000000000000", 80},
 750         {"-0x4000000000000000000000", 87},
 751 }
 752
 753 func TestBitLen(t *testing.T) {
 754         for i, test := range bitLenTests {
 755                 x, ok := new(Int).SetString(test.in, 0)
 756                 if !ok {
 757                         t.Errorf("#%d test input invalid: %s", i, test.in)
 758                         continue
 759                 }
 760
 761                 if n := x.BitLen(); n != test.out {
 762                         t.Errorf("#%d got %d want %d", i, n, test.out)
 763                 }
 764         }
 765 }
 766
 767 var expTests = []struct {
 768         x, y, m string
 769         out     string
 770 }{
 771         // y <= 0
 772         {"0", "0", "", "1"},
 773         {"1", "0", "", "1"},
 774         {"-10", "0", "", "1"},
 775         {"1234", "-1", "", "1"},
 776
 777         // m == 1
 778         {"0", "0", "1", "0"},
 779         {"1", "0", "1", "0"},
 780         {"-10", "0", "1", "0"},
 781         {"1234", "-1", "1", "0"},
 782
 783         // misc
 784         {"5", "-7", "", "1"},
 785         {"-5", "-7", "", "1"},
 786         {"5", "0", "", "1"},
 787         {"-5", "0", "", "1"},
 788         {"5", "1", "", "5"},
 789         {"-5", "1", "", "-5"},
 790         {"-2", "3", "2", "0"},
 791         {"5", "2", "", "25"},
 792         {"1", "65537", "2", "1"},
 793         {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
 794         {"0x8000000000000000", "2", "6719", "4944"},
 795         {"0x8000000000000000", "3", "6719", "5447"},
 796         {"0x8000000000000000", "1000", "6719", "1603"},
 797         {"0x8000000000000000", "1000000", "6719", "3199"},
 798         {"0x8000000000000000", "-1000000", "6719", "1"},
 799         {
 800                 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
 801                 "298472983472983471903246121093472394872319615612417471234712061",
 802                 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
 803                 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
 804         },
 805 }
 806
 807 func TestExp(t *testing.T) {
 808         for i, test := range expTests {
 809                 x, ok1 := new(Int).SetString(test.x, 0)
 810                 y, ok2 := new(Int).SetString(test.y, 0)
 811                 out, ok3 := new(Int).SetString(test.out, 0)
 812
 813                 var ok4 bool
 814                 var m *Int
 815
 816                 if len(test.m) == 0 {
 817                         m, ok4 = nil, true
 818                 } else {
 819                         m, ok4 = new(Int).SetString(test.m, 0)
 820                 }
 821
 822                 if !ok1 || !ok2 || !ok3 || !ok4 {
 823                         t.Errorf("#%d: error in input", i)
 824                         continue
 825                 }
 826
 827                 z1 := new(Int).Exp(x, y, m)
 828                 if !isNormalized(z1) {
 829                         t.Errorf("#%d: %v is not normalized", i, *z1)
 830                 }
 831                 if z1.Cmp(out) != 0 {
 832                         t.Errorf("#%d: got %s want %s", i, z1, out)
 833                 }
 834
 835                 if m == nil {
 836                         // the result should be the same as for m == 0;
 837                         // specifically, there should be no div-zero panic
 838                         m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
 839                         z2 := new(Int).Exp(x, y, m)
 840                         if z2.Cmp(z1) != 0 {
 841                                 t.Errorf("#%d: got %s want %s", i, z1, z2)
 842                         }
 843                 }
 844         }
 845 }
 846
 847 func checkGcd(aBytes, bBytes []byte) bool {
 848         x := new(Int)
 849         y := new(Int)
 850         a := new(Int).SetBytes(aBytes)
 851         b := new(Int).SetBytes(bBytes)
 852
 853         d := new(Int).GCD(x, y, a, b)
 854         x.Mul(x, a)
 855         y.Mul(y, b)
 856         x.Add(x, y)
 857
 858         return x.Cmp(d) == 0
 859 }
 860
 861 var gcdTests = []struct {
 862         d, x, y, a, b string
 863 }{
 864         // a <= 0 || b <= 0
 865         {"0", "0", "0", "0", "0"},
 866         {"0", "0", "0", "0", "7"},
 867         {"0", "0", "0", "11", "0"},
 868         {"0", "0", "0", "-77", "35"},
 869         {"0", "0", "0", "64515", "-24310"},
 870         {"0", "0", "0", "-64515", "-24310"},
 871
 872         {"1", "-9", "47", "120", "23"},
 873         {"7", "1", "-2", "77", "35"},
 874         {"935", "-3", "8", "64515", "24310"},
 875         {"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
 876         {"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
 877
 878         // test early exit (after one Euclidean iteration) in binaryGCD
 879         {"1", "", "", "1", "98920366548084643601728869055592650835572950932266967461790948584315647051443"},
 880 }
 881
 882 func testGcd(t *testing.T, d, x, y, a, b *Int) {
 883         var X *Int
 884         if x != nil {
 885                 X = new(Int)
 886         }
 887         var Y *Int
 888         if y != nil {
 889                 Y = new(Int)
 890         }
 891
 892         D := new(Int).GCD(X, Y, a, b)
 893         if D.Cmp(d) != 0 {
 894                 t.Errorf("GCD(%s, %s): got d = %s, want %s", a, b, D, d)
 895         }
 896         if x != nil && X.Cmp(x) != 0 {
 897                 t.Errorf("GCD(%s, %s): got x = %s, want %s", a, b, X, x)
 898         }
 899         if y != nil && Y.Cmp(y) != 0 {
 900                 t.Errorf("GCD(%s, %s): got y = %s, want %s", a, b, Y, y)
 901         }
 902
 903         // binaryGCD requires a > 0 && b > 0
 904         if a.Sign() <= 0 || b.Sign() <= 0 {
 905                 return
 906         }
 907
 908         D.binaryGCD(a, b)
 909         if D.Cmp(d) != 0 {
 910                 t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, D, d)
 911         }
 912 }
 913
 914 func TestGcd(t *testing.T) {
 915         for _, test := range gcdTests {
 916                 d, _ := new(Int).SetString(test.d, 0)
 917                 x, _ := new(Int).SetString(test.x, 0)
 918                 y, _ := new(Int).SetString(test.y, 0)
 919                 a, _ := new(Int).SetString(test.a, 0)
 920                 b, _ := new(Int).SetString(test.b, 0)
 921
 922                 testGcd(t, d, nil, nil, a, b)
 923                 testGcd(t, d, x, nil, a, b)
 924                 testGcd(t, d, nil, y, a, b)
 925                 testGcd(t, d, x, y, a, b)
 926         }
 927
 928         quick.Check(checkGcd, nil)
 929 }
 930
 931 var primes = []string{
 932         "2",
 933         "3",
 934         "5",
 935         "7",
 936         "11",
 937
 938         "13756265695458089029",
 939         "13496181268022124907",
 940         "10953742525620032441",
 941         "17908251027575790097",
 942
 943         // http://code.google.com/p/go/issues/detail?id=638
 944         "18699199384836356663",
 945
 946         "98920366548084643601728869055592650835572950932266967461790948584315647051443",
 947         "94560208308847015747498523884063394671606671904944666360068158221458669711639",
 948
 949         // http://primes.utm.edu/lists/small/small3.html
 950         "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
 951         "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
 952         "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
 953         "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
 954 }
 955
 956 var composites = []string{
 957         "21284175091214687912771199898307297748211672914763848041968395774954376176754",
 958         "6084766654921918907427900243509372380954290099172559290432744450051395395951",
 959         "84594350493221918389213352992032324280367711247940675652888030554255915464401",
 960         "82793403787388584738507275144194252681",
 961 }
 962
 963 func TestProbablyPrime(t *testing.T) {
 964         nreps := 20
 965         if testing.Short() {
 966                 nreps = 1
 967         }
 968         for i, s := range primes {
 969                 p, _ := new(Int).SetString(s, 10)
 970                 if !p.ProbablyPrime(nreps) {
 971                         t.Errorf("#%d prime found to be non-prime (%s)", i, s)
 972                 }
 973         }
 974
 975         for i, s := range composites {
 976                 c, _ := new(Int).SetString(s, 10)
 977                 if c.ProbablyPrime(nreps) {
 978                         t.Errorf("#%d composite found to be prime (%s)", i, s)
 979                 }
 980                 if testing.Short() {
 981                         break
 982                 }
 983         }
 984 }
 985
 986 type intShiftTest struct {
 987         in    string
 988         shift uint
 989         out   string
 990 }
 991
 992 var rshTests = []intShiftTest{
 993         {"0", 0, "0"},
 994         {"-0", 0, "0"},
 995         {"0", 1, "0"},
 996         {"0", 2, "0"},
 997         {"1", 0, "1"},
 998         {"1", 1, "0"},
 999         {"1", 2, "0"},
1000         {"2", 0, "2"},
1001         {"2", 1, "1"},
1002         {"-1", 0, "-1"},
1003         {"-1", 1, "-1"},
1004         {"-1", 10, "-1"},
1005         {"-100", 2, "-25"},
1006         {"-100", 3, "-13"},
1007         {"-100", 100, "-1"},
1008         {"4294967296", 0, "4294967296"},
1009         {"4294967296", 1, "2147483648"},
1010         {"4294967296", 2, "1073741824"},
1011         {"18446744073709551616", 0, "18446744073709551616"},
1012         {"18446744073709551616", 1, "9223372036854775808"},
1013         {"18446744073709551616", 2, "4611686018427387904"},
1014         {"18446744073709551616", 64, "1"},
1015         {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
1016         {"340282366920938463463374607431768211456", 128, "1"},
1017 }
1018
1019 func TestRsh(t *testing.T) {
1020         for i, test := range rshTests {
1021                 in, _ := new(Int).SetString(test.in, 10)
1022                 expected, _ := new(Int).SetString(test.out, 10)
1023                 out := new(Int).Rsh(in, test.shift)
1024
1025                 if !isNormalized(out) {
1026                         t.Errorf("#%d: %v is not normalized", i, *out)
1027                 }
1028                 if out.Cmp(expected) != 0 {
1029                         t.Errorf("#%d: got %s want %s", i, out, expected)
1030                 }
1031         }
1032 }
1033
1034 func TestRshSelf(t *testing.T) {
1035         for i, test := range rshTests {
1036                 z, _ := new(Int).SetString(test.in, 10)
1037                 expected, _ := new(Int).SetString(test.out, 10)
1038                 z.Rsh(z, test.shift)
1039
1040                 if !isNormalized(z) {
1041                         t.Errorf("#%d: %v is not normalized", i, *z)
1042                 }
1043                 if z.Cmp(expected) != 0 {
1044                         t.Errorf("#%d: got %s want %s", i, z, expected)
1045                 }
1046         }
1047 }
1048
1049 var lshTests = []intShiftTest{
1050         {"0", 0, "0"},
1051         {"0", 1, "0"},
1052         {"0", 2, "0"},
1053         {"1", 0, "1"},
1054         {"1", 1, "2"},
1055         {"1", 2, "4"},
1056         {"2", 0, "2"},
1057         {"2", 1, "4"},
1058         {"2", 2, "8"},
1059         {"-87", 1, "-174"},
1060         {"4294967296", 0, "4294967296"},
1061         {"4294967296", 1, "8589934592"},
1062         {"4294967296", 2, "17179869184"},
1063         {"18446744073709551616", 0, "18446744073709551616"},
1064         {"9223372036854775808", 1, "18446744073709551616"},
1065         {"4611686018427387904", 2, "18446744073709551616"},
1066         {"1", 64, "18446744073709551616"},
1067         {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
1068         {"1", 128, "340282366920938463463374607431768211456"},
1069 }
1070
1071 func TestLsh(t *testing.T) {
1072         for i, test := range lshTests {
1073                 in, _ := new(Int).SetString(test.in, 10)
1074                 expected, _ := new(Int).SetString(test.out, 10)
1075                 out := new(Int).Lsh(in, test.shift)
1076
1077                 if !isNormalized(out) {
1078                         t.Errorf("#%d: %v is not normalized", i, *out)
1079                 }
1080                 if out.Cmp(expected) != 0 {
1081                         t.Errorf("#%d: got %s want %s", i, out, expected)
1082                 }
1083         }
1084 }
1085
1086 func TestLshSelf(t *testing.T) {
1087         for i, test := range lshTests {
1088                 z, _ := new(Int).SetString(test.in, 10)
1089                 expected, _ := new(Int).SetString(test.out, 10)
1090                 z.Lsh(z, test.shift)
1091
1092                 if !isNormalized(z) {
1093                         t.Errorf("#%d: %v is not normalized", i, *z)
1094                 }
1095                 if z.Cmp(expected) != 0 {
1096                         t.Errorf("#%d: got %s want %s", i, z, expected)
1097                 }
1098         }
1099 }
1100
1101 func TestLshRsh(t *testing.T) {
1102         for i, test := range rshTests {
1103                 in, _ := new(Int).SetString(test.in, 10)
1104                 out := new(Int).Lsh(in, test.shift)
1105                 out = out.Rsh(out, test.shift)
1106
1107                 if !isNormalized(out) {
1108                         t.Errorf("#%d: %v is not normalized", i, *out)
1109                 }
1110                 if in.Cmp(out) != 0 {
1111                         t.Errorf("#%d: got %s want %s", i, out, in)
1112                 }
1113         }
1114         for i, test := range lshTests {
1115                 in, _ := new(Int).SetString(test.in, 10)
1116                 out := new(Int).Lsh(in, test.shift)
1117                 out.Rsh(out, test.shift)
1118
1119                 if !isNormalized(out) {
1120                         t.Errorf("#%d: %v is not normalized", i, *out)
1121                 }
1122                 if in.Cmp(out) != 0 {
1123                         t.Errorf("#%d: got %s want %s", i, out, in)
1124                 }
1125         }
1126 }
1127
1128 var int64Tests = []int64{
1129         0,
1130         1,
1131         -1,
1132         4294967295,
1133         -4294967295,
1134         4294967296,
1135         -4294967296,
1136         9223372036854775807,
1137         -9223372036854775807,
1138         -9223372036854775808,
1139 }
1140
1141 func TestInt64(t *testing.T) {
1142         for i, testVal := range int64Tests {
1143                 in := NewInt(testVal)
1144                 out := in.Int64()
1145
1146                 if out != testVal {
1147                         t.Errorf("#%d got %d want %d", i, out, testVal)
1148                 }
1149         }
1150 }
1151
1152 var uint64Tests = []uint64{
1153         0,
1154         1,
1155         4294967295,
1156         4294967296,
1157         8589934591,
1158         8589934592,
1159         9223372036854775807,
1160         9223372036854775808,
1161         18446744073709551615, // 1<<64 - 1
1162 }
1163
1164 func TestUint64(t *testing.T) {
1165         in := new(Int)
1166         for i, testVal := range uint64Tests {
1167                 in.SetUint64(testVal)
1168                 out := in.Uint64()
1169
1170                 if out != testVal {
1171                         t.Errorf("#%d got %d want %d", i, out, testVal)
1172                 }
1173
1174                 str := fmt.Sprint(testVal)
1175                 strOut := in.String()
1176                 if strOut != str {
1177                         t.Errorf("#%d.String got %s want %s", i, strOut, str)
1178                 }
1179         }
1180 }
1181
1182 var bitwiseTests = []struct {
1183         x, y                 string
1184         and, or, xor, andNot string
1185 }{
1186         {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
1187         {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
1188         {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1189         {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1190         {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1191         {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1192         {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1193         {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1194         {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1195         {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1196         {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1197         {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1198         {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1199         {
1200                 "0x1000009dc6e3d9822cba04129bcbe3401",
1201                 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1202                 "0x1000001186210100001000009048c2001",
1203                 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1204                 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1205                 "0x8c40c2d8822caa04120b8321400",
1206         },
1207         {
1208                 "0x1000009dc6e3d9822cba04129bcbe3401",
1209                 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1210                 "0x8c40c2d8822caa04120b8321401",
1211                 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1212                 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1213                 "0x1000001186210100001000009048c2000",
1214         },
1215         {
1216                 "-0x1000009dc6e3d9822cba04129bcbe3401",
1217                 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1218                 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1219                 "-0x1000001186210100001000009048c2001",
1220                 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1221                 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1222         },
1223 }
1224
1225 type bitFun func(z, x, y *Int) *Int
1226
1227 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1228         expected := new(Int)
1229         expected.SetString(exp, 0)
1230
1231         out := f(new(Int), x, y)
1232         if out.Cmp(expected) != 0 {
1233                 t.Errorf("%s: got %s want %s", msg, out, expected)
1234         }
1235 }
1236
1237 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1238         self := new(Int)
1239         self.Set(x)
1240         expected := new(Int)
1241         expected.SetString(exp, 0)
1242
1243         self = f(self, self, y)
1244         if self.Cmp(expected) != 0 {
1245                 t.Errorf("%s: got %s want %s", msg, self, expected)
1246         }
1247 }
1248
1249 func altBit(x *Int, i int) uint {
1250         z := new(Int).Rsh(x, uint(i))
1251         z = z.And(z, NewInt(1))
1252         if z.Cmp(new(Int)) != 0 {
1253                 return 1
1254         }
1255         return 0
1256 }
1257
1258 func altSetBit(z *Int, x *Int, i int, b uint) *Int {
1259         one := NewInt(1)
1260         m := one.Lsh(one, uint(i))
1261         switch b {
1262         case 1:
1263                 return z.Or(x, m)
1264         case 0:
1265                 return z.AndNot(x, m)
1266         }
1267         panic("set bit is not 0 or 1")
1268 }
1269
1270 func testBitset(t *testing.T, x *Int) {
1271         n := x.BitLen()
1272         z := new(Int).Set(x)
1273         z1 := new(Int).Set(x)
1274         for i := 0; i < n+10; i++ {
1275                 old := z.Bit(i)
1276                 old1 := altBit(z1, i)
1277                 if old != old1 {
1278                         t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1279                 }
1280                 z := new(Int).SetBit(z, i, 1)
1281                 z1 := altSetBit(new(Int), z1, i, 1)
1282                 if z.Bit(i) == 0 {
1283                         t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1284                 }
1285                 if z.Cmp(z1) != 0 {
1286                         t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1287                 }
1288                 z.SetBit(z, i, 0)
1289                 altSetBit(z1, z1, i, 0)
1290                 if z.Bit(i) != 0 {
1291                         t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1292                 }
1293                 if z.Cmp(z1) != 0 {
1294                         t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1295                 }
1296                 altSetBit(z1, z1, i, old)
1297                 z.SetBit(z, i, old)
1298                 if z.Cmp(z1) != 0 {
1299                         t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1300                 }
1301         }
1302         if z.Cmp(x) != 0 {
1303                 t.Errorf("bitset: got %s want %s", z, x)
1304         }
1305 }
1306
1307 var bitsetTests = []struct {
1308         x string
1309         i int
1310         b uint
1311 }{
1312         {"0", 0, 0},
1313         {"0", 200, 0},
1314         {"1", 0, 1},
1315         {"1", 1, 0},
1316         {"-1", 0, 1},
1317         {"-1", 200, 1},
1318         {"0x2000000000000000000000000000", 108, 0},
1319         {"0x2000000000000000000000000000", 109, 1},
1320         {"0x2000000000000000000000000000", 110, 0},
1321         {"-0x2000000000000000000000000001", 108, 1},
1322         {"-0x2000000000000000000000000001", 109, 0},
1323         {"-0x2000000000000000000000000001", 110, 1},
1324 }
1325
1326 func TestBitSet(t *testing.T) {
1327         for _, test := range bitwiseTests {
1328                 x := new(Int)
1329                 x.SetString(test.x, 0)
1330                 testBitset(t, x)
1331                 x = new(Int)
1332                 x.SetString(test.y, 0)
1333                 testBitset(t, x)
1334         }
1335         for i, test := range bitsetTests {
1336                 x := new(Int)
1337                 x.SetString(test.x, 0)
1338                 b := x.Bit(test.i)
1339                 if b != test.b {
1340                         t.Errorf("#%d got %v want %v", i, b, test.b)
1341                 }
1342         }
1343         z := NewInt(1)
1344         z.SetBit(NewInt(0), 2, 1)
1345         if z.Cmp(NewInt(4)) != 0 {
1346                 t.Errorf("destination leaked into result; got %s want 4", z)
1347         }
1348 }
1349
1350 func BenchmarkBitset(b *testing.B) {
1351         z := new(Int)
1352         z.SetBit(z, 512, 1)
1353         b.ResetTimer()
1354         b.StartTimer()
1355         for i := b.N - 1; i >= 0; i-- {
1356                 z.SetBit(z, i&512, 1)
1357         }
1358 }
1359
1360 func BenchmarkBitsetNeg(b *testing.B) {
1361         z := NewInt(-1)
1362         z.SetBit(z, 512, 0)
1363         b.ResetTimer()
1364         b.StartTimer()
1365         for i := b.N - 1; i >= 0; i-- {
1366                 z.SetBit(z, i&512, 0)
1367         }
1368 }
1369
1370 func BenchmarkBitsetOrig(b *testing.B) {
1371         z := new(Int)
1372         altSetBit(z, z, 512, 1)
1373         b.ResetTimer()
1374         b.StartTimer()
1375         for i := b.N - 1; i >= 0; i-- {
1376                 altSetBit(z, z, i&512, 1)
1377         }
1378 }
1379
1380 func BenchmarkBitsetNegOrig(b *testing.B) {
1381         z := NewInt(-1)
1382         altSetBit(z, z, 512, 0)
1383         b.ResetTimer()
1384         b.StartTimer()
1385         for i := b.N - 1; i >= 0; i-- {
1386                 altSetBit(z, z, i&512, 0)
1387         }
1388 }
1389
1390 func TestBitwise(t *testing.T) {
1391         x := new(Int)
1392         y := new(Int)
1393         for _, test := range bitwiseTests {
1394                 x.SetString(test.x, 0)
1395                 y.SetString(test.y, 0)
1396
1397                 testBitFun(t, "and", (*Int).And, x, y, test.and)
1398                 testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
1399                 testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1400                 testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1401                 testBitFun(t, "or", (*Int).Or, x, y, test.or)
1402                 testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
1403                 testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
1404                 testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1405         }
1406 }
1407
1408 var notTests = []struct {
1409         in  string
1410         out string
1411 }{
1412         {"0", "-1"},
1413         {"1", "-2"},
1414         {"7", "-8"},
1415         {"0", "-1"},
1416         {"-81910", "81909"},
1417         {
1418                 "298472983472983471903246121093472394872319615612417471234712061",
1419                 "-298472983472983471903246121093472394872319615612417471234712062",
1420         },
1421 }
1422
1423 func TestNot(t *testing.T) {
1424         in := new(Int)
1425         out := new(Int)
1426         expected := new(Int)
1427         for i, test := range notTests {
1428                 in.SetString(test.in, 10)
1429                 expected.SetString(test.out, 10)
1430                 out = out.Not(in)
1431                 if out.Cmp(expected) != 0 {
1432                         t.Errorf("#%d: got %s want %s", i, out, expected)
1433                 }
1434                 out = out.Not(out)
1435                 if out.Cmp(in) != 0 {
1436                         t.Errorf("#%d: got %s want %s", i, out, in)
1437                 }
1438         }
1439 }
1440
1441 var modInverseTests = []struct {
1442         element string
1443         prime   string
1444 }{
1445         {"1", "7"},
1446         {"1", "13"},
1447         {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1448 }
1449
1450 func TestModInverse(t *testing.T) {
1451         var element, prime Int
1452         one := NewInt(1)
1453         for i, test := range modInverseTests {
1454                 (&element).SetString(test.element, 10)
1455                 (&prime).SetString(test.prime, 10)
1456                 inverse := new(Int).ModInverse(&element, &prime)
1457                 inverse.Mul(inverse, &element)
1458                 inverse.Mod(inverse, &prime)
1459                 if inverse.Cmp(one) != 0 {
1460                         t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
1461                 }
1462         }
1463 }
1464
1465 var encodingTests = []string{
1466         "-539345864568634858364538753846587364875430589374589",
1467         "-678645873",
1468         "-100",
1469         "-2",
1470         "-1",
1471         "0",
1472         "1",
1473         "2",
1474         "10",
1475         "42",
1476         "1234567890",
1477         "298472983472983471903246121093472394872319615612417471234712061",
1478 }
1479
1480 func TestIntGobEncoding(t *testing.T) {
1481         var medium bytes.Buffer
1482         enc := gob.NewEncoder(&medium)
1483         dec := gob.NewDecoder(&medium)
1484         for _, test := range encodingTests {
1485                 medium.Reset() // empty buffer for each test case (in case of failures)
1486                 var tx Int
1487                 tx.SetString(test, 10)
1488                 if err := enc.Encode(&tx); err != nil {
1489                         t.Errorf("encoding of %s failed: %s", &tx, err)
1490                 }
1491                 var rx Int
1492                 if err := dec.Decode(&rx); err != nil {
1493                         t.Errorf("decoding of %s failed: %s", &tx, err)
1494                 }
1495                 if rx.Cmp(&tx) != 0 {
1496                         t.Errorf("transmission of %s failed: got %s want %s", &tx, &rx, &tx)
1497                 }
1498         }
1499 }
1500
1501 // Sending a nil Int pointer (inside a slice) on a round trip through gob should yield a zero.
1502 // TODO: top-level nils.
1503 func TestGobEncodingNilIntInSlice(t *testing.T) {
1504         buf := new(bytes.Buffer)
1505         enc := gob.NewEncoder(buf)
1506         dec := gob.NewDecoder(buf)
1507
1508         var in = make([]*Int, 1)
1509         err := enc.Encode(&in)
1510         if err != nil {
1511                 t.Errorf("gob encode failed: %q", err)
1512         }
1513         var out []*Int
1514         err = dec.Decode(&out)
1515         if err != nil {
1516                 t.Fatalf("gob decode failed: %q", err)
1517         }
1518         if len(out) != 1 {
1519                 t.Fatalf("wrong len; want 1 got %d", len(out))
1520         }
1521         var zero Int
1522         if out[0].Cmp(&zero) != 0 {
1523                 t.Errorf("transmission of (*Int)(nill) failed: got %s want 0", out)
1524         }
1525 }
1526
1527 func TestIntJSONEncoding(t *testing.T) {
1528         for _, test := range encodingTests {
1529                 var tx Int
1530                 tx.SetString(test, 10)
1531                 b, err := json.Marshal(&tx)
1532                 if err != nil {
1533                         t.Errorf("marshaling of %s failed: %s", &tx, err)
1534                 }
1535                 var rx Int
1536                 if err := json.Unmarshal(b, &rx); err != nil {
1537                         t.Errorf("unmarshaling of %s failed: %s", &tx, err)
1538                 }
1539                 if rx.Cmp(&tx) != 0 {
1540                         t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx)
1541                 }
1542         }
1543 }
1544
1545 var intVals = []string{
1546         "-141592653589793238462643383279502884197169399375105820974944592307816406286",
1547         "-1415926535897932384626433832795028841971",
1548         "-141592653589793",
1549         "-1",
1550         "0",
1551         "1",
1552         "141592653589793",
1553         "1415926535897932384626433832795028841971",
1554         "141592653589793238462643383279502884197169399375105820974944592307816406286",
1555 }
1556
1557 func TestIntJSONEncodingTextMarshaller(t *testing.T) {
1558         for _, num := range intVals {
1559                 var tx Int
1560                 tx.SetString(num, 0)
1561                 b, err := json.Marshal(&tx)
1562                 if err != nil {
1563                         t.Errorf("marshaling of %s failed: %s", &tx, err)
1564                         continue
1565                 }
1566                 var rx Int
1567                 if err := json.Unmarshal(b, &rx); err != nil {
1568                         t.Errorf("unmarshaling of %s failed: %s", &tx, err)
1569                         continue
1570                 }
1571                 if rx.Cmp(&tx) != 0 {
1572                         t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx)
1573                 }
1574         }
1575 }
1576
1577 func TestIntXMLEncodingTextMarshaller(t *testing.T) {
1578         for _, num := range intVals {
1579                 var tx Int
1580                 tx.SetString(num, 0)
1581                 b, err := xml.Marshal(&tx)
1582                 if err != nil {
1583                         t.Errorf("marshaling of %s failed: %s", &tx, err)
1584                         continue
1585                 }
1586                 var rx Int
1587                 if err := xml.Unmarshal(b, &rx); err != nil {
1588                         t.Errorf("unmarshaling of %s failed: %s", &tx, err)
1589                         continue
1590                 }
1591                 if rx.Cmp(&tx) != 0 {
1592                         t.Errorf("XML encoding of %s failed: got %s want %s", &tx, &rx, &tx)
1593                 }
1594         }
1595 }
1596
1597 func TestIssue2607(t *testing.T) {
1598         // This code sequence used to hang.
1599         n := NewInt(10)
1600         n.Rand(rand.New(rand.NewSource(9)), n)
1601 }