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.
20 func isNormalized(x *Int) bool {
25 return x.abs[len(x.abs)-1] != 0
28 type funZZ func(z, x, y *Int) *Int
34 {NewInt(0), NewInt(0), NewInt(0)},
35 {NewInt(1), NewInt(1), NewInt(0)},
36 {NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
37 {NewInt(-1), NewInt(-1), NewInt(0)},
38 {NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
39 {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
50 func TestSignZ(t *testing.T) {
52 for _, a := range sumZZ {
56 t.Errorf("got %d; want %d for z = %v", s, e, a.z)
61 func TestSetZ(t *testing.T) {
62 for _, a := range sumZZ {
65 if !isNormalized(&z) {
66 t.Errorf("%v is not normalized", z)
68 if (&z).Cmp(a.z) != 0 {
69 t.Errorf("got z = %v; want %v", z, a.z)
74 func TestAbsZ(t *testing.T) {
76 for _, a := range sumZZ {
85 t.Errorf("got z = %v; want %v", z, e)
90 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
93 if !isNormalized(&z) {
94 t.Errorf("%s%v is not normalized", msg, z)
96 if (&z).Cmp(a.z) != 0 {
97 t.Errorf("%v %s %v\n\tgot z = %v; want %v", a.x, msg, a.y, &z, a.z)
101 func TestSumZZ(t *testing.T) {
102 AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
103 SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
104 for _, a := range sumZZ {
106 testFunZZ(t, "AddZZ", AddZZ, arg)
108 arg = argZZ{a.z, a.y, a.x}
109 testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
111 arg = argZZ{a.x, a.z, a.y}
112 testFunZZ(t, "SubZZ", SubZZ, arg)
114 arg = argZZ{a.y, a.z, a.x}
115 testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
119 func TestProdZZ(t *testing.T) {
120 MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
121 for _, a := range prodZZ {
123 testFunZZ(t, "MulZZ", MulZZ, arg)
125 arg = argZZ{a.z, a.y, a.x}
126 testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
130 // mulBytes returns x*y via grade school multiplication. Both inputs
131 // and the result are assumed to be in big-endian representation (to
132 // match the semantics of Int.Bytes and Int.SetBytes).
133 func mulBytes(x, y []byte) []byte {
134 z := make([]byte, len(x)+len(y))
138 for j := len(y) - 1; j >= 0; j-- {
143 for i := len(x) - 1; i >= 0; i-- {
144 t := int(z[k]) + int(x[i])*d + carry
145 z[k], carry = byte(t), t>>8
153 // normalize (remove leading 0's)
155 for i < len(z) && z[i] == 0 {
162 func checkMul(a, b []byte) bool {
169 z2.SetBytes(mulBytes(a, b))
171 return z1.Cmp(&z2) == 0
174 func TestMul(t *testing.T) {
175 if err := quick.Check(checkMul, nil); err != nil {
180 var mulRangesZ = []struct {
184 // entirely positive ranges are covered by mulRangesN
191 {0, -1, "1"}, // empty range
192 {-1, -100, "1"}, // empty range
193 {-1, 1, "0"}, // range includes 0
194 {-1e9, 0, "0"}, // range includes 0
195 {-1e9, 1e9, "0"}, // range includes 0
196 {-10, -1, "3628800"}, // 10!
197 {-20, -2, "-2432902008176640000"}, // -20!
199 "-933262154439441526816992388562667004907159682643816214685929" +
200 "638952175999932299156089414639761565182862536979208272237582" +
201 "511852109168640000000000000000000000", // -99!
205 func TestMulRangeZ(t *testing.T) {
207 // test entirely positive ranges
208 for i, r := range mulRangesN {
209 prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
211 t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
215 for i, r := range mulRangesZ {
216 prod := tmp.MulRange(r.a, r.b).String()
218 t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
223 func TestBinomial(t *testing.T) {
225 for _, test := range []struct {
244 {100, 10, "17310309456440"},
245 {100, 90, "17310309456440"},
246 {1000, 10, "263409560461970212832400"},
247 {1000, 990, "263409560461970212832400"},
249 if got := z.Binomial(test.n, test.k).String(); got != test.want {
250 t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
255 func BenchmarkBinomial(b *testing.B) {
257 for i := 0; i < b.N; i++ {
258 z.Binomial(1000, 990)
262 // Examples from the Go Language Spec, section "Arithmetic operators"
263 var divisionSignsTests = []struct {
265 q, r int64 // T-division
266 d, m int64 // Euclidean division
269 {-5, 3, -1, -2, -2, 1},
270 {5, -3, -1, 2, -1, 2},
271 {-5, -3, 1, -2, 2, 1},
276 func TestDivisionSigns(t *testing.T) {
277 for i, test := range divisionSignsTests {
285 q1 := new(Int).Quo(x, y)
286 r1 := new(Int).Rem(x, y)
287 if !isNormalized(q1) {
288 t.Errorf("#%d Quo: %v is not normalized", i, *q1)
290 if !isNormalized(r1) {
291 t.Errorf("#%d Rem: %v is not normalized", i, *r1)
293 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
294 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
297 q2, r2 := new(Int).QuoRem(x, y, new(Int))
298 if !isNormalized(q2) {
299 t.Errorf("#%d Quo: %v is not normalized", i, *q2)
301 if !isNormalized(r2) {
302 t.Errorf("#%d Rem: %v is not normalized", i, *r2)
304 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
305 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
308 d1 := new(Int).Div(x, y)
309 m1 := new(Int).Mod(x, y)
310 if !isNormalized(d1) {
311 t.Errorf("#%d Div: %v is not normalized", i, *d1)
313 if !isNormalized(m1) {
314 t.Errorf("#%d Mod: %v is not normalized", i, *m1)
316 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
317 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
320 d2, m2 := new(Int).DivMod(x, y, new(Int))
321 if !isNormalized(d2) {
322 t.Errorf("#%d Div: %v is not normalized", i, *d2)
324 if !isNormalized(m2) {
325 t.Errorf("#%d Mod: %v is not normalized", i, *m2)
327 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
328 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
333 func norm(x nat) nat {
335 for i > 0 && x[i-1] == 0 {
341 func TestBits(t *testing.T) {
342 for _, test := range []nat{
348 {4, 3, 2, 1, 0, 0, 0, 0},
352 got := z.SetBits(test)
354 if got.abs.cmp(want) != 0 {
355 t.Errorf("SetBits(%v) = %v; want %v", test, got.abs, want)
359 t.Errorf("SetBits(%v): got negative result", test)
362 bits := nat(z.Bits())
363 if bits.cmp(want) != 0 {
364 t.Errorf("%v.Bits() = %v; want %v", z.abs, bits, want)
369 func checkSetBytes(b []byte) bool {
370 hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
371 hex2 := hex.EncodeToString(b)
373 for len(hex1) < len(hex2) {
377 for len(hex1) > len(hex2) {
384 func TestSetBytes(t *testing.T) {
385 if err := quick.Check(checkSetBytes, nil); err != nil {
390 func checkBytes(b []byte) bool {
391 // trim leading zero bytes since Bytes() won't return them
393 for len(b) > 0 && b[0] == 0 {
396 b2 := new(Int).SetBytes(b).Bytes()
397 return bytes.Equal(b, b2)
400 func TestBytes(t *testing.T) {
401 if err := quick.Check(checkBytes, nil); err != nil {
406 func checkQuo(x, y []byte) bool {
407 u := new(Int).SetBytes(x)
408 v := new(Int).SetBytes(y)
415 q, r := new(Int).QuoRem(u, v, r)
421 uprime := new(Int).Set(q)
422 uprime.Mul(uprime, v)
423 uprime.Add(uprime, r)
425 return uprime.Cmp(u) == 0
428 var quoTests = []struct {
433 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
434 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
439 "11510768301994997771168",
440 "1328165573307167369775",
442 "885443715537658812968",
446 func TestQuo(t *testing.T) {
447 if err := quick.Check(checkQuo, nil); err != nil {
451 for i, test := range quoTests {
452 x, _ := new(Int).SetString(test.x, 10)
453 y, _ := new(Int).SetString(test.y, 10)
454 expectedQ, _ := new(Int).SetString(test.q, 10)
455 expectedR, _ := new(Int).SetString(test.r, 10)
458 q, r := new(Int).QuoRem(x, y, r)
460 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
461 t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
466 func TestQuoStepD6(t *testing.T) {
467 // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
468 // a code path which only triggers 1 in 10^{-19} cases.
470 u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
471 v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
474 q, r := new(Int).QuoRem(u, v, r)
475 const expectedQ64 = "18446744073709551613"
476 const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
477 const expectedQ32 = "4294967293"
478 const expectedR32 = "39614081266355540837921718287"
479 if q.String() != expectedQ64 && q.String() != expectedQ32 ||
480 r.String() != expectedR64 && r.String() != expectedR32 {
481 t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
485 func BenchmarkQuoRem(b *testing.B) {
486 x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
487 y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
492 for i := 0; i < b.N; i++ {
497 var bitLenTests = []struct {
509 {"0x800000000000", 48},
510 {"0x8000000000000000", 64},
511 {"0x80000000000000000000", 80},
512 {"-0x4000000000000000000000", 87},
515 func TestBitLen(t *testing.T) {
516 for i, test := range bitLenTests {
517 x, ok := new(Int).SetString(test.in, 0)
519 t.Errorf("#%d test input invalid: %s", i, test.in)
523 if n := x.BitLen(); n != test.out {
524 t.Errorf("#%d got %d want %d", i, n, test.out)
529 var expTests = []struct {
536 {"-10", "0", "", "1"},
537 {"1234", "-1", "", "1"},
538 {"1234", "-1", "0", "1"},
539 {"17", "-100", "1234", "865"},
540 {"2", "-100", "1234", ""},
543 {"0", "0", "1", "0"},
544 {"1", "0", "1", "0"},
545 {"-10", "0", "1", "0"},
546 {"1234", "-1", "1", "0"},
549 {"5", "1", "3", "2"},
550 {"5", "-7", "", "1"},
551 {"-5", "-7", "", "1"},
553 {"-5", "0", "", "1"},
555 {"-5", "1", "", "-5"},
556 {"-5", "1", "7", "2"},
557 {"-2", "3", "2", "0"},
558 {"5", "2", "", "25"},
559 {"1", "65537", "2", "1"},
560 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
561 {"0x8000000000000000", "2", "6719", "4944"},
562 {"0x8000000000000000", "3", "6719", "5447"},
563 {"0x8000000000000000", "1000", "6719", "1603"},
564 {"0x8000000000000000", "1000000", "6719", "3199"},
565 {"0x8000000000000000", "-1000000", "6719", "3663"}, // 3663 = ModInverse(3199, 6719) Issue #25865
567 {"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
570 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
571 "298472983472983471903246121093472394872319615612417471234712061",
572 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
573 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
575 // test case for issue 8822
577 "11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
578 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
579 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
580 "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
583 "-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
584 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
585 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
586 "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
589 // test cases for issue 13907
590 {"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
591 {"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
592 {"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
593 {"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
597 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
598 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", // odd
599 "0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
603 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
604 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", // even
605 "0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
609 func TestExp(t *testing.T) {
610 for i, test := range expTests {
611 x, ok1 := new(Int).SetString(test.x, 0)
612 y, ok2 := new(Int).SetString(test.y, 0)
617 if len(test.out) == 0 {
620 out, ok3 = new(Int).SetString(test.out, 0)
623 if len(test.m) == 0 {
626 m, ok4 = new(Int).SetString(test.m, 0)
629 if !ok1 || !ok2 || !ok3 || !ok4 {
630 t.Errorf("#%d: error in input", i)
634 z1 := new(Int).Exp(x, y, m)
635 if z1 != nil && !isNormalized(z1) {
636 t.Errorf("#%d: %v is not normalized", i, *z1)
638 if !(z1 == nil && out == nil || z1.Cmp(out) == 0) {
639 t.Errorf("#%d: got %x want %x", i, z1, out)
643 // The result should be the same as for m == 0;
644 // specifically, there should be no div-zero panic.
645 m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
646 z2 := new(Int).Exp(x, y, m)
648 t.Errorf("#%d: got %x want %x", i, z2, z1)
654 func BenchmarkExp(b *testing.B) {
655 x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
656 y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
657 n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
659 for i := 0; i < b.N; i++ {
664 func BenchmarkExpMont(b *testing.B) {
665 x, _ := new(Int).SetString("297778224889315382157302278696111964193", 0)
666 y, _ := new(Int).SetString("2548977943381019743024248146923164919440527843026415174732254534318292492375775985739511369575861449426580651447974311336267954477239437734832604782764979371984246675241012538135715981292390886872929238062252506842498360562303324154310849745753254532852868768268023732398278338025070694508489163836616810661033068070127919590264734220833816416141878688318329193389865030063416339367925710474801991305827284114894677717927892032165200876093838921477120036402410731159852999623461591709308405270748511350289172153076023215", 0)
667 var mods = []struct {
671 {"Odd", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF"},
672 {"Even1", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FE"},
673 {"Even2", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FC"},
674 {"Even3", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F8"},
675 {"Even4", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F0"},
676 {"Even8", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B21828100"},
677 {"Even32", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B00000000"},
678 {"Even64", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FF0000000000000000"},
679 {"Even96", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828283000000000000000000000000"},
680 {"Even128", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF00000000000000000000000000000000"},
681 {"Even255", "0x82828282828200FFFF28FF2B218281FF8000000000000000000000000000000000000000000000000000000000000000"},
682 {"SmallEven1", "0x7E"},
683 {"SmallEven2", "0x7C"},
684 {"SmallEven3", "0x78"},
685 {"SmallEven4", "0x70"},
687 for _, mod := range mods {
688 n, _ := new(Int).SetString(mod.val, 0)
690 b.Run(mod.name, func(b *testing.B) {
692 for i := 0; i < b.N; i++ {
699 func BenchmarkExp2(b *testing.B) {
700 x, _ := new(Int).SetString("2", 0)
701 y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
702 n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
704 for i := 0; i < b.N; i++ {
709 func checkGcd(aBytes, bBytes []byte) bool {
712 a := new(Int).SetBytes(aBytes)
713 b := new(Int).SetBytes(bBytes)
715 d := new(Int).GCD(x, y, a, b)
723 // euclidExtGCD is a reference implementation of Euclid's
724 // extended GCD algorithm for testing against optimized algorithms.
725 // Requirements: a, b > 0
726 func euclidExtGCD(a, b *Int) (g, x, y *Int) {
732 Ua := new(Int).SetInt64(1)
736 Vb := new(Int).SetInt64(1)
743 q, r = q.QuoRem(A, B, r)
747 // Ua, Ub = Ub, Ua-q*Ub
753 // Va, Vb = Vb, Va-q*Vb
762 func checkLehmerGcd(aBytes, bBytes []byte) bool {
763 a := new(Int).SetBytes(aBytes)
764 b := new(Int).SetBytes(bBytes)
766 if a.Sign() <= 0 || b.Sign() <= 0 {
767 return true // can only test positive arguments
770 d := new(Int).lehmerGCD(nil, nil, a, b)
771 d0, _, _ := euclidExtGCD(a, b)
773 return d.Cmp(d0) == 0
776 func checkLehmerExtGcd(aBytes, bBytes []byte) bool {
777 a := new(Int).SetBytes(aBytes)
778 b := new(Int).SetBytes(bBytes)
782 if a.Sign() <= 0 || b.Sign() <= 0 {
783 return true // can only test positive arguments
786 d := new(Int).lehmerGCD(x, y, a, b)
787 d0, x0, y0 := euclidExtGCD(a, b)
789 return d.Cmp(d0) == 0 && x.Cmp(x0) == 0 && y.Cmp(y0) == 0
792 var gcdTests = []struct {
796 {"0", "0", "0", "0", "0"},
797 {"7", "0", "1", "0", "7"},
798 {"7", "0", "-1", "0", "-7"},
799 {"11", "1", "0", "11", "0"},
800 {"7", "-1", "-2", "-77", "35"},
801 {"935", "-3", "8", "64515", "24310"},
802 {"935", "-3", "-8", "64515", "-24310"},
803 {"935", "3", "-8", "-64515", "-24310"},
805 {"1", "-9", "47", "120", "23"},
806 {"7", "1", "-2", "77", "35"},
807 {"935", "-3", "8", "64515", "24310"},
808 {"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
809 {"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
812 func testGcd(t *testing.T, d, x, y, a, b *Int) {
822 D := new(Int).GCD(X, Y, a, b)
824 t.Errorf("GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
826 if x != nil && X.Cmp(x) != 0 {
827 t.Errorf("GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
829 if y != nil && Y.Cmp(y) != 0 {
830 t.Errorf("GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
833 // check results in presence of aliasing (issue #11284)
834 a2 := new(Int).Set(a)
835 b2 := new(Int).Set(b)
836 a2.GCD(X, Y, a2, b2) // result is same as 1st argument
838 t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, a2, d)
840 if x != nil && X.Cmp(x) != 0 {
841 t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
843 if y != nil && Y.Cmp(y) != 0 {
844 t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
849 b2.GCD(X, Y, a2, b2) // result is same as 2nd argument
851 t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, b2, d)
853 if x != nil && X.Cmp(x) != 0 {
854 t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
856 if y != nil && Y.Cmp(y) != 0 {
857 t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
862 D = new(Int).GCD(a2, b2, a2, b2) // x = a, y = b
864 t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
866 if x != nil && a2.Cmp(x) != 0 {
867 t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, a2, x)
869 if y != nil && b2.Cmp(y) != 0 {
870 t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, b2, y)
875 D = new(Int).GCD(b2, a2, a2, b2) // x = b, y = a
877 t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
879 if x != nil && b2.Cmp(x) != 0 {
880 t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, b2, x)
882 if y != nil && a2.Cmp(y) != 0 {
883 t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, a2, y)
887 func TestGcd(t *testing.T) {
888 for _, test := range gcdTests {
889 d, _ := new(Int).SetString(test.d, 0)
890 x, _ := new(Int).SetString(test.x, 0)
891 y, _ := new(Int).SetString(test.y, 0)
892 a, _ := new(Int).SetString(test.a, 0)
893 b, _ := new(Int).SetString(test.b, 0)
895 testGcd(t, d, nil, nil, a, b)
896 testGcd(t, d, x, nil, a, b)
897 testGcd(t, d, nil, y, a, b)
898 testGcd(t, d, x, y, a, b)
901 if err := quick.Check(checkGcd, nil); err != nil {
905 if err := quick.Check(checkLehmerGcd, nil); err != nil {
909 if err := quick.Check(checkLehmerExtGcd, nil); err != nil {
914 type intShiftTest struct {
920 var rshTests = []intShiftTest{
936 {"4294967296", 0, "4294967296"},
937 {"4294967296", 1, "2147483648"},
938 {"4294967296", 2, "1073741824"},
939 {"18446744073709551616", 0, "18446744073709551616"},
940 {"18446744073709551616", 1, "9223372036854775808"},
941 {"18446744073709551616", 2, "4611686018427387904"},
942 {"18446744073709551616", 64, "1"},
943 {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
944 {"340282366920938463463374607431768211456", 128, "1"},
947 func TestRsh(t *testing.T) {
948 for i, test := range rshTests {
949 in, _ := new(Int).SetString(test.in, 10)
950 expected, _ := new(Int).SetString(test.out, 10)
951 out := new(Int).Rsh(in, test.shift)
953 if !isNormalized(out) {
954 t.Errorf("#%d: %v is not normalized", i, *out)
956 if out.Cmp(expected) != 0 {
957 t.Errorf("#%d: got %s want %s", i, out, expected)
962 func TestRshSelf(t *testing.T) {
963 for i, test := range rshTests {
964 z, _ := new(Int).SetString(test.in, 10)
965 expected, _ := new(Int).SetString(test.out, 10)
968 if !isNormalized(z) {
969 t.Errorf("#%d: %v is not normalized", i, *z)
971 if z.Cmp(expected) != 0 {
972 t.Errorf("#%d: got %s want %s", i, z, expected)
977 var lshTests = []intShiftTest{
988 {"4294967296", 0, "4294967296"},
989 {"4294967296", 1, "8589934592"},
990 {"4294967296", 2, "17179869184"},
991 {"18446744073709551616", 0, "18446744073709551616"},
992 {"9223372036854775808", 1, "18446744073709551616"},
993 {"4611686018427387904", 2, "18446744073709551616"},
994 {"1", 64, "18446744073709551616"},
995 {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
996 {"1", 128, "340282366920938463463374607431768211456"},
999 func TestLsh(t *testing.T) {
1000 for i, test := range lshTests {
1001 in, _ := new(Int).SetString(test.in, 10)
1002 expected, _ := new(Int).SetString(test.out, 10)
1003 out := new(Int).Lsh(in, test.shift)
1005 if !isNormalized(out) {
1006 t.Errorf("#%d: %v is not normalized", i, *out)
1008 if out.Cmp(expected) != 0 {
1009 t.Errorf("#%d: got %s want %s", i, out, expected)
1014 func TestLshSelf(t *testing.T) {
1015 for i, test := range lshTests {
1016 z, _ := new(Int).SetString(test.in, 10)
1017 expected, _ := new(Int).SetString(test.out, 10)
1018 z.Lsh(z, test.shift)
1020 if !isNormalized(z) {
1021 t.Errorf("#%d: %v is not normalized", i, *z)
1023 if z.Cmp(expected) != 0 {
1024 t.Errorf("#%d: got %s want %s", i, z, expected)
1029 func TestLshRsh(t *testing.T) {
1030 for i, test := range rshTests {
1031 in, _ := new(Int).SetString(test.in, 10)
1032 out := new(Int).Lsh(in, test.shift)
1033 out = out.Rsh(out, test.shift)
1035 if !isNormalized(out) {
1036 t.Errorf("#%d: %v is not normalized", i, *out)
1038 if in.Cmp(out) != 0 {
1039 t.Errorf("#%d: got %s want %s", i, out, in)
1042 for i, test := range lshTests {
1043 in, _ := new(Int).SetString(test.in, 10)
1044 out := new(Int).Lsh(in, test.shift)
1045 out.Rsh(out, test.shift)
1047 if !isNormalized(out) {
1048 t.Errorf("#%d: %v is not normalized", i, *out)
1050 if in.Cmp(out) != 0 {
1051 t.Errorf("#%d: got %s want %s", i, out, in)
1056 // Entries must be sorted by value in ascending order.
1057 var cmpAbsTests = []string{
1063 "2783678367462374683678456387645876387564783686583485",
1064 "2783678367462374683678456387645876387564783686583486",
1065 "32957394867987420967976567076075976570670947609750670956097509670576075067076027578341538",
1068 func TestCmpAbs(t *testing.T) {
1069 values := make([]*Int, len(cmpAbsTests))
1071 for i, s := range cmpAbsTests {
1072 x, ok := new(Int).SetString(s, 0)
1074 t.Fatalf("SetString(%s, 0) failed", s)
1076 if prev != nil && prev.Cmp(x) >= 0 {
1077 t.Fatal("cmpAbsTests entries not sorted in ascending order")
1083 for i, x := range values {
1084 for j, y := range values {
1085 // try all combinations of signs for x, y
1086 for k := 0; k < 4; k++ {
1106 t.Errorf("absCmp |%s|, |%s|: got %d; want %d", &a, &b, got, want)
1113 func TestIntCmpSelf(t *testing.T) {
1114 for _, s := range cmpAbsTests {
1115 x, ok := new(Int).SetString(s, 0)
1117 t.Fatalf("SetString(%s, 0) failed", s)
1122 t.Errorf("x = %s: x.Cmp(x): got %d; want %d", x, got, want)
1127 var int64Tests = []string{
1136 "9223372036854775807",
1137 "-9223372036854775807",
1138 "-9223372036854775808",
1141 "0x8000000000000000",
1142 "-0x8000000000000001",
1143 "38579843757496759476987459679745",
1144 "-38579843757496759476987459679745",
1147 func TestInt64(t *testing.T) {
1148 for _, s := range int64Tests {
1150 _, ok := x.SetString(s, 0)
1152 t.Errorf("SetString(%s, 0) failed", s)
1156 want, err := strconv.ParseInt(s, 0, 64)
1158 if err.(*strconv.NumError).Err == strconv.ErrRange {
1160 t.Errorf("IsInt64(%s) succeeded unexpectedly", s)
1163 t.Errorf("ParseInt(%s) failed", s)
1169 t.Errorf("IsInt64(%s) failed unexpectedly", s)
1174 t.Errorf("Int64(%s) = %d; want %d", s, got, want)
1179 var uint64Tests = []string{
1187 "9223372036854775807",
1188 "9223372036854775808",
1189 "0x08000000000000000",
1192 "0x10000000000000000",
1193 "-0x08000000000000000",
1197 func TestUint64(t *testing.T) {
1198 for _, s := range uint64Tests {
1200 _, ok := x.SetString(s, 0)
1202 t.Errorf("SetString(%s, 0) failed", s)
1206 want, err := strconv.ParseUint(s, 0, 64)
1208 // check for sign explicitly (ErrRange doesn't cover signed input)
1209 if s[0] == '-' || err.(*strconv.NumError).Err == strconv.ErrRange {
1211 t.Errorf("IsUint64(%s) succeeded unexpectedly", s)
1214 t.Errorf("ParseUint(%s) failed", s)
1220 t.Errorf("IsUint64(%s) failed unexpectedly", s)
1225 t.Errorf("Uint64(%s) = %d; want %d", s, got, want)
1230 var bitwiseTests = []struct {
1232 and, or, xor, andNot string
1234 {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
1235 {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
1236 {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1237 {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1238 {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1239 {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1240 {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1241 {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1242 {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1243 {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1244 {"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
1245 {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1246 {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1247 {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1249 "0x1000009dc6e3d9822cba04129bcbe3401",
1250 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1251 "0x1000001186210100001000009048c2001",
1252 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1253 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1254 "0x8c40c2d8822caa04120b8321400",
1257 "0x1000009dc6e3d9822cba04129bcbe3401",
1258 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1259 "0x8c40c2d8822caa04120b8321401",
1260 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1261 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1262 "0x1000001186210100001000009048c2000",
1265 "-0x1000009dc6e3d9822cba04129bcbe3401",
1266 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1267 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1268 "-0x1000001186210100001000009048c2001",
1269 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1270 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1274 type bitFun func(z, x, y *Int) *Int
1276 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1277 expected := new(Int)
1278 expected.SetString(exp, 0)
1280 out := f(new(Int), x, y)
1281 if out.Cmp(expected) != 0 {
1282 t.Errorf("%s: got %s want %s", msg, out, expected)
1286 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1289 expected := new(Int)
1290 expected.SetString(exp, 0)
1292 self = f(self, self, y)
1293 if self.Cmp(expected) != 0 {
1294 t.Errorf("%s: got %s want %s", msg, self, expected)
1298 func altBit(x *Int, i int) uint {
1299 z := new(Int).Rsh(x, uint(i))
1300 z = z.And(z, NewInt(1))
1301 if z.Cmp(new(Int)) != 0 {
1307 func altSetBit(z *Int, x *Int, i int, b uint) *Int {
1309 m := one.Lsh(one, uint(i))
1314 return z.AndNot(x, m)
1316 panic("set bit is not 0 or 1")
1319 func testBitset(t *testing.T, x *Int) {
1321 z := new(Int).Set(x)
1322 z1 := new(Int).Set(x)
1323 for i := 0; i < n+10; i++ {
1325 old1 := altBit(z1, i)
1327 t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1329 z := new(Int).SetBit(z, i, 1)
1330 z1 := altSetBit(new(Int), z1, i, 1)
1332 t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1335 t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1338 altSetBit(z1, z1, i, 0)
1340 t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1343 t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1345 altSetBit(z1, z1, i, old)
1348 t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1352 t.Errorf("bitset: got %s want %s", z, x)
1356 var bitsetTests = []struct {
1367 {"0x2000000000000000000000000000", 108, 0},
1368 {"0x2000000000000000000000000000", 109, 1},
1369 {"0x2000000000000000000000000000", 110, 0},
1370 {"-0x2000000000000000000000000001", 108, 1},
1371 {"-0x2000000000000000000000000001", 109, 0},
1372 {"-0x2000000000000000000000000001", 110, 1},
1375 func TestBitSet(t *testing.T) {
1376 for _, test := range bitwiseTests {
1378 x.SetString(test.x, 0)
1381 x.SetString(test.y, 0)
1384 for i, test := range bitsetTests {
1386 x.SetString(test.x, 0)
1389 t.Errorf("#%d got %v want %v", i, b, test.b)
1393 z.SetBit(NewInt(0), 2, 1)
1394 if z.Cmp(NewInt(4)) != 0 {
1395 t.Errorf("destination leaked into result; got %s want 4", z)
1399 var tzbTests = []struct {
1408 {"0x4000000000000000000", 74},
1409 {"-0x8000000000000000000", 75},
1412 func TestTrailingZeroBits(t *testing.T) {
1413 for i, test := range tzbTests {
1414 in, _ := new(Int).SetString(test.in, 0)
1416 got := in.TrailingZeroBits()
1419 t.Errorf("#%d: got %v want %v", i, got, want)
1424 func BenchmarkBitset(b *testing.B) {
1428 for i := b.N - 1; i >= 0; i-- {
1429 z.SetBit(z, i&512, 1)
1433 func BenchmarkBitsetNeg(b *testing.B) {
1437 for i := b.N - 1; i >= 0; i-- {
1438 z.SetBit(z, i&512, 0)
1442 func BenchmarkBitsetOrig(b *testing.B) {
1444 altSetBit(z, z, 512, 1)
1446 for i := b.N - 1; i >= 0; i-- {
1447 altSetBit(z, z, i&512, 1)
1451 func BenchmarkBitsetNegOrig(b *testing.B) {
1453 altSetBit(z, z, 512, 0)
1455 for i := b.N - 1; i >= 0; i-- {
1456 altSetBit(z, z, i&512, 0)
1460 // tri generates the trinomial 2**(n*2) - 2**n - 1, which is always 3 mod 4 and
1461 // 7 mod 8, so that 2 is always a quadratic residue.
1462 func tri(n uint) *Int {
1465 x2 := new(Int).Lsh(x, n)
1471 func BenchmarkModSqrt225_Tonelli(b *testing.B) {
1474 for i := 0; i < b.N; i++ {
1476 x.modSqrtTonelliShanks(x, p)
1480 func BenchmarkModSqrt225_3Mod4(b *testing.B) {
1482 x := new(Int).SetUint64(2)
1483 for i := 0; i < b.N; i++ {
1485 x.modSqrt3Mod4Prime(x, p)
1489 func BenchmarkModSqrt231_Tonelli(b *testing.B) {
1492 p.Sub(p, intOne) // tri(231) - 2 is a prime == 5 mod 8
1493 x := new(Int).SetUint64(7)
1494 for i := 0; i < b.N; i++ {
1496 x.modSqrtTonelliShanks(x, p)
1500 func BenchmarkModSqrt231_5Mod8(b *testing.B) {
1503 p.Sub(p, intOne) // tri(231) - 2 is a prime == 5 mod 8
1504 x := new(Int).SetUint64(7)
1505 for i := 0; i < b.N; i++ {
1507 x.modSqrt5Mod8Prime(x, p)
1511 func TestBitwise(t *testing.T) {
1514 for _, test := range bitwiseTests {
1515 x.SetString(test.x, 0)
1516 y.SetString(test.y, 0)
1518 testBitFun(t, "and", (*Int).And, x, y, test.and)
1519 testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
1520 testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1521 testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1522 testBitFun(t, "or", (*Int).Or, x, y, test.or)
1523 testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
1524 testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
1525 testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1529 var notTests = []struct {
1537 {"-81910", "81909"},
1539 "298472983472983471903246121093472394872319615612417471234712061",
1540 "-298472983472983471903246121093472394872319615612417471234712062",
1544 func TestNot(t *testing.T) {
1547 expected := new(Int)
1548 for i, test := range notTests {
1549 in.SetString(test.in, 10)
1550 expected.SetString(test.out, 10)
1552 if out.Cmp(expected) != 0 {
1553 t.Errorf("#%d: got %s want %s", i, out, expected)
1556 if out.Cmp(in) != 0 {
1557 t.Errorf("#%d: got %s want %s", i, out, in)
1562 var modInverseTests = []struct {
1566 {"1234567", "458948883992"},
1567 {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1568 {"-10", "13"}, // issue #16984
1573 func TestModInverse(t *testing.T) {
1574 var element, modulus, gcd, inverse Int
1576 for _, test := range modInverseTests {
1577 (&element).SetString(test.element, 10)
1578 (&modulus).SetString(test.modulus, 10)
1579 (&inverse).ModInverse(&element, &modulus)
1580 (&inverse).Mul(&inverse, &element)
1581 (&inverse).Mod(&inverse, &modulus)
1582 if (&inverse).Cmp(one) != 0 {
1583 t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
1586 // exhaustive test for small values
1587 for n := 2; n < 100; n++ {
1588 (&modulus).SetInt64(int64(n))
1589 for x := 1; x < n; x++ {
1590 (&element).SetInt64(int64(x))
1591 (&gcd).GCD(nil, nil, &element, &modulus)
1592 if (&gcd).Cmp(one) != 0 {
1595 (&inverse).ModInverse(&element, &modulus)
1596 (&inverse).Mul(&inverse, &element)
1597 (&inverse).Mod(&inverse, &modulus)
1598 if (&inverse).Cmp(one) != 0 {
1599 t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
1605 func BenchmarkModInverse(b *testing.B) {
1606 p := new(Int).SetInt64(1) // Mersenne prime 2**1279 -1
1607 p.abs = p.abs.shl(p.abs, 1279)
1609 x := new(Int).Sub(p, intOne)
1611 for i := 0; i < b.N; i++ {
1616 // testModSqrt is a helper for TestModSqrt,
1617 // which checks that ModSqrt can compute a square-root of elt^2.
1618 func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
1619 var sqChk, sqrtChk, sqrtsq Int
1622 z := sqrt.ModSqrt(sq, mod)
1624 t.Errorf("ModSqrt returned wrong value %s", z)
1627 // test ModSqrt arguments outside the range [0,mod)
1629 z = sqrtChk.ModSqrt(&sqChk, mod)
1630 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1631 t.Errorf("ModSqrt returned inconsistent value %s", z)
1634 z = sqrtChk.ModSqrt(&sqChk, mod)
1635 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1636 t.Errorf("ModSqrt returned inconsistent value %s", z)
1639 // test x aliasing z
1640 z = sqrtChk.ModSqrt(sqrtChk.Set(sq), mod)
1641 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1642 t.Errorf("ModSqrt returned inconsistent value %s", z)
1645 // make sure we actually got a square root
1646 if sqrt.Cmp(elt) == 0 {
1647 return true // we found the "desired" square root
1649 sqrtsq.Mul(sqrt, sqrt) // make sure we found the "other" one
1650 sqrtsq.Mod(&sqrtsq, mod)
1651 return sq.Cmp(&sqrtsq) == 0
1654 func TestModSqrt(t *testing.T) {
1655 var elt, mod, modx4, sq, sqrt Int
1656 r := rand.New(rand.NewSource(9))
1657 for i, s := range primes[1:] { // skip 2, use only odd primes
1658 mod.SetString(s, 10)
1661 // test a few random elements per prime
1662 for x := 1; x < 5; x++ {
1664 elt.Sub(&elt, &mod) // test range [-mod, 3*mod)
1665 if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
1666 t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
1670 if testing.Short() && i > 2 {
1675 if testing.Short() {
1679 // exhaustive test for small values
1680 for n := 3; n < 100; n++ {
1681 mod.SetInt64(int64(n))
1682 if !mod.ProbablyPrime(10) {
1685 isSquare := make([]bool, n)
1687 // test all the squares
1688 for x := 1; x < n; x++ {
1689 elt.SetInt64(int64(x))
1690 if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
1691 t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
1693 isSquare[sq.Uint64()] = true
1696 // test all non-squares
1697 for x := 1; x < n; x++ {
1698 sq.SetInt64(int64(x))
1699 z := sqrt.ModSqrt(&sq, &mod)
1700 if !isSquare[x] && z != nil {
1701 t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
1707 func TestJacobi(t *testing.T) {
1708 testCases := []struct {
1733 for i, test := range testCases {
1736 expected := test.result
1737 actual := Jacobi(&x, &y)
1738 if actual != expected {
1739 t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
1744 func TestJacobiPanic(t *testing.T) {
1745 const failureMsg = "test failure"
1748 if msg == nil || msg == failureMsg {
1755 // Jacobi should panic when the second argument is even.
1760 func TestIssue2607(t *testing.T) {
1761 // This code sequence used to hang.
1763 n.Rand(rand.New(rand.NewSource(9)), n)
1766 func TestSqrt(t *testing.T) {
1769 for i := 0; i < 10000; i++ {
1770 if (root+1)*(root+1) <= i {
1773 n := NewInt(int64(i))
1776 if r.Cmp(NewInt(int64(root))) != 0 {
1777 t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
1781 for i := 0; i < 1000; i += 10 {
1782 n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10)
1783 r := new(Int).Sqrt(n)
1784 root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10)
1785 if r.Cmp(root) != 0 {
1786 t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
1793 if r.Int64() != 10 {
1794 t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
1798 // We can't test this together with the other Exp tests above because
1799 // it requires a different receiver setup.
1800 func TestIssue22830(t *testing.T) {
1801 one := new(Int).SetInt64(1)
1802 base, _ := new(Int).SetString("84555555300000000000", 10)
1803 mod, _ := new(Int).SetString("66666670001111111111", 10)
1804 want, _ := new(Int).SetString("17888885298888888889", 10)
1806 var tests = []int64{
1810 for _, n := range tests {
1812 if got := m.Exp(base, one, mod); got.Cmp(want) != 0 {
1813 t.Errorf("(%v).Exp(%s, 1, %s) = %s, want %s", n, base, mod, got, want)
1818 func BenchmarkSqrt(b *testing.B) {
1819 n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10)
1822 for i := 0; i < b.N; i++ {
1827 func benchmarkIntSqr(b *testing.B, nwords int) {
1829 x.abs = rndNat(nwords)
1832 for i := 0; i < b.N; i++ {
1837 func BenchmarkIntSqr(b *testing.B) {
1838 for _, n := range sqrBenchSizes {
1839 if isRaceBuilder && n > 1e3 {
1842 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
1843 benchmarkIntSqr(b, n)
1848 func benchmarkDiv(b *testing.B, aSize, bSize int) {
1849 var r = rand.New(rand.NewSource(1234))
1850 aa := randInt(r, uint(aSize))
1851 bb := randInt(r, uint(bSize))
1859 for i := 0; i < b.N; i++ {
1864 func BenchmarkDiv(b *testing.B) {
1866 10, 20, 50, 100, 200, 500, 1000,
1869 for _, i := range sizes {
1871 b.Run(fmt.Sprintf("%d/%d", j, i), func(b *testing.B) {
1872 benchmarkDiv(b, j, i)
1877 func TestFillBytes(t *testing.T) {
1878 checkResult := func(t *testing.T, buf []byte, want *Int) {
1880 got := new(Int).SetBytes(buf)
1881 if got.CmpAbs(want) != 0 {
1882 t.Errorf("got 0x%x, want 0x%x: %x", got, want, buf)
1885 panics := func(f func()) (panic bool) {
1886 defer func() { panic = recover() != nil }()
1891 for _, n := range []string{
1896 "0xffffffffffffffff",
1897 "0x10000000000000000",
1898 "0xabababababababababababababababababababababababababa",
1899 "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
1901 t.Run(n, func(t *testing.T) {
1903 x, ok := new(Int).SetString(n, 0)
1905 panic("invalid test entry")
1908 // Perfectly sized buffer.
1909 byteLen := (x.BitLen() + 7) / 8
1910 buf := make([]byte, byteLen)
1911 checkResult(t, x.FillBytes(buf), x)
1913 // Way larger, checking all bytes get zeroed.
1914 buf = make([]byte, 100)
1915 for i := range buf {
1918 checkResult(t, x.FillBytes(buf), x)
1922 buf = make([]byte, byteLen-1)
1923 if !panics(func() { x.FillBytes(buf) }) {
1924 t.Errorf("expected panic for small buffer and value %x", x)
1931 func TestNewIntMinInt64(t *testing.T) {
1932 // Test for uint64 cast in NewInt.
1933 want := int64(math.MinInt64)
1934 if got := NewInt(want).Int64(); got != want {
1935 t.Fatalf("wanted %d, got %d", want, got)
1939 func TestNewIntAllocs(t *testing.T) {
1940 testenv.SkipIfOptimizationOff(t)
1941 for _, n := range []int64{0, 7, -7, 1 << 30, -1 << 30, 1 << 50, -1 << 50} {
1943 got := testing.AllocsPerRun(100, func() {
1944 // NewInt should inline, and all its allocations
1945 // can happen on the stack. Passing the result of NewInt
1946 // to Add should not cause any of those allocations to escape.
1950 t.Errorf("x.Add(x, NewInt(%d)), wanted 0 allocations, got %f", n, got)
1955 func TestToFloat64(t *testing.T) {
1956 for _, test := range []struct {
1961 {"-1000000000000000000000000000000000000000000000000000000", -1000000000000000078291540404596243842305360299886116864.000000, Below},
1962 {"-9223372036854775809", math.MinInt64, Above},
1963 {"-9223372036854775808", -9223372036854775808, Exact}, // -2^63
1964 {"-9223372036854775807", -9223372036854775807, Below},
1965 {"-18014398509481985", -18014398509481984.000000, Above},
1966 {"-18014398509481984", -18014398509481984.000000, Exact}, // -2^54
1967 {"-18014398509481983", -18014398509481984.000000, Below},
1968 {"-9007199254740993", -9007199254740992.000000, Above},
1969 {"-9007199254740992", -9007199254740992.000000, Exact}, // -2^53
1970 {"-9007199254740991", -9007199254740991.000000, Exact},
1971 {"-4503599627370497", -4503599627370497.000000, Exact},
1972 {"-4503599627370496", -4503599627370496.000000, Exact}, // -2^52
1973 {"-4503599627370495", -4503599627370495.000000, Exact},
1974 {"-12345", -12345, Exact},
1978 {"12345", 12345, Exact},
1979 {"0x1010000000000000", 0x1010000000000000, Exact}, // >2^53 but exact nonetheless
1980 {"9223372036854775807", 9223372036854775808, Above},
1981 {"9223372036854775808", 9223372036854775808, Exact}, // +2^63
1982 {"1000000000000000000000000000000000000000000000000000000", 1000000000000000078291540404596243842305360299886116864.000000, Above},
1984 i, ok := new(Int).SetString(test.istr, 0)
1986 t.Errorf("SetString(%s) failed", test.istr)
1990 // Test against expectation.
1991 f, acc := i.ToFloat64()
1992 if f != test.f || acc != test.acc {
1993 t.Errorf("%s: got %f (%s); want %f (%s)", test.istr, f, acc, test.f, test.acc)
1996 // Cross-check the fast path against the big.Float implementation.
1997 f2, acc2 := new(Float).SetInt(i).Float64()
1998 if f != f2 || acc != acc2 {
1999 t.Errorf("%s: got %f (%s); Float.Float64 gives %f (%s)", test.istr, f, acc, f2, acc2)