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