libgo/go/math/big/arith_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         "math/rand"
   9         "testing"
  10 )
  11
  12 type funWW func(x, y, c Word) (z1, z0 Word)
  13 type argWW struct {
  14         x, y, c, z1, z0 Word
  15 }
  16
  17 var sumWW = []argWW{
  18         {0, 0, 0, 0, 0},
  19         {0, 1, 0, 0, 1},
  20         {0, 0, 1, 0, 1},
  21         {0, 1, 1, 0, 2},
  22         {12345, 67890, 0, 0, 80235},
  23         {12345, 67890, 1, 0, 80236},
  24         {_M, 1, 0, 1, 0},
  25         {_M, 0, 1, 1, 0},
  26         {_M, 1, 1, 1, 1},
  27         {_M, _M, 0, 1, _M - 1},
  28         {_M, _M, 1, 1, _M},
  29 }
  30
  31 func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
  32         z1, z0 := f(a.x, a.y, a.c)
  33         if z1 != a.z1 || z0 != a.z0 {
  34                 t.Errorf("%s%+v\n\tgot z1:z0 = %#x:%#x; want %#x:%#x", msg, a, z1, z0, a.z1, a.z0)
  35         }
  36 }
  37
  38 func TestFunWW(t *testing.T) {
  39         for _, a := range sumWW {
  40                 arg := a
  41                 testFunWW(t, "addWW_g", addWW_g, arg)
  42
  43                 arg = argWW{a.y, a.x, a.c, a.z1, a.z0}
  44                 testFunWW(t, "addWW_g symmetric", addWW_g, arg)
  45
  46                 arg = argWW{a.z0, a.x, a.c, a.z1, a.y}
  47                 testFunWW(t, "subWW_g", subWW_g, arg)
  48
  49                 arg = argWW{a.z0, a.y, a.c, a.z1, a.x}
  50                 testFunWW(t, "subWW_g symmetric", subWW_g, arg)
  51         }
  52 }
  53
  54 type funVV func(z, x, y []Word) (c Word)
  55 type argVV struct {
  56         z, x, y nat
  57         c       Word
  58 }
  59
  60 var sumVV = []argVV{
  61         {},
  62         {nat{0}, nat{0}, nat{0}, 0},
  63         {nat{1}, nat{1}, nat{0}, 0},
  64         {nat{0}, nat{_M}, nat{1}, 1},
  65         {nat{80235}, nat{12345}, nat{67890}, 0},
  66         {nat{_M - 1}, nat{_M}, nat{_M}, 1},
  67         {nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
  68         {nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
  69         {nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
  70 }
  71
  72 func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
  73         z := make(nat, len(a.z))
  74         c := f(z, a.x, a.y)
  75         for i, zi := range z {
  76                 if zi != a.z[i] {
  77                         t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
  78                         break
  79                 }
  80         }
  81         if c != a.c {
  82                 t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
  83         }
  84 }
  85
  86 func TestFunVV(t *testing.T) {
  87         for _, a := range sumVV {
  88                 arg := a
  89                 testFunVV(t, "addVV_g", addVV_g, arg)
  90                 testFunVV(t, "addVV", addVV, arg)
  91
  92                 arg = argVV{a.z, a.y, a.x, a.c}
  93                 testFunVV(t, "addVV_g symmetric", addVV_g, arg)
  94                 testFunVV(t, "addVV symmetric", addVV, arg)
  95
  96                 arg = argVV{a.x, a.z, a.y, a.c}
  97                 testFunVV(t, "subVV_g", subVV_g, arg)
  98                 testFunVV(t, "subVV", subVV, arg)
  99
 100                 arg = argVV{a.y, a.z, a.x, a.c}
 101                 testFunVV(t, "subVV_g symmetric", subVV_g, arg)
 102                 testFunVV(t, "subVV symmetric", subVV, arg)
 103         }
 104 }
 105
 106 // Always the same seed for reproducible results.
 107 var rnd = rand.New(rand.NewSource(0))
 108
 109 func rndW() Word {
 110         return Word(rnd.Int63()<<1 | rnd.Int63n(2))
 111 }
 112
 113 func rndV(n int) []Word {
 114         v := make([]Word, n)
 115         for i := range v {
 116                 v[i] = rndW()
 117         }
 118         return v
 119 }
 120
 121 func benchmarkFunVV(b *testing.B, f funVV, n int) {
 122         x := rndV(n)
 123         y := rndV(n)
 124         z := make([]Word, n)
 125         b.SetBytes(int64(n * _W))
 126         b.ResetTimer()
 127         for i := 0; i < b.N; i++ {
 128                 f(z, x, y)
 129         }
 130 }
 131
 132 func BenchmarkAddVV_1(b *testing.B)   { benchmarkFunVV(b, addVV, 1) }
 133 func BenchmarkAddVV_2(b *testing.B)   { benchmarkFunVV(b, addVV, 2) }
 134 func BenchmarkAddVV_3(b *testing.B)   { benchmarkFunVV(b, addVV, 3) }
 135 func BenchmarkAddVV_4(b *testing.B)   { benchmarkFunVV(b, addVV, 4) }
 136 func BenchmarkAddVV_5(b *testing.B)   { benchmarkFunVV(b, addVV, 5) }
 137 func BenchmarkAddVV_1e1(b *testing.B) { benchmarkFunVV(b, addVV, 1e1) }
 138 func BenchmarkAddVV_1e2(b *testing.B) { benchmarkFunVV(b, addVV, 1e2) }
 139 func BenchmarkAddVV_1e3(b *testing.B) { benchmarkFunVV(b, addVV, 1e3) }
 140 func BenchmarkAddVV_1e4(b *testing.B) { benchmarkFunVV(b, addVV, 1e4) }
 141 func BenchmarkAddVV_1e5(b *testing.B) { benchmarkFunVV(b, addVV, 1e5) }
 142
 143 type funVW func(z, x []Word, y Word) (c Word)
 144 type argVW struct {
 145         z, x nat
 146         y    Word
 147         c    Word
 148 }
 149
 150 var sumVW = []argVW{
 151         {},
 152         {nil, nil, 2, 2},
 153         {nat{0}, nat{0}, 0, 0},
 154         {nat{1}, nat{0}, 1, 0},
 155         {nat{1}, nat{1}, 0, 0},
 156         {nat{0}, nat{_M}, 1, 1},
 157         {nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
 158 }
 159
 160 var prodVW = []argVW{
 161         {},
 162         {nat{0}, nat{0}, 0, 0},
 163         {nat{0}, nat{_M}, 0, 0},
 164         {nat{0}, nat{0}, _M, 0},
 165         {nat{1}, nat{1}, 1, 0},
 166         {nat{22793}, nat{991}, 23, 0},
 167         {nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0},
 168         {nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0},
 169         {nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0},
 170         {nat{_M << 1 & _M}, nat{_M}, 1 << 1, _M >> (_W - 1)},
 171         {nat{_M << 7 & _M}, nat{_M}, 1 << 7, _M >> (_W - 7)},
 172         {nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, _M >> (_W - 7)},
 173 }
 174
 175 var lshVW = []argVW{
 176         {},
 177         {nat{0}, nat{0}, 0, 0},
 178         {nat{0}, nat{0}, 1, 0},
 179         {nat{0}, nat{0}, 20, 0},
 180
 181         {nat{_M}, nat{_M}, 0, 0},
 182         {nat{_M << 1 & _M}, nat{_M}, 1, 1},
 183         {nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
 184
 185         {nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
 186         {nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
 187         {nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
 188 }
 189
 190 var rshVW = []argVW{
 191         {},
 192         {nat{0}, nat{0}, 0, 0},
 193         {nat{0}, nat{0}, 1, 0},
 194         {nat{0}, nat{0}, 20, 0},
 195
 196         {nat{_M}, nat{_M}, 0, 0},
 197         {nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
 198         {nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
 199
 200         {nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
 201         {nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
 202         {nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
 203 }
 204
 205 func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
 206         z := make(nat, len(a.z))
 207         c := f(z, a.x, a.y)
 208         for i, zi := range z {
 209                 if zi != a.z[i] {
 210                         t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
 211                         break
 212                 }
 213         }
 214         if c != a.c {
 215                 t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
 216         }
 217 }
 218
 219 func makeFunVW(f func(z, x []Word, s uint) (c Word)) funVW {
 220         return func(z, x []Word, s Word) (c Word) {
 221                 return f(z, x, uint(s))
 222         }
 223 }
 224
 225 func TestFunVW(t *testing.T) {
 226         for _, a := range sumVW {
 227                 arg := a
 228                 testFunVW(t, "addVW_g", addVW_g, arg)
 229                 testFunVW(t, "addVW", addVW, arg)
 230
 231                 arg = argVW{a.x, a.z, a.y, a.c}
 232                 testFunVW(t, "subVW_g", subVW_g, arg)
 233                 testFunVW(t, "subVW", subVW, arg)
 234         }
 235
 236         shlVW_g := makeFunVW(shlVU_g)
 237         shlVW := makeFunVW(shlVU)
 238         for _, a := range lshVW {
 239                 arg := a
 240                 testFunVW(t, "shlVU_g", shlVW_g, arg)
 241                 testFunVW(t, "shlVU", shlVW, arg)
 242         }
 243
 244         shrVW_g := makeFunVW(shrVU_g)
 245         shrVW := makeFunVW(shrVU)
 246         for _, a := range rshVW {
 247                 arg := a
 248                 testFunVW(t, "shrVU_g", shrVW_g, arg)
 249                 testFunVW(t, "shrVU", shrVW, arg)
 250         }
 251 }
 252
 253 func benchmarkFunVW(b *testing.B, f funVW, n int) {
 254         x := rndV(n)
 255         y := rndW()
 256         z := make([]Word, n)
 257         b.SetBytes(int64(n * _W))
 258         b.ResetTimer()
 259         for i := 0; i < b.N; i++ {
 260                 f(z, x, y)
 261         }
 262 }
 263
 264 func BenchmarkAddVW_1(b *testing.B)   { benchmarkFunVW(b, addVW, 1) }
 265 func BenchmarkAddVW_2(b *testing.B)   { benchmarkFunVW(b, addVW, 2) }
 266 func BenchmarkAddVW_3(b *testing.B)   { benchmarkFunVW(b, addVW, 3) }
 267 func BenchmarkAddVW_4(b *testing.B)   { benchmarkFunVW(b, addVW, 4) }
 268 func BenchmarkAddVW_5(b *testing.B)   { benchmarkFunVW(b, addVW, 5) }
 269 func BenchmarkAddVW_1e1(b *testing.B) { benchmarkFunVW(b, addVW, 1e1) }
 270 func BenchmarkAddVW_1e2(b *testing.B) { benchmarkFunVW(b, addVW, 1e2) }
 271 func BenchmarkAddVW_1e3(b *testing.B) { benchmarkFunVW(b, addVW, 1e3) }
 272 func BenchmarkAddVW_1e4(b *testing.B) { benchmarkFunVW(b, addVW, 1e4) }
 273 func BenchmarkAddVW_1e5(b *testing.B) { benchmarkFunVW(b, addVW, 1e5) }
 274
 275 type funVWW func(z, x []Word, y, r Word) (c Word)
 276 type argVWW struct {
 277         z, x nat
 278         y, r Word
 279         c    Word
 280 }
 281
 282 var prodVWW = []argVWW{
 283         {},
 284         {nat{0}, nat{0}, 0, 0, 0},
 285         {nat{991}, nat{0}, 0, 991, 0},
 286         {nat{0}, nat{_M}, 0, 0, 0},
 287         {nat{991}, nat{_M}, 0, 991, 0},
 288         {nat{0}, nat{0}, _M, 0, 0},
 289         {nat{991}, nat{0}, _M, 991, 0},
 290         {nat{1}, nat{1}, 1, 0, 0},
 291         {nat{992}, nat{1}, 1, 991, 0},
 292         {nat{22793}, nat{991}, 23, 0, 0},
 293         {nat{22800}, nat{991}, 23, 7, 0},
 294         {nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
 295         {nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
 296         {nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
 297         {nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
 298         {nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
 299         {nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
 300         {nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
 301         {nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
 302         {nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
 303         {nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
 304         {nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
 305         {nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
 306 }
 307
 308 func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
 309         z := make(nat, len(a.z))
 310         c := f(z, a.x, a.y, a.r)
 311         for i, zi := range z {
 312                 if zi != a.z[i] {
 313                         t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
 314                         break
 315                 }
 316         }
 317         if c != a.c {
 318                 t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
 319         }
 320 }
 321
 322 // TODO(gri) mulAddVWW and divWVW are symmetric operations but
 323 //           their signature is not symmetric. Try to unify.
 324
 325 type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
 326 type argWVW struct {
 327         z  nat
 328         xn Word
 329         x  nat
 330         y  Word
 331         r  Word
 332 }
 333
 334 func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
 335         z := make(nat, len(a.z))
 336         r := f(z, a.xn, a.x, a.y)
 337         for i, zi := range z {
 338                 if zi != a.z[i] {
 339                         t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
 340                         break
 341                 }
 342         }
 343         if r != a.r {
 344                 t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
 345         }
 346 }
 347
 348 func TestFunVWW(t *testing.T) {
 349         for _, a := range prodVWW {
 350                 arg := a
 351                 testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
 352                 testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
 353
 354                 if a.y != 0 && a.r < a.y {
 355                         arg := argWVW{a.x, a.c, a.z, a.y, a.r}
 356                         testFunWVW(t, "divWVW_g", divWVW_g, arg)
 357                         testFunWVW(t, "divWVW", divWVW, arg)
 358                 }
 359         }
 360 }
 361
 362 var mulWWTests = []struct {
 363         x, y Word
 364         q, r Word
 365 }{
 366         {_M, _M, _M - 1, 1},
 367         // 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
 368 }
 369
 370 func TestMulWW(t *testing.T) {
 371         for i, test := range mulWWTests {
 372                 q, r := mulWW_g(test.x, test.y)
 373                 if q != test.q || r != test.r {
 374                         t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
 375                 }
 376         }
 377 }
 378
 379 var mulAddWWWTests = []struct {
 380         x, y, c Word
 381         q, r    Word
 382 }{
 383         // TODO(agl): These will only work on 64-bit platforms.
 384         // {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
 385         // {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
 386         {_M, _M, 0, _M - 1, 1},
 387         {_M, _M, _M, _M, 0},
 388 }
 389
 390 func TestMulAddWWW(t *testing.T) {
 391         for i, test := range mulAddWWWTests {
 392                 q, r := mulAddWWW_g(test.x, test.y, test.c)
 393                 if q != test.q || r != test.r {
 394                         t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
 395                 }
 396         }
 397 }
 398
 399 func benchmarkAddMulVVW(b *testing.B, n int) {
 400         x := rndV(n)
 401         y := rndW()
 402         z := make([]Word, n)
 403         b.SetBytes(int64(n * _W))
 404         b.ResetTimer()
 405         for i := 0; i < b.N; i++ {
 406                 addMulVVW(z, x, y)
 407         }
 408 }
 409
 410 func BenchmarkAddMulVVW_1(b *testing.B)   { benchmarkAddMulVVW(b, 1) }
 411 func BenchmarkAddMulVVW_2(b *testing.B)   { benchmarkAddMulVVW(b, 2) }
 412 func BenchmarkAddMulVVW_3(b *testing.B)   { benchmarkAddMulVVW(b, 3) }
 413 func BenchmarkAddMulVVW_4(b *testing.B)   { benchmarkAddMulVVW(b, 4) }
 414 func BenchmarkAddMulVVW_5(b *testing.B)   { benchmarkAddMulVVW(b, 5) }
 415 func BenchmarkAddMulVVW_1e1(b *testing.B) { benchmarkAddMulVVW(b, 1e1) }
 416 func BenchmarkAddMulVVW_1e2(b *testing.B) { benchmarkAddMulVVW(b, 1e2) }
 417 func BenchmarkAddMulVVW_1e3(b *testing.B) { benchmarkAddMulVVW(b, 1e3) }
 418 func BenchmarkAddMulVVW_1e4(b *testing.B) { benchmarkAddMulVVW(b, 1e4) }
 419 func BenchmarkAddMulVVW_1e5(b *testing.B) { benchmarkAddMulVVW(b, 1e5) }
 420
 421 func testWordBitLen(t *testing.T, fname string, f func(Word) int) {
 422         for i := 0; i <= _W; i++ {
 423                 x := Word(1) << uint(i-1) // i == 0 => x == 0
 424                 n := f(x)
 425                 if n != i {
 426                         t.Errorf("got %d; want %d for %s(%#x)", n, i, fname, x)
 427                 }
 428         }
 429 }
 430
 431 func TestWordBitLen(t *testing.T) {
 432         testWordBitLen(t, "bitLen", bitLen)
 433         testWordBitLen(t, "bitLen_g", bitLen_g)
 434 }
 435
 436 // runs b.N iterations of bitLen called on a Word containing (1 << nbits)-1.
 437 func benchmarkBitLenN(b *testing.B, nbits uint) {
 438         testword := Word((uint64(1) << nbits) - 1)
 439         for i := 0; i < b.N; i++ {
 440                 bitLen(testword)
 441         }
 442 }
 443
 444 // Individual bitLen tests.  Numbers chosen to examine both sides
 445 // of powers-of-two boundaries.
 446 func BenchmarkBitLen0(b *testing.B)  { benchmarkBitLenN(b, 0) }
 447 func BenchmarkBitLen1(b *testing.B)  { benchmarkBitLenN(b, 1) }
 448 func BenchmarkBitLen2(b *testing.B)  { benchmarkBitLenN(b, 2) }
 449 func BenchmarkBitLen3(b *testing.B)  { benchmarkBitLenN(b, 3) }
 450 func BenchmarkBitLen4(b *testing.B)  { benchmarkBitLenN(b, 4) }
 451 func BenchmarkBitLen5(b *testing.B)  { benchmarkBitLenN(b, 5) }
 452 func BenchmarkBitLen8(b *testing.B)  { benchmarkBitLenN(b, 8) }
 453 func BenchmarkBitLen9(b *testing.B)  { benchmarkBitLenN(b, 9) }
 454 func BenchmarkBitLen16(b *testing.B) { benchmarkBitLenN(b, 16) }
 455 func BenchmarkBitLen17(b *testing.B) { benchmarkBitLenN(b, 17) }
 456 func BenchmarkBitLen31(b *testing.B) { benchmarkBitLenN(b, 31) }