libgo/go/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 "testing"
   8
   9 var cmpTests = []struct {
  10         x, y nat
  11         r    int
  12 }{
  13         {nil, nil, 0},
  14         {nil, nat{}, 0},
  15         {nat{}, nil, 0},
  16         {nat{}, nat{}, 0},
  17         {nat{0}, nat{0}, 0},
  18         {nat{0}, nat{1}, -1},
  19         {nat{1}, nat{0}, 1},
  20         {nat{1}, nat{1}, 0},
  21         {nat{0, _M}, nat{1}, 1},
  22         {nat{1}, nat{0, _M}, -1},
  23         {nat{1, _M}, nat{0, _M}, 1},
  24         {nat{0, _M}, nat{1, _M}, -1},
  25         {nat{16, 571956, 8794, 68}, nat{837, 9146, 1, 754489}, -1},
  26         {nat{34986, 41, 105, 1957}, nat{56, 7458, 104, 1957}, 1},
  27 }
  28
  29
  30 func TestCmp(t *testing.T) {
  31         for i, a := range cmpTests {
  32                 r := a.x.cmp(a.y)
  33                 if r != a.r {
  34                         t.Errorf("#%d got r = %v; want %v", i, r, a.r)
  35                 }
  36         }
  37 }
  38
  39
  40 type funNN func(z, x, y nat) nat
  41 type argNN struct {
  42         z, x, y nat
  43 }
  44
  45
  46 var sumNN = []argNN{
  47         {},
  48         {nat{1}, nil, nat{1}},
  49         {nat{1111111110}, nat{123456789}, nat{987654321}},
  50         {nat{0, 0, 0, 1}, nil, nat{0, 0, 0, 1}},
  51         {nat{0, 0, 0, 1111111110}, nat{0, 0, 0, 123456789}, nat{0, 0, 0, 987654321}},
  52         {nat{0, 0, 0, 1}, nat{0, 0, _M}, nat{0, 0, 1}},
  53 }
  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 }
  66
  67
  68 func TestSet(t *testing.T) {
  69         for _, a := range sumNN {
  70                 z := nat(nil).set(a.z)
  71                 if z.cmp(a.z) != 0 {
  72                         t.Errorf("got z = %v; want %v", z, a.z)
  73                 }
  74         }
  75 }
  76
  77
  78 func testFunNN(t *testing.T, msg string, f funNN, a argNN) {
  79         z := f(nil, a.x, a.y)
  80         if z.cmp(a.z) != 0 {
  81                 t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, z, a.z)
  82         }
  83 }
  84
  85
  86 func TestFunNN(t *testing.T) {
  87         for _, a := range sumNN {
  88                 arg := a
  89                 testFunNN(t, "add", nat.add, arg)
  90
  91                 arg = argNN{a.z, a.y, a.x}
  92                 testFunNN(t, "add symmetric", nat.add, arg)
  93
  94                 arg = argNN{a.x, a.z, a.y}
  95                 testFunNN(t, "sub", nat.sub, arg)
  96
  97                 arg = argNN{a.y, a.z, a.x}
  98                 testFunNN(t, "sub symmetric", nat.sub, arg)
  99         }
 100
 101         for _, a := range prodNN {
 102                 arg := a
 103                 testFunNN(t, "mul", nat.mul, arg)
 104
 105                 arg = argNN{a.z, a.y, a.x}
 106                 testFunNN(t, "mul symmetric", nat.mul, arg)
 107         }
 108 }
 109
 110
 111 var mulRangesN = []struct {
 112         a, b uint64
 113         prod string
 114 }{
 115         {0, 0, "0"},
 116         {1, 1, "1"},
 117         {1, 2, "2"},
 118         {1, 3, "6"},
 119         {10, 10, "10"},
 120         {0, 100, "0"},
 121         {0, 1e9, "0"},
 122         {1, 0, "1"},                    // empty range
 123         {100, 1, "1"},                  // empty range
 124         {1, 10, "3628800"},             // 10!
 125         {1, 20, "2432902008176640000"}, // 20!
 126         {1, 100,
 127                 "933262154439441526816992388562667004907159682643816214685929" +
 128                         "638952175999932299156089414639761565182862536979208272237582" +
 129                         "51185210916864000000000000000000000000", // 100!
 130         },
 131 }
 132
 133
 134 func TestMulRangeN(t *testing.T) {
 135         for i, r := range mulRangesN {
 136                 prod := nat(nil).mulRange(r.a, r.b).string(10)
 137                 if prod != r.prod {
 138                         t.Errorf("#%d: got %s; want %s", i, prod, r.prod)
 139                 }
 140         }
 141 }
 142
 143
 144 var mulArg, mulTmp nat
 145
 146 func init() {
 147         const n = 1000
 148         mulArg = make(nat, n)
 149         for i := 0; i < n; i++ {
 150                 mulArg[i] = _M
 151         }
 152 }
 153
 154
 155 func benchmarkMulLoad() {
 156         for j := 1; j <= 10; j++ {
 157                 x := mulArg[0 : j*100]
 158                 mulTmp.mul(x, x)
 159         }
 160 }
 161
 162
 163 func BenchmarkMul(b *testing.B) {
 164         for i := 0; i < b.N; i++ {
 165                 benchmarkMulLoad()
 166         }
 167 }
 168
 169
 170 var tab = []struct {
 171         x nat
 172         b int
 173         s string
 174 }{
 175         {nil, 10, "0"},
 176         {nat{1}, 10, "1"},
 177         {nat{10}, 10, "10"},
 178         {nat{1234567890}, 10, "1234567890"},
 179 }
 180
 181
 182 func TestString(t *testing.T) {
 183         for _, a := range tab {
 184                 s := a.x.string(a.b)
 185                 if s != a.s {
 186                         t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
 187                 }
 188
 189                 x, b, n := nat(nil).scan(a.s, a.b)
 190                 if x.cmp(a.x) != 0 {
 191                         t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
 192                 }
 193                 if b != a.b {
 194                         t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.b)
 195                 }
 196                 if n != len(a.s) {
 197                         t.Errorf("scan%+v\n\tgot n = %d; want %d", a, n, len(a.s))
 198                 }
 199         }
 200 }
 201
 202
 203 func TestLeadingZeros(t *testing.T) {
 204         var x Word = _B >> 1
 205         for i := 0; i <= _W; i++ {
 206                 if int(leadingZeros(x)) != i {
 207                         t.Errorf("failed at %x: got %d want %d", x, leadingZeros(x), i)
 208                 }
 209                 x >>= 1
 210         }
 211 }
 212
 213
 214 type shiftTest struct {
 215         in    nat
 216         shift uint
 217         out   nat
 218 }
 219
 220
 221 var leftShiftTests = []shiftTest{
 222         {nil, 0, nil},
 223         {nil, 1, nil},
 224         {natOne, 0, natOne},
 225         {natOne, 1, natTwo},
 226         {nat{1 << (_W - 1)}, 1, nat{0}},
 227         {nat{1 << (_W - 1), 0}, 1, nat{0, 1}},
 228 }
 229
 230
 231 func TestShiftLeft(t *testing.T) {
 232         for i, test := range leftShiftTests {
 233                 var z nat
 234                 z = z.shl(test.in, test.shift)
 235                 for j, d := range test.out {
 236                         if j >= len(z) || z[j] != d {
 237                                 t.Errorf("#%d: got: %v want: %v", i, z, test.out)
 238                                 break
 239                         }
 240                 }
 241         }
 242 }
 243
 244
 245 var rightShiftTests = []shiftTest{
 246         {nil, 0, nil},
 247         {nil, 1, nil},
 248         {natOne, 0, natOne},
 249         {natOne, 1, nil},
 250         {natTwo, 1, natOne},
 251         {nat{0, 1}, 1, nat{1 << (_W - 1)}},
 252         {nat{2, 1, 1}, 1, nat{1<<(_W-1) + 1, 1 << (_W - 1)}},
 253 }
 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
 270 type modWTest struct {
 271         in       string
 272         dividend string
 273         out      string
 274 }
 275
 276
 277 var modWTests32 = []modWTest{
 278         {"23492635982634928349238759823742", "252341", "220170"},
 279 }
 280
 281
 282 var modWTests64 = []modWTest{
 283         {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
 284 }
 285
 286
 287 func runModWTests(t *testing.T, tests []modWTest) {
 288         for i, test := range tests {
 289                 in, _ := new(Int).SetString(test.in, 10)
 290                 d, _ := new(Int).SetString(test.dividend, 10)
 291                 out, _ := new(Int).SetString(test.out, 10)
 292
 293                 r := in.abs.modW(d.abs[0])
 294                 if r != out.abs[0] {
 295                         t.Errorf("#%d failed: got %s want %s", i, r, out)
 296                 }
 297         }
 298 }
 299
 300
 301 func TestModW(t *testing.T) {
 302         if _W >= 32 {
 303                 runModWTests(t, modWTests32)
 304         }
 305         if _W >= 64 {
 306                 runModWTests(t, modWTests64)
 307         }
 308 }
 309
 310
 311 func TestTrailingZeroBits(t *testing.T) {
 312         var x Word
 313         x--
 314         for i := 0; i < _W; i++ {
 315                 if trailingZeroBits(x) != i {
 316                         t.Errorf("Failed at step %d: x: %x got: %d", i, x, trailingZeroBits(x))
 317                 }
 318                 x <<= 1
 319         }
 320 }
 321
 322
 323 var expNNTests = []struct {
 324         x, y, m string
 325         out     string
 326 }{
 327         {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
 328         {"0x8000000000000000", "2", "6719", "4944"},
 329         {"0x8000000000000000", "3", "6719", "5447"},
 330         {"0x8000000000000000", "1000", "6719", "1603"},
 331         {"0x8000000000000000", "1000000", "6719", "3199"},
 332         {
 333                 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
 334                 "298472983472983471903246121093472394872319615612417471234712061",
 335                 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
 336                 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
 337         },
 338 }
 339
 340
 341 func TestExpNN(t *testing.T) {
 342         for i, test := range expNNTests {
 343                 x, _, _ := nat(nil).scan(test.x, 0)
 344                 y, _, _ := nat(nil).scan(test.y, 0)
 345                 out, _, _ := nat(nil).scan(test.out, 0)
 346
 347                 var m nat
 348
 349                 if len(test.m) > 0 {
 350                         m, _, _ = nat(nil).scan(test.m, 0)
 351                 }
 352
 353                 z := nat(nil).expNN(x, y, m)
 354                 if z.cmp(out) != 0 {
 355                         t.Errorf("#%d got %v want %v", i, z, out)
 356                 }
 357         }
 358 }