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.
17 func isNormalized(x *Int) bool {
22 return x.abs[len(x.abs)-1] != 0
26 type funZZ func(z, x, y *Int) *Int
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)},
43 {NewInt(0), NewInt(0), NewInt(0)},
44 {NewInt(0), NewInt(1), NewInt(0)},
45 {NewInt(1), NewInt(1), NewInt(1)},
46 {NewInt(-991 * 991), NewInt(991), NewInt(-991)},
47 // TODO(gri) add larger products
51 func TestSignZ(t *testing.T) {
53 for _, a := range sumZZ {
57 t.Errorf("got %d; want %d for z = %v", s, e, a.z)
63 func TestSetZ(t *testing.T) {
64 for _, a := range sumZZ {
67 if !isNormalized(&z) {
68 t.Errorf("%v is not normalized", z)
70 if (&z).Cmp(a.z) != 0 {
71 t.Errorf("got z = %v; want %v", z, a.z)
77 func TestAbsZ(t *testing.T) {
79 for _, a := range sumZZ {
88 t.Errorf("got z = %v; want %v", z, e)
94 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
97 if !isNormalized(&z) {
98 t.Errorf("%s%v is not normalized", z, msg)
100 if (&z).Cmp(a.z) != 0 {
101 t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
106 func TestSumZZ(t *testing.T) {
107 AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
108 SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
109 for _, a := range sumZZ {
111 testFunZZ(t, "AddZZ", AddZZ, arg)
113 arg = argZZ{a.z, a.y, a.x}
114 testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
116 arg = argZZ{a.x, a.z, a.y}
117 testFunZZ(t, "SubZZ", SubZZ, arg)
119 arg = argZZ{a.y, a.z, a.x}
120 testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
125 func TestProdZZ(t *testing.T) {
126 MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
127 for _, a := range prodZZ {
129 testFunZZ(t, "MulZZ", MulZZ, arg)
131 arg = argZZ{a.z, a.y, a.x}
132 testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
137 // mulBytes returns x*y via grade school multiplication. Both inputs
138 // and the result are assumed to be in big-endian representation (to
139 // match the semantics of Int.Bytes and Int.SetBytes).
140 func mulBytes(x, y []byte) []byte {
141 z := make([]byte, len(x)+len(y))
145 for j := len(y) - 1; j >= 0; j-- {
150 for i := len(x) - 1; i >= 0; i-- {
151 t := int(z[k]) + int(x[i])*d + carry
152 z[k], carry = byte(t), t>>8
160 // normalize (remove leading 0's)
162 for i < len(z) && z[i] == 0 {
170 func checkMul(a, b []byte) bool {
177 z2.SetBytes(mulBytes(a, b))
179 return z1.Cmp(&z2) == 0
183 func TestMul(t *testing.T) {
184 if err := quick.Check(checkMul, nil); err != nil {
190 var mulRangesZ = []struct {
194 // entirely positive ranges are covered by mulRangesN
201 {0, -1, "1"}, // empty range
202 {-1, -100, "1"}, // empty range
203 {-1, 1, "0"}, // range includes 0
204 {-1e9, 0, "0"}, // range includes 0
205 {-1e9, 1e9, "0"}, // range includes 0
206 {-10, -1, "3628800"}, // 10!
207 {-20, -2, "-2432902008176640000"}, // -20!
209 "-933262154439441526816992388562667004907159682643816214685929" +
210 "638952175999932299156089414639761565182862536979208272237582" +
211 "511852109168640000000000000000000000", // -99!
216 func TestMulRangeZ(t *testing.T) {
218 // test entirely positive ranges
219 for i, r := range mulRangesN {
220 prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
222 t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
226 for i, r := range mulRangesZ {
227 prod := tmp.MulRange(r.a, r.b).String()
229 t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
235 var stringTests = []struct {
243 {in: "a", ok: false},
244 {in: "z", ok: false},
245 {in: "+", ok: false},
246 {in: "-", ok: false},
247 {in: "0b", ok: false},
248 {in: "0x", ok: false},
249 {in: "2", base: 2, ok: false},
250 {in: "0b2", base: 0, ok: false},
251 {in: "08", ok: false},
252 {in: "8", base: 8, ok: false},
253 {in: "0xg", base: 0, ok: false},
254 {in: "g", base: 16, ok: false},
255 {"0", "0", 0, 0, true},
256 {"0", "0", 10, 0, true},
257 {"0", "0", 16, 0, true},
258 {"+0", "0", 0, 0, true},
259 {"-0", "0", 0, 0, true},
260 {"10", "10", 0, 10, true},
261 {"10", "10", 10, 10, true},
262 {"10", "10", 16, 16, true},
263 {"-10", "-10", 16, -16, true},
264 {"+10", "10", 16, 16, true},
265 {"0x10", "16", 0, 16, true},
266 {in: "0x10", base: 16, ok: false},
267 {"-0x10", "-16", 0, -16, true},
268 {"+0x10", "16", 0, 16, true},
269 {"00", "0", 0, 0, true},
270 {"0", "0", 8, 0, true},
271 {"07", "7", 0, 7, true},
272 {"7", "7", 8, 7, true},
273 {"023", "19", 0, 19, true},
274 {"23", "23", 8, 19, true},
275 {"cafebabe", "cafebabe", 16, 0xcafebabe, true},
276 {"0b0", "0", 0, 0, true},
277 {"-111", "-111", 2, -7, true},
278 {"-0b111", "-7", 0, -7, true},
279 {"0b1001010111", "599", 0, 0x257, true},
280 {"1001010111", "1001010111", 2, 0x257, true},
284 func format(base int) string {
297 func TestGetString(t *testing.T) {
299 for i, test := range stringTests {
308 t.Errorf("#%da got %s; want %s", i, s, test.out)
312 s := fmt.Sprintf(format(test.base), z)
314 t.Errorf("#%db got %s; want %s", i, s, test.out)
320 func TestSetString(t *testing.T) {
322 for i, test := range stringTests {
323 n1, ok1 := new(Int).SetString(test.in, test.base)
324 n2, ok2 := tmp.SetString(test.in, test.base)
325 expected := NewInt(test.val)
326 if ok1 != test.ok || ok2 != test.ok {
327 t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
334 if ok1 && !isNormalized(n1) {
335 t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
337 if ok2 && !isNormalized(n2) {
338 t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
341 if n1.Cmp(expected) != 0 {
342 t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
344 if n2.Cmp(expected) != 0 {
345 t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
351 // Examples from the Go Language Spec, section "Arithmetic operators"
352 var divisionSignsTests = []struct {
354 q, r int64 // T-division
355 d, m int64 // Euclidian division
358 {-5, 3, -1, -2, -2, 1},
359 {5, -3, -1, 2, -1, 2},
360 {-5, -3, 1, -2, 2, 1},
366 func TestDivisionSigns(t *testing.T) {
367 for i, test := range divisionSignsTests {
375 q1 := new(Int).Quo(x, y)
376 r1 := new(Int).Rem(x, y)
377 if !isNormalized(q1) {
378 t.Errorf("#%d Quo: %v is not normalized", i, *q1)
380 if !isNormalized(r1) {
381 t.Errorf("#%d Rem: %v is not normalized", i, *r1)
383 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
384 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
387 q2, r2 := new(Int).QuoRem(x, y, new(Int))
388 if !isNormalized(q2) {
389 t.Errorf("#%d Quo: %v is not normalized", i, *q2)
391 if !isNormalized(r2) {
392 t.Errorf("#%d Rem: %v is not normalized", i, *r2)
394 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
395 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
398 d1 := new(Int).Div(x, y)
399 m1 := new(Int).Mod(x, y)
400 if !isNormalized(d1) {
401 t.Errorf("#%d Div: %v is not normalized", i, *d1)
403 if !isNormalized(m1) {
404 t.Errorf("#%d Mod: %v is not normalized", i, *m1)
406 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
407 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
410 d2, m2 := new(Int).DivMod(x, y, new(Int))
411 if !isNormalized(d2) {
412 t.Errorf("#%d Div: %v is not normalized", i, *d2)
414 if !isNormalized(m2) {
415 t.Errorf("#%d Mod: %v is not normalized", i, *m2)
417 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
418 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
424 func checkSetBytes(b []byte) bool {
425 hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
426 hex2 := hex.EncodeToString(b)
428 for len(hex1) < len(hex2) {
432 for len(hex1) > len(hex2) {
440 func TestSetBytes(t *testing.T) {
441 if err := quick.Check(checkSetBytes, nil); err != nil {
447 func checkBytes(b []byte) bool {
448 b2 := new(Int).SetBytes(b).Bytes()
449 return bytes.Compare(b, b2) == 0
453 func TestBytes(t *testing.T) {
454 if err := quick.Check(checkSetBytes, nil); err != nil {
460 func checkQuo(x, y []byte) bool {
461 u := new(Int).SetBytes(x)
462 v := new(Int).SetBytes(y)
469 q, r := new(Int).QuoRem(u, v, r)
475 uprime := new(Int).Set(q)
476 uprime.Mul(uprime, v)
477 uprime.Add(uprime, r)
479 return uprime.Cmp(u) == 0
483 var quoTests = []struct {
488 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
489 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
494 "11510768301994997771168",
495 "1328165573307167369775",
497 "885443715537658812968",
502 func TestQuo(t *testing.T) {
503 if err := quick.Check(checkQuo, nil); err != nil {
507 for i, test := range quoTests {
508 x, _ := new(Int).SetString(test.x, 10)
509 y, _ := new(Int).SetString(test.y, 10)
510 expectedQ, _ := new(Int).SetString(test.q, 10)
511 expectedR, _ := new(Int).SetString(test.r, 10)
514 q, r := new(Int).QuoRem(x, y, r)
516 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
517 t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
523 func TestQuoStepD6(t *testing.T) {
524 // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
525 // a code path which only triggers 1 in 10^{-19} cases.
527 u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
528 v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
531 q, r := new(Int).QuoRem(u, v, r)
532 const expectedQ64 = "18446744073709551613"
533 const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
534 const expectedQ32 = "4294967293"
535 const expectedR32 = "39614081266355540837921718287"
536 if q.String() != expectedQ64 && q.String() != expectedQ32 ||
537 r.String() != expectedR64 && r.String() != expectedR32 {
538 t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
543 var bitLenTests = []struct {
555 {"0x800000000000", 48},
556 {"0x8000000000000000", 64},
557 {"0x80000000000000000000", 80},
558 {"-0x4000000000000000000000", 87},
562 func TestBitLen(t *testing.T) {
563 for i, test := range bitLenTests {
564 x, ok := new(Int).SetString(test.in, 0)
566 t.Errorf("#%d test input invalid: %s", i, test.in)
570 if n := x.BitLen(); n != test.out {
571 t.Errorf("#%d got %d want %d", i, n, test.out)
577 var expTests = []struct {
582 {"-5", "0", "", "-1"},
584 {"-5", "1", "", "-5"},
585 {"-2", "3", "2", "0"},
586 {"5", "2", "", "25"},
587 {"1", "65537", "2", "1"},
588 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
589 {"0x8000000000000000", "2", "6719", "4944"},
590 {"0x8000000000000000", "3", "6719", "5447"},
591 {"0x8000000000000000", "1000", "6719", "1603"},
592 {"0x8000000000000000", "1000000", "6719", "3199"},
594 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
595 "298472983472983471903246121093472394872319615612417471234712061",
596 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
597 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
602 func TestExp(t *testing.T) {
603 for i, test := range expTests {
604 x, ok1 := new(Int).SetString(test.x, 0)
605 y, ok2 := new(Int).SetString(test.y, 0)
606 out, ok3 := new(Int).SetString(test.out, 0)
611 if len(test.m) == 0 {
614 m, ok4 = new(Int).SetString(test.m, 0)
617 if !ok1 || !ok2 || !ok3 || !ok4 {
618 t.Errorf("#%d: error in input", i)
623 if !isNormalized(z) {
624 t.Errorf("#%d: %v is not normalized", i, *z)
627 t.Errorf("#%d: got %s want %s", i, z, out)
633 func checkGcd(aBytes, bBytes []byte) bool {
634 a := new(Int).SetBytes(aBytes)
635 b := new(Int).SetBytes(bBytes)
641 GcdInt(d, x, y, a, b)
650 var gcdTests = []struct {
654 {120, 23, 1, -9, 47},
658 func TestGcd(t *testing.T) {
659 for i, test := range gcdTests {
667 expectedX := NewInt(test.x)
668 expectedY := NewInt(test.y)
669 expectedD := NewInt(test.d)
671 GcdInt(d, x, y, a, b)
673 if expectedX.Cmp(x) != 0 ||
674 expectedY.Cmp(y) != 0 ||
675 expectedD.Cmp(d) != 0 {
676 t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x, y, d, expectedX, expectedY, expectedD)
680 quick.Check(checkGcd, nil)
684 var primes = []string{
691 "13756265695458089029",
692 "13496181268022124907",
693 "10953742525620032441",
694 "17908251027575790097",
696 // http://code.google.com/p/go/issues/detail?id=638
697 "18699199384836356663",
699 "98920366548084643601728869055592650835572950932266967461790948584315647051443",
700 "94560208308847015747498523884063394671606671904944666360068158221458669711639",
702 // http://primes.utm.edu/lists/small/small3.html
703 "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
704 "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
705 "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
706 "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
710 var composites = []string{
711 "21284175091214687912771199898307297748211672914763848041968395774954376176754",
712 "6084766654921918907427900243509372380954290099172559290432744450051395395951",
713 "84594350493221918389213352992032324280367711247940675652888030554255915464401",
714 "82793403787388584738507275144194252681",
718 func TestProbablyPrime(t *testing.T) {
719 for i, s := range primes {
720 p, _ := new(Int).SetString(s, 10)
721 if !ProbablyPrime(p, 20) {
722 t.Errorf("#%d prime found to be non-prime (%s)", i, s)
726 for i, s := range composites {
727 c, _ := new(Int).SetString(s, 10)
728 if ProbablyPrime(c, 20) {
729 t.Errorf("#%d composite found to be prime (%s)", i, s)
735 type intShiftTest struct {
742 var rshTests = []intShiftTest{
758 {"4294967296", 0, "4294967296"},
759 {"4294967296", 1, "2147483648"},
760 {"4294967296", 2, "1073741824"},
761 {"18446744073709551616", 0, "18446744073709551616"},
762 {"18446744073709551616", 1, "9223372036854775808"},
763 {"18446744073709551616", 2, "4611686018427387904"},
764 {"18446744073709551616", 64, "1"},
765 {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
766 {"340282366920938463463374607431768211456", 128, "1"},
770 func TestRsh(t *testing.T) {
771 for i, test := range rshTests {
772 in, _ := new(Int).SetString(test.in, 10)
773 expected, _ := new(Int).SetString(test.out, 10)
774 out := new(Int).Rsh(in, test.shift)
776 if !isNormalized(out) {
777 t.Errorf("#%d: %v is not normalized", i, *out)
779 if out.Cmp(expected) != 0 {
780 t.Errorf("#%d: got %s want %s", i, out, expected)
786 func TestRshSelf(t *testing.T) {
787 for i, test := range rshTests {
788 z, _ := new(Int).SetString(test.in, 10)
789 expected, _ := new(Int).SetString(test.out, 10)
792 if !isNormalized(z) {
793 t.Errorf("#%d: %v is not normalized", i, *z)
795 if z.Cmp(expected) != 0 {
796 t.Errorf("#%d: got %s want %s", i, z, expected)
802 var lshTests = []intShiftTest{
813 {"4294967296", 0, "4294967296"},
814 {"4294967296", 1, "8589934592"},
815 {"4294967296", 2, "17179869184"},
816 {"18446744073709551616", 0, "18446744073709551616"},
817 {"9223372036854775808", 1, "18446744073709551616"},
818 {"4611686018427387904", 2, "18446744073709551616"},
819 {"1", 64, "18446744073709551616"},
820 {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
821 {"1", 128, "340282366920938463463374607431768211456"},
825 func TestLsh(t *testing.T) {
826 for i, test := range lshTests {
827 in, _ := new(Int).SetString(test.in, 10)
828 expected, _ := new(Int).SetString(test.out, 10)
829 out := new(Int).Lsh(in, test.shift)
831 if !isNormalized(out) {
832 t.Errorf("#%d: %v is not normalized", i, *out)
834 if out.Cmp(expected) != 0 {
835 t.Errorf("#%d: got %s want %s", i, out, expected)
841 func TestLshSelf(t *testing.T) {
842 for i, test := range lshTests {
843 z, _ := new(Int).SetString(test.in, 10)
844 expected, _ := new(Int).SetString(test.out, 10)
847 if !isNormalized(z) {
848 t.Errorf("#%d: %v is not normalized", i, *z)
850 if z.Cmp(expected) != 0 {
851 t.Errorf("#%d: got %s want %s", i, z, expected)
857 func TestLshRsh(t *testing.T) {
858 for i, test := range rshTests {
859 in, _ := new(Int).SetString(test.in, 10)
860 out := new(Int).Lsh(in, test.shift)
861 out = out.Rsh(out, test.shift)
863 if !isNormalized(out) {
864 t.Errorf("#%d: %v is not normalized", i, *out)
866 if in.Cmp(out) != 0 {
867 t.Errorf("#%d: got %s want %s", i, out, in)
870 for i, test := range lshTests {
871 in, _ := new(Int).SetString(test.in, 10)
872 out := new(Int).Lsh(in, test.shift)
873 out.Rsh(out, test.shift)
875 if !isNormalized(out) {
876 t.Errorf("#%d: %v is not normalized", i, *out)
878 if in.Cmp(out) != 0 {
879 t.Errorf("#%d: got %s want %s", i, out, in)
885 var int64Tests = []int64{
894 -9223372036854775807,
895 -9223372036854775808,
899 func TestInt64(t *testing.T) {
900 for i, testVal := range int64Tests {
901 in := NewInt(testVal)
905 t.Errorf("#%d got %d want %d", i, out, testVal)
911 var bitwiseTests = []struct {
913 and, or, xor, andNot string
915 {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
916 {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
917 {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
918 {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
919 {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
920 {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
921 {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
922 {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
923 {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
924 {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
925 {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
926 {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
927 {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
929 "0x1000009dc6e3d9822cba04129bcbe3401",
930 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
931 "0x1000001186210100001000009048c2001",
932 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
933 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
934 "0x8c40c2d8822caa04120b8321400",
937 "0x1000009dc6e3d9822cba04129bcbe3401",
938 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
939 "0x8c40c2d8822caa04120b8321401",
940 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
941 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
942 "0x1000001186210100001000009048c2000",
945 "-0x1000009dc6e3d9822cba04129bcbe3401",
946 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
947 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
948 "-0x1000001186210100001000009048c2001",
949 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
950 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
955 type bitFun func(z, x, y *Int) *Int
957 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
959 expected.SetString(exp, 0)
961 out := f(new(Int), x, y)
962 if out.Cmp(expected) != 0 {
963 t.Errorf("%s: got %s want %s", msg, out, expected)
968 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
972 expected.SetString(exp, 0)
974 self = f(self, self, y)
975 if self.Cmp(expected) != 0 {
976 t.Errorf("%s: got %s want %s", msg, self, expected)
981 func TestBitwise(t *testing.T) {
984 for _, test := range bitwiseTests {
985 x.SetString(test.x, 0)
986 y.SetString(test.y, 0)
988 testBitFun(t, "and", (*Int).And, x, y, test.and)
989 testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
990 testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
991 testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
992 testBitFun(t, "or", (*Int).Or, x, y, test.or)
993 testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
994 testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
995 testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1000 var notTests = []struct {
1008 {"-81910", "81909"},
1010 "298472983472983471903246121093472394872319615612417471234712061",
1011 "-298472983472983471903246121093472394872319615612417471234712062",
1015 func TestNot(t *testing.T) {
1018 expected := new(Int)
1019 for i, test := range notTests {
1020 in.SetString(test.in, 10)
1021 expected.SetString(test.out, 10)
1023 if out.Cmp(expected) != 0 {
1024 t.Errorf("#%d: got %s want %s", i, out, expected)
1027 if out.Cmp(in) != 0 {
1028 t.Errorf("#%d: got %s want %s", i, out, in)
1034 var modInverseTests = []struct {
1040 {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1043 func TestModInverse(t *testing.T) {
1044 var element, prime Int
1046 for i, test := range modInverseTests {
1047 (&element).SetString(test.element, 10)
1048 (&prime).SetString(test.prime, 10)
1049 inverse := new(Int).ModInverse(&element, &prime)
1050 inverse.Mul(inverse, &element)
1051 inverse.Mod(inverse, &prime)
1052 if inverse.Cmp(one) != 0 {
1053 t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
1059 var gobEncodingTests = []string{
1066 "298472983472983471903246121093472394872319615612417471234712061",
1069 func TestGobEncoding(t *testing.T) {
1070 var medium bytes.Buffer
1071 enc := gob.NewEncoder(&medium)
1072 dec := gob.NewDecoder(&medium)
1073 for i, test := range gobEncodingTests {
1074 for j := 0; j < 2; j++ {
1075 medium.Reset() // empty buffer for each test case (in case of failures)
1081 tx.SetString(stest, 10)
1082 if err := enc.Encode(&tx); err != nil {
1083 t.Errorf("#%d%c: encoding failed: %s", i, 'a'+j, err)
1086 if err := dec.Decode(&rx); err != nil {
1087 t.Errorf("#%d%c: decoding failed: %s", i, 'a'+j, err)
1089 if rx.Cmp(&tx) != 0 {
1090 t.Errorf("#%d%c: transmission failed: got %s want %s", i, 'a'+j, &rx, &tx)