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