libgo/go/math/big/nat_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         "runtime"
   9         "strings"
  10         "testing"
  11 )
  12
  13 var cmpTests = []struct {
  14         x, y nat
  15         r    int
  16 }{
  17         {nil, nil, 0},
  18         {nil, nat(nil), 0},
  19         {nat(nil), nil, 0},
  20         {nat(nil), nat(nil), 0},
  21         {nat{0}, nat{0}, 0},
  22         {nat{0}, nat{1}, -1},
  23         {nat{1}, nat{0}, 1},
  24         {nat{1}, nat{1}, 0},
  25         {nat{0, _M}, nat{1}, 1},
  26         {nat{1}, nat{0, _M}, -1},
  27         {nat{1, _M}, nat{0, _M}, 1},
  28         {nat{0, _M}, nat{1, _M}, -1},
  29         {nat{16, 571956, 8794, 68}, nat{837, 9146, 1, 754489}, -1},
  30         {nat{34986, 41, 105, 1957}, nat{56, 7458, 104, 1957}, 1},
  31 }
  32
  33 func TestCmp(t *testing.T) {
  34         for i, a := range cmpTests {
  35                 r := a.x.cmp(a.y)
  36                 if r != a.r {
  37                         t.Errorf("#%d got r = %v; want %v", i, r, a.r)
  38                 }
  39         }
  40 }
  41
  42 type funNN func(z, x, y nat) nat
  43 type argNN struct {
  44         z, x, y nat
  45 }
  46
  47 var sumNN = []argNN{
  48         {},
  49         {nat{1}, nil, nat{1}},
  50         {nat{1111111110}, nat{123456789}, nat{987654321}},
  51         {nat{0, 0, 0, 1}, nil, nat{0, 0, 0, 1}},
  52         {nat{0, 0, 0, 1111111110}, nat{0, 0, 0, 123456789}, nat{0, 0, 0, 987654321}},
  53         {nat{0, 0, 0, 1}, nat{0, 0, _M}, nat{0, 0, 1}},
  54 }
  55
  56 var prodNN = []argNN{
  57         {},
  58         {nil, nil, nil},
  59         {nil, nat{991}, nil},
  60         {nat{991}, nat{991}, nat{1}},
  61         {nat{991 * 991}, nat{991}, nat{991}},
  62         {nat{0, 0, 991 * 991}, nat{0, 991}, nat{0, 991}},
  63         {nat{1 * 991, 2 * 991, 3 * 991, 4 * 991}, nat{1, 2, 3, 4}, nat{991}},
  64         {nat{4, 11, 20, 30, 20, 11, 4}, nat{1, 2, 3, 4}, nat{4, 3, 2, 1}},
  65         // 3^100 * 3^28 = 3^128
  66         {
  67                 natFromString("11790184577738583171520872861412518665678211592275841109096961"),
  68                 natFromString("515377520732011331036461129765621272702107522001"),
  69                 natFromString("22876792454961"),
  70         },
  71         // z = 111....1 (70000 digits)
  72         // x = 10^(99*700) + ... + 10^1400 + 10^700 + 1
  73         // y = 111....1 (700 digits, larger than Karatsuba threshold on 32-bit and 64-bit)
  74         {
  75                 natFromString(strings.Repeat("1", 70000)),
  76                 natFromString("1" + strings.Repeat(strings.Repeat("0", 699)+"1", 99)),
  77                 natFromString(strings.Repeat("1", 700)),
  78         },
  79         // z = 111....1 (20000 digits)
  80         // x = 10^10000 + 1
  81         // y = 111....1 (10000 digits)
  82         {
  83                 natFromString(strings.Repeat("1", 20000)),
  84                 natFromString("1" + strings.Repeat("0", 9999) + "1"),
  85                 natFromString(strings.Repeat("1", 10000)),
  86         },
  87 }
  88
  89 func natFromString(s string) nat {
  90         x, _, _, err := nat(nil).scan(strings.NewReader(s), 0, false)
  91         if err != nil {
  92                 panic(err)
  93         }
  94         return x
  95 }
  96
  97 func TestSet(t *testing.T) {
  98         for _, a := range sumNN {
  99                 z := nat(nil).set(a.z)
 100                 if z.cmp(a.z) != 0 {
 101                         t.Errorf("got z = %v; want %v", z, a.z)
 102                 }
 103         }
 104 }
 105
 106 func testFunNN(t *testing.T, msg string, f funNN, a argNN) {
 107         z := f(nil, a.x, a.y)
 108         if z.cmp(a.z) != 0 {
 109                 t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, z, a.z)
 110         }
 111 }
 112
 113 func TestFunNN(t *testing.T) {
 114         for _, a := range sumNN {
 115                 arg := a
 116                 testFunNN(t, "add", nat.add, arg)
 117
 118                 arg = argNN{a.z, a.y, a.x}
 119                 testFunNN(t, "add symmetric", nat.add, arg)
 120
 121                 arg = argNN{a.x, a.z, a.y}
 122                 testFunNN(t, "sub", nat.sub, arg)
 123
 124                 arg = argNN{a.y, a.z, a.x}
 125                 testFunNN(t, "sub symmetric", nat.sub, arg)
 126         }
 127
 128         for _, a := range prodNN {
 129                 arg := a
 130                 testFunNN(t, "mul", nat.mul, arg)
 131
 132                 arg = argNN{a.z, a.y, a.x}
 133                 testFunNN(t, "mul symmetric", nat.mul, arg)
 134         }
 135 }
 136
 137 var mulRangesN = []struct {
 138         a, b uint64
 139         prod string
 140 }{
 141         {0, 0, "0"},
 142         {1, 1, "1"},
 143         {1, 2, "2"},
 144         {1, 3, "6"},
 145         {10, 10, "10"},
 146         {0, 100, "0"},
 147         {0, 1e9, "0"},
 148         {1, 0, "1"},                    // empty range
 149         {100, 1, "1"},                  // empty range
 150         {1, 10, "3628800"},             // 10!
 151         {1, 20, "2432902008176640000"}, // 20!
 152         {1, 100,
 153                 "933262154439441526816992388562667004907159682643816214685929" +
 154                         "638952175999932299156089414639761565182862536979208272237582" +
 155                         "51185210916864000000000000000000000000", // 100!
 156         },
 157 }
 158
 159 func TestMulRangeN(t *testing.T) {
 160         for i, r := range mulRangesN {
 161                 prod := nat(nil).mulRange(r.a, r.b).decimalString()
 162                 if prod != r.prod {
 163                         t.Errorf("#%d: got %s; want %s", i, prod, r.prod)
 164                 }
 165         }
 166 }
 167
 168 // allocBytes returns the number of bytes allocated by invoking f.
 169 func allocBytes(f func()) uint64 {
 170         var stats runtime.MemStats
 171         runtime.ReadMemStats(&stats)
 172         t := stats.TotalAlloc
 173         f()
 174         runtime.ReadMemStats(&stats)
 175         return stats.TotalAlloc - t
 176 }
 177
 178 // TestMulUnbalanced tests that multiplying numbers of different lengths
 179 // does not cause deep recursion and in turn allocate too much memory.
 180 // Test case for issue 3807.
 181 func TestMulUnbalanced(t *testing.T) {
 182         defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(1))
 183         x := rndNat(50000)
 184         y := rndNat(40)
 185         allocSize := allocBytes(func() {
 186                 nat(nil).mul(x, y)
 187         })
 188         inputSize := uint64(len(x)+len(y)) * _S
 189         if ratio := allocSize / uint64(inputSize); ratio > 10 {
 190                 t.Errorf("multiplication uses too much memory (%d > %d times the size of inputs)", allocSize, ratio)
 191         }
 192 }
 193
 194 func rndNat(n int) nat {
 195         return nat(rndV(n)).norm()
 196 }
 197
 198 func BenchmarkMul(b *testing.B) {
 199         mulx := rndNat(1e4)
 200         muly := rndNat(1e4)
 201         b.ResetTimer()
 202         for i := 0; i < b.N; i++ {
 203                 var z nat
 204                 z.mul(mulx, muly)
 205         }
 206 }
 207
 208 func TestNLZ(t *testing.T) {
 209         var x Word = _B >> 1
 210         for i := 0; i <= _W; i++ {
 211                 if int(nlz(x)) != i {
 212                         t.Errorf("failed at %x: got %d want %d", x, nlz(x), i)
 213                 }
 214                 x >>= 1
 215         }
 216 }
 217
 218 type shiftTest struct {
 219         in    nat
 220         shift uint
 221         out   nat
 222 }
 223
 224 var leftShiftTests = []shiftTest{
 225         {nil, 0, nil},
 226         {nil, 1, nil},
 227         {natOne, 0, natOne},
 228         {natOne, 1, natTwo},
 229         {nat{1 << (_W - 1)}, 1, nat{0}},
 230         {nat{1 << (_W - 1), 0}, 1, nat{0, 1}},
 231 }
 232
 233 func TestShiftLeft(t *testing.T) {
 234         for i, test := range leftShiftTests {
 235                 var z nat
 236                 z = z.shl(test.in, test.shift)
 237                 for j, d := range test.out {
 238                         if j >= len(z) || z[j] != d {
 239                                 t.Errorf("#%d: got: %v want: %v", i, z, test.out)
 240                                 break
 241                         }
 242                 }
 243         }
 244 }
 245
 246 var rightShiftTests = []shiftTest{
 247         {nil, 0, nil},
 248         {nil, 1, nil},
 249         {natOne, 0, natOne},
 250         {natOne, 1, nil},
 251         {natTwo, 1, natOne},
 252         {nat{0, 1}, 1, nat{1 << (_W - 1)}},
 253         {nat{2, 1, 1}, 1, nat{1<<(_W-1) + 1, 1 << (_W - 1)}},
 254 }
 255
 256 func TestShiftRight(t *testing.T) {
 257         for i, test := range rightShiftTests {
 258                 var z nat
 259                 z = z.shr(test.in, test.shift)
 260                 for j, d := range test.out {
 261                         if j >= len(z) || z[j] != d {
 262                                 t.Errorf("#%d: got: %v want: %v", i, z, test.out)
 263                                 break
 264                         }
 265                 }
 266         }
 267 }
 268
 269 type modWTest struct {
 270         in       string
 271         dividend string
 272         out      string
 273 }
 274
 275 var modWTests32 = []modWTest{
 276         {"23492635982634928349238759823742", "252341", "220170"},
 277 }
 278
 279 var modWTests64 = []modWTest{
 280         {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
 281 }
 282
 283 func runModWTests(t *testing.T, tests []modWTest) {
 284         for i, test := range tests {
 285                 in, _ := new(Int).SetString(test.in, 10)
 286                 d, _ := new(Int).SetString(test.dividend, 10)
 287                 out, _ := new(Int).SetString(test.out, 10)
 288
 289                 r := in.abs.modW(d.abs[0])
 290                 if r != out.abs[0] {
 291                         t.Errorf("#%d failed: got %d want %s", i, r, out)
 292                 }
 293         }
 294 }
 295
 296 func TestModW(t *testing.T) {
 297         if _W >= 32 {
 298                 runModWTests(t, modWTests32)
 299         }
 300         if _W >= 64 {
 301                 runModWTests(t, modWTests64)
 302         }
 303 }
 304
 305 func TestTrailingZeroBits(t *testing.T) {
 306         // test 0 case explicitly
 307         if n := trailingZeroBits(0); n != 0 {
 308                 t.Errorf("got trailingZeroBits(0) = %d; want 0", n)
 309         }
 310
 311         x := Word(1)
 312         for i := uint(0); i < _W; i++ {
 313                 n := trailingZeroBits(x)
 314                 if n != i {
 315                         t.Errorf("got trailingZeroBits(%#x) = %d; want %d", x, n, i%_W)
 316                 }
 317                 x <<= 1
 318         }
 319
 320         // test 0 case explicitly
 321         if n := nat(nil).trailingZeroBits(); n != 0 {
 322                 t.Errorf("got nat(nil).trailingZeroBits() = %d; want 0", n)
 323         }
 324
 325         y := nat(nil).set(natOne)
 326         for i := uint(0); i <= 3*_W; i++ {
 327                 n := y.trailingZeroBits()
 328                 if n != i {
 329                         t.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y.hexString(), n, i)
 330                 }
 331                 y = y.shl(y, 1)
 332         }
 333 }
 334
 335 var montgomeryTests = []struct {
 336         x, y, m      string
 337         k0           uint64
 338         out32, out64 string
 339 }{
 340         {
 341                 "0xffffffffffffffffffffffffffffffffffffffffffffffffe",
 342                 "0xffffffffffffffffffffffffffffffffffffffffffffffffe",
 343                 "0xfffffffffffffffffffffffffffffffffffffffffffffffff",
 344                 0x0000000000000000,
 345                 "0xffffffffffffffffffffffffffffffffffffffffff",
 346                 "0xffffffffffffffffffffffffffffffffff",
 347         },
 348         {
 349                 "0x0000000080000000",
 350                 "0x00000000ffffffff",
 351                 "0x0000000010000001",
 352                 0xff0000000fffffff,
 353                 "0x0000000088000000",
 354                 "0x0000000007800001",
 355         },
 356         {
 357                 "0xffffffffffffffffffffffffffffffff00000000000022222223333333333444444444",
 358                 "0xffffffffffffffffffffffffffffffff999999999999999aaabbbbbbbbcccccccccccc",
 359                 "0x33377fffffffffffffffffffffffffffffffffffffffffffff0000000000022222eee1",
 360                 0xdecc8f1249812adf,
 361                 "0x22bb05b6d95eaaeca2bb7c05e51f807bce9064b5fbad177161695e4558f9474e91cd79",
 362                 "0x14beb58d230f85b6d95eaaeca2bb7c05e51f807bce9064b5fb45669afa695f228e48cd",
 363         },
 364         {
 365                 "0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000022222223333333333444444444",
 366                 "0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffff999999999999999aaabbbbbbbbcccccccccccc",
 367                 "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff33377fffffffffffffffffffffffffffffffffffffffffffff0000000000022222eee1",
 368                 0xdecc8f1249812adf,
 369                 "0x5c0d52f451aec609b15da8e5e5626c4eaa88723bdeac9d25ca9b961269400410ca208a16af9c2fb07d7a11c7772cba02c22f9711078d51a3797eb18e691295293284d988e349fa6deba46b25a4ecd9f715",
 370                 "0x92fcad4b5c0d52f451aec609b15da8e5e5626c4eaa88723bdeac9d25ca9b961269400410ca208a16af9c2fb07d799c32fe2f3cc5422f9711078d51a3797eb18e691295293284d8f5e69caf6decddfe1df6",
 371         },
 372 }
 373
 374 func TestMontgomery(t *testing.T) {
 375         for i, test := range montgomeryTests {
 376                 x := natFromString(test.x)
 377                 y := natFromString(test.y)
 378                 m := natFromString(test.m)
 379
 380                 var out nat
 381                 if _W == 32 {
 382                         out = natFromString(test.out32)
 383                 } else {
 384                         out = natFromString(test.out64)
 385                 }
 386
 387                 k0 := Word(test.k0 & _M) // mask k0 to ensure that it fits for 32-bit systems.
 388                 z := nat(nil).montgomery(x, y, m, k0, len(m))
 389                 z = z.norm()
 390                 if z.cmp(out) != 0 {
 391                         t.Errorf("#%d got %s want %s", i, z.decimalString(), out.decimalString())
 392                 }
 393         }
 394 }
 395
 396 var expNNTests = []struct {
 397         x, y, m string
 398         out     string
 399 }{
 400         {"0", "0", "0", "1"},
 401         {"0", "0", "1", "0"},
 402         {"1", "1", "1", "0"},
 403         {"2", "1", "1", "0"},
 404         {"2", "2", "1", "0"},
 405         {"10", "100000000000", "1", "0"},
 406         {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
 407         {"0x8000000000000000", "2", "6719", "4944"},
 408         {"0x8000000000000000", "3", "6719", "5447"},
 409         {"0x8000000000000000", "1000", "6719", "1603"},
 410         {"0x8000000000000000", "1000000", "6719", "3199"},
 411         {
 412                 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
 413                 "298472983472983471903246121093472394872319615612417471234712061",
 414                 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
 415                 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
 416         },
 417 }
 418
 419 func TestExpNN(t *testing.T) {
 420         for i, test := range expNNTests {
 421                 x := natFromString(test.x)
 422                 y := natFromString(test.y)
 423                 out := natFromString(test.out)
 424
 425                 var m nat
 426                 if len(test.m) > 0 {
 427                         m = natFromString(test.m)
 428                 }
 429
 430                 z := nat(nil).expNN(x, y, m)
 431                 if z.cmp(out) != 0 {
 432                         t.Errorf("#%d got %s want %s", i, z.decimalString(), out.decimalString())
 433                 }
 434         }
 435 }
 436
 437 func ExpHelper(b *testing.B, x, y Word) {
 438         var z nat
 439         for i := 0; i < b.N; i++ {
 440                 z.expWW(x, y)
 441         }
 442 }
 443
 444 func BenchmarkExp3Power0x10(b *testing.B)     { ExpHelper(b, 3, 0x10) }
 445 func BenchmarkExp3Power0x40(b *testing.B)     { ExpHelper(b, 3, 0x40) }
 446 func BenchmarkExp3Power0x100(b *testing.B)    { ExpHelper(b, 3, 0x100) }
 447 func BenchmarkExp3Power0x400(b *testing.B)    { ExpHelper(b, 3, 0x400) }
 448 func BenchmarkExp3Power0x1000(b *testing.B)   { ExpHelper(b, 3, 0x1000) }
 449 func BenchmarkExp3Power0x4000(b *testing.B)   { ExpHelper(b, 3, 0x4000) }
 450 func BenchmarkExp3Power0x10000(b *testing.B)  { ExpHelper(b, 3, 0x10000) }
 451 func BenchmarkExp3Power0x40000(b *testing.B)  { ExpHelper(b, 3, 0x40000) }
 452 func BenchmarkExp3Power0x100000(b *testing.B) { ExpHelper(b, 3, 0x100000) }
 453 func BenchmarkExp3Power0x400000(b *testing.B) { ExpHelper(b, 3, 0x400000) }
 454
 455 func fibo(n int) nat {
 456         switch n {
 457         case 0:
 458                 return nil
 459         case 1:
 460                 return nat{1}
 461         }
 462         f0 := fibo(0)
 463         f1 := fibo(1)
 464         var f2 nat
 465         for i := 1; i < n; i++ {
 466                 f2 = f2.add(f0, f1)
 467                 f0, f1, f2 = f1, f2, f0
 468         }
 469         return f1
 470 }
 471
 472 var fiboNums = []string{
 473         "0",
 474         "55",
 475         "6765",
 476         "832040",
 477         "102334155",
 478         "12586269025",
 479         "1548008755920",
 480         "190392490709135",
 481         "23416728348467685",
 482         "2880067194370816120",
 483         "354224848179261915075",
 484 }
 485
 486 func TestFibo(t *testing.T) {
 487         for i, want := range fiboNums {
 488                 n := i * 10
 489                 got := fibo(n).decimalString()
 490                 if got != want {
 491                         t.Errorf("fibo(%d) failed: got %s want %s", n, got, want)
 492                 }
 493         }
 494 }
 495
 496 func BenchmarkFibo(b *testing.B) {
 497         for i := 0; i < b.N; i++ {
 498                 fibo(1e0)
 499                 fibo(1e1)
 500                 fibo(1e2)
 501                 fibo(1e3)
 502                 fibo(1e4)
 503                 fibo(1e5)
 504         }
 505 }
 506
 507 var bitTests = []struct {
 508         x    string
 509         i    uint
 510         want uint
 511 }{
 512         {"0", 0, 0},
 513         {"0", 1, 0},
 514         {"0", 1000, 0},
 515
 516         {"0x1", 0, 1},
 517         {"0x10", 0, 0},
 518         {"0x10", 3, 0},
 519         {"0x10", 4, 1},
 520         {"0x10", 5, 0},
 521
 522         {"0x8000000000000000", 62, 0},
 523         {"0x8000000000000000", 63, 1},
 524         {"0x8000000000000000", 64, 0},
 525
 526         {"0x3" + strings.Repeat("0", 32), 127, 0},
 527         {"0x3" + strings.Repeat("0", 32), 128, 1},
 528         {"0x3" + strings.Repeat("0", 32), 129, 1},
 529         {"0x3" + strings.Repeat("0", 32), 130, 0},
 530 }
 531
 532 func TestBit(t *testing.T) {
 533         for i, test := range bitTests {
 534                 x := natFromString(test.x)
 535                 if got := x.bit(test.i); got != test.want {
 536                         t.Errorf("#%d: %s.bit(%d) = %v; want %v", i, test.x, test.i, got, test.want)
 537                 }
 538         }
 539 }
 540
 541 var stickyTests = []struct {
 542         x    string
 543         i    uint
 544         want uint
 545 }{
 546         {"0", 0, 0},
 547         {"0", 1, 0},
 548         {"0", 1000, 0},
 549
 550         {"0x1", 0, 0},
 551         {"0x1", 1, 1},
 552
 553         {"0x1350", 0, 0},
 554         {"0x1350", 4, 0},
 555         {"0x1350", 5, 1},
 556
 557         {"0x8000000000000000", 63, 0},
 558         {"0x8000000000000000", 64, 1},
 559
 560         {"0x1" + strings.Repeat("0", 100), 400, 0},
 561         {"0x1" + strings.Repeat("0", 100), 401, 1},
 562 }
 563
 564 func TestSticky(t *testing.T) {
 565         for i, test := range stickyTests {
 566                 x := natFromString(test.x)
 567                 if got := x.sticky(test.i); got != test.want {
 568                         t.Errorf("#%d: %s.sticky(%d) = %v; want %v", i, test.x, test.i, got, test.want)
 569                 }
 570                 if test.want == 1 {
 571                         // all subsequent i's should also return 1
 572                         for d := uint(1); d <= 3; d++ {
 573                                 if got := x.sticky(test.i + d); got != 1 {
 574                                         t.Errorf("#%d: %s.sticky(%d) = %v; want %v", i, test.x, test.i+d, got, 1)
 575                                 }
 576                         }
 577                 }
 578         }
 579 }