123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896 |
- // Copyright 2009 The Go Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style
- // license that can be found in the LICENSE file.
- package big
- import (
- "bytes"
- "encoding/hex"
- "fmt"
- "math/rand"
- "strconv"
- "strings"
- "testing"
- "testing/quick"
- )
- func isNormalized(x *Int) bool {
- if len(x.abs) == 0 {
- return !x.neg
- }
- // len(x.abs) > 0
- return x.abs[len(x.abs)-1] != 0
- }
- type funZZ func(z, x, y *Int) *Int
- type argZZ struct {
- z, x, y *Int
- }
- var sumZZ = []argZZ{
- {NewInt(0), NewInt(0), NewInt(0)},
- {NewInt(1), NewInt(1), NewInt(0)},
- {NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
- {NewInt(-1), NewInt(-1), NewInt(0)},
- {NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
- {NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
- }
- var prodZZ = []argZZ{
- {NewInt(0), NewInt(0), NewInt(0)},
- {NewInt(0), NewInt(1), NewInt(0)},
- {NewInt(1), NewInt(1), NewInt(1)},
- {NewInt(-991 * 991), NewInt(991), NewInt(-991)},
- // TODO(gri) add larger products
- }
- func TestSignZ(t *testing.T) {
- var zero Int
- for _, a := range sumZZ {
- s := a.z.Sign()
- e := a.z.Cmp(&zero)
- if s != e {
- t.Errorf("got %d; want %d for z = %v", s, e, a.z)
- }
- }
- }
- func TestSetZ(t *testing.T) {
- for _, a := range sumZZ {
- var z Int
- z.Set(a.z)
- if !isNormalized(&z) {
- t.Errorf("%v is not normalized", z)
- }
- if (&z).Cmp(a.z) != 0 {
- t.Errorf("got z = %v; want %v", z, a.z)
- }
- }
- }
- func TestAbsZ(t *testing.T) {
- var zero Int
- for _, a := range sumZZ {
- var z Int
- z.Abs(a.z)
- var e Int
- e.Set(a.z)
- if e.Cmp(&zero) < 0 {
- e.Sub(&zero, &e)
- }
- if z.Cmp(&e) != 0 {
- t.Errorf("got z = %v; want %v", z, e)
- }
- }
- }
- func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
- var z Int
- f(&z, a.x, a.y)
- if !isNormalized(&z) {
- t.Errorf("%s%v is not normalized", msg, z)
- }
- if (&z).Cmp(a.z) != 0 {
- t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
- }
- }
- func TestSumZZ(t *testing.T) {
- AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
- SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
- for _, a := range sumZZ {
- arg := a
- testFunZZ(t, "AddZZ", AddZZ, arg)
- arg = argZZ{a.z, a.y, a.x}
- testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
- arg = argZZ{a.x, a.z, a.y}
- testFunZZ(t, "SubZZ", SubZZ, arg)
- arg = argZZ{a.y, a.z, a.x}
- testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
- }
- }
- func TestProdZZ(t *testing.T) {
- MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
- for _, a := range prodZZ {
- arg := a
- testFunZZ(t, "MulZZ", MulZZ, arg)
- arg = argZZ{a.z, a.y, a.x}
- testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
- }
- }
- // mulBytes returns x*y via grade school multiplication. Both inputs
- // and the result are assumed to be in big-endian representation (to
- // match the semantics of Int.Bytes and Int.SetBytes).
- func mulBytes(x, y []byte) []byte {
- z := make([]byte, len(x)+len(y))
- // multiply
- k0 := len(z) - 1
- for j := len(y) - 1; j >= 0; j-- {
- d := int(y[j])
- if d != 0 {
- k := k0
- carry := 0
- for i := len(x) - 1; i >= 0; i-- {
- t := int(z[k]) + int(x[i])*d + carry
- z[k], carry = byte(t), t>>8
- k--
- }
- z[k] = byte(carry)
- }
- k0--
- }
- // normalize (remove leading 0's)
- i := 0
- for i < len(z) && z[i] == 0 {
- i++
- }
- return z[i:]
- }
- func checkMul(a, b []byte) bool {
- var x, y, z1 Int
- x.SetBytes(a)
- y.SetBytes(b)
- z1.Mul(&x, &y)
- var z2 Int
- z2.SetBytes(mulBytes(a, b))
- return z1.Cmp(&z2) == 0
- }
- func TestMul(t *testing.T) {
- if err := quick.Check(checkMul, nil); err != nil {
- t.Error(err)
- }
- }
- var mulRangesZ = []struct {
- a, b int64
- prod string
- }{
- // entirely positive ranges are covered by mulRangesN
- {-1, 1, "0"},
- {-2, -1, "2"},
- {-3, -2, "6"},
- {-3, -1, "-6"},
- {1, 3, "6"},
- {-10, -10, "-10"},
- {0, -1, "1"}, // empty range
- {-1, -100, "1"}, // empty range
- {-1, 1, "0"}, // range includes 0
- {-1e9, 0, "0"}, // range includes 0
- {-1e9, 1e9, "0"}, // range includes 0
- {-10, -1, "3628800"}, // 10!
- {-20, -2, "-2432902008176640000"}, // -20!
- {-99, -1,
- "-933262154439441526816992388562667004907159682643816214685929" +
- "638952175999932299156089414639761565182862536979208272237582" +
- "511852109168640000000000000000000000", // -99!
- },
- }
- func TestMulRangeZ(t *testing.T) {
- var tmp Int
- // test entirely positive ranges
- for i, r := range mulRangesN {
- prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
- if prod != r.prod {
- t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
- }
- }
- // test other ranges
- for i, r := range mulRangesZ {
- prod := tmp.MulRange(r.a, r.b).String()
- if prod != r.prod {
- t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
- }
- }
- }
- func TestBinomial(t *testing.T) {
- var z Int
- for _, test := range []struct {
- n, k int64
- want string
- }{
- {0, 0, "1"},
- {0, 1, "0"},
- {1, 0, "1"},
- {1, 1, "1"},
- {1, 10, "0"},
- {4, 0, "1"},
- {4, 1, "4"},
- {4, 2, "6"},
- {4, 3, "4"},
- {4, 4, "1"},
- {10, 1, "10"},
- {10, 9, "10"},
- {10, 5, "252"},
- {11, 5, "462"},
- {11, 6, "462"},
- {100, 10, "17310309456440"},
- {100, 90, "17310309456440"},
- {1000, 10, "263409560461970212832400"},
- {1000, 990, "263409560461970212832400"},
- } {
- if got := z.Binomial(test.n, test.k).String(); got != test.want {
- t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
- }
- }
- }
- func BenchmarkBinomial(b *testing.B) {
- var z Int
- for i := b.N - 1; i >= 0; i-- {
- z.Binomial(1000, 990)
- }
- }
- // Examples from the Go Language Spec, section "Arithmetic operators"
- var divisionSignsTests = []struct {
- x, y int64
- q, r int64 // T-division
- d, m int64 // Euclidean division
- }{
- {5, 3, 1, 2, 1, 2},
- {-5, 3, -1, -2, -2, 1},
- {5, -3, -1, 2, -1, 2},
- {-5, -3, 1, -2, 2, 1},
- {1, 2, 0, 1, 0, 1},
- {8, 4, 2, 0, 2, 0},
- }
- func TestDivisionSigns(t *testing.T) {
- for i, test := range divisionSignsTests {
- x := NewInt(test.x)
- y := NewInt(test.y)
- q := NewInt(test.q)
- r := NewInt(test.r)
- d := NewInt(test.d)
- m := NewInt(test.m)
- q1 := new(Int).Quo(x, y)
- r1 := new(Int).Rem(x, y)
- if !isNormalized(q1) {
- t.Errorf("#%d Quo: %v is not normalized", i, *q1)
- }
- if !isNormalized(r1) {
- t.Errorf("#%d Rem: %v is not normalized", i, *r1)
- }
- if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
- t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
- }
- q2, r2 := new(Int).QuoRem(x, y, new(Int))
- if !isNormalized(q2) {
- t.Errorf("#%d Quo: %v is not normalized", i, *q2)
- }
- if !isNormalized(r2) {
- t.Errorf("#%d Rem: %v is not normalized", i, *r2)
- }
- if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
- t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
- }
- d1 := new(Int).Div(x, y)
- m1 := new(Int).Mod(x, y)
- if !isNormalized(d1) {
- t.Errorf("#%d Div: %v is not normalized", i, *d1)
- }
- if !isNormalized(m1) {
- t.Errorf("#%d Mod: %v is not normalized", i, *m1)
- }
- if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
- t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
- }
- d2, m2 := new(Int).DivMod(x, y, new(Int))
- if !isNormalized(d2) {
- t.Errorf("#%d Div: %v is not normalized", i, *d2)
- }
- if !isNormalized(m2) {
- t.Errorf("#%d Mod: %v is not normalized", i, *m2)
- }
- if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
- t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
- }
- }
- }
- func norm(x nat) nat {
- i := len(x)
- for i > 0 && x[i-1] == 0 {
- i--
- }
- return x[:i]
- }
- func TestBits(t *testing.T) {
- for _, test := range []nat{
- nil,
- {0},
- {1},
- {0, 1, 2, 3, 4},
- {4, 3, 2, 1, 0},
- {4, 3, 2, 1, 0, 0, 0, 0},
- } {
- var z Int
- z.neg = true
- got := z.SetBits(test)
- want := norm(test)
- if got.abs.cmp(want) != 0 {
- t.Errorf("SetBits(%v) = %v; want %v", test, got.abs, want)
- }
- if got.neg {
- t.Errorf("SetBits(%v): got negative result", test)
- }
- bits := nat(z.Bits())
- if bits.cmp(want) != 0 {
- t.Errorf("%v.Bits() = %v; want %v", z.abs, bits, want)
- }
- }
- }
- func checkSetBytes(b []byte) bool {
- hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
- hex2 := hex.EncodeToString(b)
- for len(hex1) < len(hex2) {
- hex1 = "0" + hex1
- }
- for len(hex1) > len(hex2) {
- hex2 = "0" + hex2
- }
- return hex1 == hex2
- }
- func TestSetBytes(t *testing.T) {
- if err := quick.Check(checkSetBytes, nil); err != nil {
- t.Error(err)
- }
- }
- func checkBytes(b []byte) bool {
- // trim leading zero bytes since Bytes() won't return them
- // (was issue 12231)
- for len(b) > 0 && b[0] == 0 {
- b = b[1:]
- }
- b2 := new(Int).SetBytes(b).Bytes()
- return bytes.Equal(b, b2)
- }
- func TestBytes(t *testing.T) {
- if err := quick.Check(checkBytes, nil); err != nil {
- t.Error(err)
- }
- }
- func checkQuo(x, y []byte) bool {
- u := new(Int).SetBytes(x)
- v := new(Int).SetBytes(y)
- if len(v.abs) == 0 {
- return true
- }
- r := new(Int)
- q, r := new(Int).QuoRem(u, v, r)
- if r.Cmp(v) >= 0 {
- return false
- }
- uprime := new(Int).Set(q)
- uprime.Mul(uprime, v)
- uprime.Add(uprime, r)
- return uprime.Cmp(u) == 0
- }
- var quoTests = []struct {
- x, y string
- q, r string
- }{
- {
- "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
- "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
- "50911",
- "1",
- },
- {
- "11510768301994997771168",
- "1328165573307167369775",
- "8",
- "885443715537658812968",
- },
- }
- func TestQuo(t *testing.T) {
- if err := quick.Check(checkQuo, nil); err != nil {
- t.Error(err)
- }
- for i, test := range quoTests {
- x, _ := new(Int).SetString(test.x, 10)
- y, _ := new(Int).SetString(test.y, 10)
- expectedQ, _ := new(Int).SetString(test.q, 10)
- expectedR, _ := new(Int).SetString(test.r, 10)
- r := new(Int)
- q, r := new(Int).QuoRem(x, y, r)
- if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
- t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
- }
- }
- }
- func TestQuoStepD6(t *testing.T) {
- // See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
- // a code path which only triggers 1 in 10^{-19} cases.
- u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
- v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
- r := new(Int)
- q, r := new(Int).QuoRem(u, v, r)
- const expectedQ64 = "18446744073709551613"
- const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
- const expectedQ32 = "4294967293"
- const expectedR32 = "39614081266355540837921718287"
- if q.String() != expectedQ64 && q.String() != expectedQ32 ||
- r.String() != expectedR64 && r.String() != expectedR32 {
- t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
- }
- }
- func BenchmarkQuoRem(b *testing.B) {
- x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
- y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
- q := new(Int)
- r := new(Int)
- b.ResetTimer()
- for i := 0; i < b.N; i++ {
- q.QuoRem(y, x, r)
- }
- }
- var bitLenTests = []struct {
- in string
- out int
- }{
- {"-1", 1},
- {"0", 0},
- {"1", 1},
- {"2", 2},
- {"4", 3},
- {"0xabc", 12},
- {"0x8000", 16},
- {"0x80000000", 32},
- {"0x800000000000", 48},
- {"0x8000000000000000", 64},
- {"0x80000000000000000000", 80},
- {"-0x4000000000000000000000", 87},
- }
- func TestBitLen(t *testing.T) {
- for i, test := range bitLenTests {
- x, ok := new(Int).SetString(test.in, 0)
- if !ok {
- t.Errorf("#%d test input invalid: %s", i, test.in)
- continue
- }
- if n := x.BitLen(); n != test.out {
- t.Errorf("#%d got %d want %d", i, n, test.out)
- }
- }
- }
- var expTests = []struct {
- x, y, m string
- out string
- }{
- // y <= 0
- {"0", "0", "", "1"},
- {"1", "0", "", "1"},
- {"-10", "0", "", "1"},
- {"1234", "-1", "", "1"},
- {"1234", "-1", "0", "1"},
- {"17", "-100", "1234", "865"},
- {"2", "-100", "1234", ""},
- // m == 1
- {"0", "0", "1", "0"},
- {"1", "0", "1", "0"},
- {"-10", "0", "1", "0"},
- {"1234", "-1", "1", "0"},
- // misc
- {"5", "1", "3", "2"},
- {"5", "-7", "", "1"},
- {"-5", "-7", "", "1"},
- {"5", "0", "", "1"},
- {"-5", "0", "", "1"},
- {"5", "1", "", "5"},
- {"-5", "1", "", "-5"},
- {"-5", "1", "7", "2"},
- {"-2", "3", "2", "0"},
- {"5", "2", "", "25"},
- {"1", "65537", "2", "1"},
- {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
- {"0x8000000000000000", "2", "6719", "4944"},
- {"0x8000000000000000", "3", "6719", "5447"},
- {"0x8000000000000000", "1000", "6719", "1603"},
- {"0x8000000000000000", "1000000", "6719", "3199"},
- {"0x8000000000000000", "-1000000", "6719", "3663"}, // 3663 = ModInverse(3199, 6719) Issue #25865
- {"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
- {
- "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
- "298472983472983471903246121093472394872319615612417471234712061",
- "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
- "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
- },
- // test case for issue 8822
- {
- "11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
- "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
- "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
- "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
- },
- {
- "-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
- "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
- "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
- "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
- },
- // test cases for issue 13907
- {"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
- {"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
- {"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
- {"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
- {
- "2",
- "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
- "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", // odd
- "0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
- },
- {
- "2",
- "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
- "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", // even
- "0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
- },
- }
- func TestExp(t *testing.T) {
- for i, test := range expTests {
- x, ok1 := new(Int).SetString(test.x, 0)
- y, ok2 := new(Int).SetString(test.y, 0)
- var ok3, ok4 bool
- var out, m *Int
- if len(test.out) == 0 {
- out, ok3 = nil, true
- } else {
- out, ok3 = new(Int).SetString(test.out, 0)
- }
- if len(test.m) == 0 {
- m, ok4 = nil, true
- } else {
- m, ok4 = new(Int).SetString(test.m, 0)
- }
- if !ok1 || !ok2 || !ok3 || !ok4 {
- t.Errorf("#%d: error in input", i)
- continue
- }
- z1 := new(Int).Exp(x, y, m)
- if z1 != nil && !isNormalized(z1) {
- t.Errorf("#%d: %v is not normalized", i, *z1)
- }
- if !(z1 == nil && out == nil || z1.Cmp(out) == 0) {
- t.Errorf("#%d: got %x want %x", i, z1, out)
- }
- if m == nil {
- // The result should be the same as for m == 0;
- // specifically, there should be no div-zero panic.
- m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
- z2 := new(Int).Exp(x, y, m)
- if z2.Cmp(z1) != 0 {
- t.Errorf("#%d: got %x want %x", i, z2, z1)
- }
- }
- }
- }
- func BenchmarkExp(b *testing.B) {
- x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
- y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
- n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
- out := new(Int)
- for i := 0; i < b.N; i++ {
- out.Exp(x, y, n)
- }
- }
- func BenchmarkExp2(b *testing.B) {
- x, _ := new(Int).SetString("2", 0)
- y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
- n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
- out := new(Int)
- for i := 0; i < b.N; i++ {
- out.Exp(x, y, n)
- }
- }
- func checkGcd(aBytes, bBytes []byte) bool {
- x := new(Int)
- y := new(Int)
- a := new(Int).SetBytes(aBytes)
- b := new(Int).SetBytes(bBytes)
- d := new(Int).GCD(x, y, a, b)
- x.Mul(x, a)
- y.Mul(y, b)
- x.Add(x, y)
- return x.Cmp(d) == 0
- }
- // euclidExtGCD is a reference implementation of Euclid's
- // extended GCD algorithm for testing against optimized algorithms.
- // Requirements: a, b > 0
- func euclidExtGCD(a, b *Int) (g, x, y *Int) {
- A := new(Int).Set(a)
- B := new(Int).Set(b)
- // A = Ua*a + Va*b
- // B = Ub*a + Vb*b
- Ua := new(Int).SetInt64(1)
- Va := new(Int)
- Ub := new(Int)
- Vb := new(Int).SetInt64(1)
- q := new(Int)
- temp := new(Int)
- r := new(Int)
- for len(B.abs) > 0 {
- q, r = q.QuoRem(A, B, r)
- A, B, r = B, r, A
- // Ua, Ub = Ub, Ua-q*Ub
- temp.Set(Ub)
- Ub.Mul(Ub, q)
- Ub.Sub(Ua, Ub)
- Ua.Set(temp)
- // Va, Vb = Vb, Va-q*Vb
- temp.Set(Vb)
- Vb.Mul(Vb, q)
- Vb.Sub(Va, Vb)
- Va.Set(temp)
- }
- return A, Ua, Va
- }
- func checkLehmerGcd(aBytes, bBytes []byte) bool {
- a := new(Int).SetBytes(aBytes)
- b := new(Int).SetBytes(bBytes)
- if a.Sign() <= 0 || b.Sign() <= 0 {
- return true // can only test positive arguments
- }
- d := new(Int).lehmerGCD(nil, nil, a, b)
- d0, _, _ := euclidExtGCD(a, b)
- return d.Cmp(d0) == 0
- }
- func checkLehmerExtGcd(aBytes, bBytes []byte) bool {
- a := new(Int).SetBytes(aBytes)
- b := new(Int).SetBytes(bBytes)
- x := new(Int)
- y := new(Int)
- if a.Sign() <= 0 || b.Sign() <= 0 {
- return true // can only test positive arguments
- }
- d := new(Int).lehmerGCD(x, y, a, b)
- d0, x0, y0 := euclidExtGCD(a, b)
- return d.Cmp(d0) == 0 && x.Cmp(x0) == 0 && y.Cmp(y0) == 0
- }
- var gcdTests = []struct {
- d, x, y, a, b string
- }{
- // a <= 0 || b <= 0
- {"0", "0", "0", "0", "0"},
- {"7", "0", "1", "0", "7"},
- {"7", "0", "-1", "0", "-7"},
- {"11", "1", "0", "11", "0"},
- {"7", "-1", "-2", "-77", "35"},
- {"935", "-3", "8", "64515", "24310"},
- {"935", "-3", "-8", "64515", "-24310"},
- {"935", "3", "-8", "-64515", "-24310"},
- {"1", "-9", "47", "120", "23"},
- {"7", "1", "-2", "77", "35"},
- {"935", "-3", "8", "64515", "24310"},
- {"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
- {"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
- }
- func testGcd(t *testing.T, d, x, y, a, b *Int) {
- var X *Int
- if x != nil {
- X = new(Int)
- }
- var Y *Int
- if y != nil {
- Y = new(Int)
- }
- D := new(Int).GCD(X, Y, a, b)
- if D.Cmp(d) != 0 {
- t.Errorf("GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
- }
- if x != nil && X.Cmp(x) != 0 {
- t.Errorf("GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
- }
- if y != nil && Y.Cmp(y) != 0 {
- t.Errorf("GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
- }
- // check results in presence of aliasing (issue #11284)
- a2 := new(Int).Set(a)
- b2 := new(Int).Set(b)
- a2.GCD(X, Y, a2, b2) // result is same as 1st argument
- if a2.Cmp(d) != 0 {
- t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, a2, d)
- }
- if x != nil && X.Cmp(x) != 0 {
- t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
- }
- if y != nil && Y.Cmp(y) != 0 {
- t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
- }
- a2 = new(Int).Set(a)
- b2 = new(Int).Set(b)
- b2.GCD(X, Y, a2, b2) // result is same as 2nd argument
- if b2.Cmp(d) != 0 {
- t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, b2, d)
- }
- if x != nil && X.Cmp(x) != 0 {
- t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
- }
- if y != nil && Y.Cmp(y) != 0 {
- t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
- }
- a2 = new(Int).Set(a)
- b2 = new(Int).Set(b)
- D = new(Int).GCD(a2, b2, a2, b2) // x = a, y = b
- if D.Cmp(d) != 0 {
- t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
- }
- if x != nil && a2.Cmp(x) != 0 {
- t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, a2, x)
- }
- if y != nil && b2.Cmp(y) != 0 {
- t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, b2, y)
- }
- a2 = new(Int).Set(a)
- b2 = new(Int).Set(b)
- D = new(Int).GCD(b2, a2, a2, b2) // x = b, y = a
- if D.Cmp(d) != 0 {
- t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
- }
- if x != nil && b2.Cmp(x) != 0 {
- t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, b2, x)
- }
- if y != nil && a2.Cmp(y) != 0 {
- t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, a2, y)
- }
- }
- func TestGcd(t *testing.T) {
- for _, test := range gcdTests {
- d, _ := new(Int).SetString(test.d, 0)
- x, _ := new(Int).SetString(test.x, 0)
- y, _ := new(Int).SetString(test.y, 0)
- a, _ := new(Int).SetString(test.a, 0)
- b, _ := new(Int).SetString(test.b, 0)
- testGcd(t, d, nil, nil, a, b)
- testGcd(t, d, x, nil, a, b)
- testGcd(t, d, nil, y, a, b)
- testGcd(t, d, x, y, a, b)
- }
- if err := quick.Check(checkGcd, nil); err != nil {
- t.Error(err)
- }
- if err := quick.Check(checkLehmerGcd, nil); err != nil {
- t.Error(err)
- }
- if err := quick.Check(checkLehmerExtGcd, nil); err != nil {
- t.Error(err)
- }
- }
- type intShiftTest struct {
- in string
- shift uint
- out string
- }
- var rshTests = []intShiftTest{
- {"0", 0, "0"},
- {"-0", 0, "0"},
- {"0", 1, "0"},
- {"0", 2, "0"},
- {"1", 0, "1"},
- {"1", 1, "0"},
- {"1", 2, "0"},
- {"2", 0, "2"},
- {"2", 1, "1"},
- {"-1", 0, "-1"},
- {"-1", 1, "-1"},
- {"-1", 10, "-1"},
- {"-100", 2, "-25"},
- {"-100", 3, "-13"},
- {"-100", 100, "-1"},
- {"4294967296", 0, "4294967296"},
- {"4294967296", 1, "2147483648"},
- {"4294967296", 2, "1073741824"},
- {"18446744073709551616", 0, "18446744073709551616"},
- {"18446744073709551616", 1, "9223372036854775808"},
- {"18446744073709551616", 2, "4611686018427387904"},
- {"18446744073709551616", 64, "1"},
- {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
- {"340282366920938463463374607431768211456", 128, "1"},
- }
- func TestRsh(t *testing.T) {
- for i, test := range rshTests {
- in, _ := new(Int).SetString(test.in, 10)
- expected, _ := new(Int).SetString(test.out, 10)
- out := new(Int).Rsh(in, test.shift)
- if !isNormalized(out) {
- t.Errorf("#%d: %v is not normalized", i, *out)
- }
- if out.Cmp(expected) != 0 {
- t.Errorf("#%d: got %s want %s", i, out, expected)
- }
- }
- }
- func TestRshSelf(t *testing.T) {
- for i, test := range rshTests {
- z, _ := new(Int).SetString(test.in, 10)
- expected, _ := new(Int).SetString(test.out, 10)
- z.Rsh(z, test.shift)
- if !isNormalized(z) {
- t.Errorf("#%d: %v is not normalized", i, *z)
- }
- if z.Cmp(expected) != 0 {
- t.Errorf("#%d: got %s want %s", i, z, expected)
- }
- }
- }
- var lshTests = []intShiftTest{
- {"0", 0, "0"},
- {"0", 1, "0"},
- {"0", 2, "0"},
- {"1", 0, "1"},
- {"1", 1, "2"},
- {"1", 2, "4"},
- {"2", 0, "2"},
- {"2", 1, "4"},
- {"2", 2, "8"},
- {"-87", 1, "-174"},
- {"4294967296", 0, "4294967296"},
- {"4294967296", 1, "8589934592"},
- {"4294967296", 2, "17179869184"},
- {"18446744073709551616", 0, "18446744073709551616"},
- {"9223372036854775808", 1, "18446744073709551616"},
- {"4611686018427387904", 2, "18446744073709551616"},
- {"1", 64, "18446744073709551616"},
- {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
- {"1", 128, "340282366920938463463374607431768211456"},
- }
- func TestLsh(t *testing.T) {
- for i, test := range lshTests {
- in, _ := new(Int).SetString(test.in, 10)
- expected, _ := new(Int).SetString(test.out, 10)
- out := new(Int).Lsh(in, test.shift)
- if !isNormalized(out) {
- t.Errorf("#%d: %v is not normalized", i, *out)
- }
- if out.Cmp(expected) != 0 {
- t.Errorf("#%d: got %s want %s", i, out, expected)
- }
- }
- }
- func TestLshSelf(t *testing.T) {
- for i, test := range lshTests {
- z, _ := new(Int).SetString(test.in, 10)
- expected, _ := new(Int).SetString(test.out, 10)
- z.Lsh(z, test.shift)
- if !isNormalized(z) {
- t.Errorf("#%d: %v is not normalized", i, *z)
- }
- if z.Cmp(expected) != 0 {
- t.Errorf("#%d: got %s want %s", i, z, expected)
- }
- }
- }
- func TestLshRsh(t *testing.T) {
- for i, test := range rshTests {
- in, _ := new(Int).SetString(test.in, 10)
- out := new(Int).Lsh(in, test.shift)
- out = out.Rsh(out, test.shift)
- if !isNormalized(out) {
- t.Errorf("#%d: %v is not normalized", i, *out)
- }
- if in.Cmp(out) != 0 {
- t.Errorf("#%d: got %s want %s", i, out, in)
- }
- }
- for i, test := range lshTests {
- in, _ := new(Int).SetString(test.in, 10)
- out := new(Int).Lsh(in, test.shift)
- out.Rsh(out, test.shift)
- if !isNormalized(out) {
- t.Errorf("#%d: %v is not normalized", i, *out)
- }
- if in.Cmp(out) != 0 {
- t.Errorf("#%d: got %s want %s", i, out, in)
- }
- }
- }
- // Entries must be sorted by value in ascending order.
- var cmpAbsTests = []string{
- "0",
- "1",
- "2",
- "10",
- "10000000",
- "2783678367462374683678456387645876387564783686583485",
- "2783678367462374683678456387645876387564783686583486",
- "32957394867987420967976567076075976570670947609750670956097509670576075067076027578341538",
- }
- func TestCmpAbs(t *testing.T) {
- values := make([]*Int, len(cmpAbsTests))
- var prev *Int
- for i, s := range cmpAbsTests {
- x, ok := new(Int).SetString(s, 0)
- if !ok {
- t.Fatalf("SetString(%s, 0) failed", s)
- }
- if prev != nil && prev.Cmp(x) >= 0 {
- t.Fatal("cmpAbsTests entries not sorted in ascending order")
- }
- values[i] = x
- prev = x
- }
- for i, x := range values {
- for j, y := range values {
- // try all combinations of signs for x, y
- for k := 0; k < 4; k++ {
- var a, b Int
- a.Set(x)
- b.Set(y)
- if k&1 != 0 {
- a.Neg(&a)
- }
- if k&2 != 0 {
- b.Neg(&b)
- }
- got := a.CmpAbs(&b)
- want := 0
- switch {
- case i > j:
- want = 1
- case i < j:
- want = -1
- }
- if got != want {
- t.Errorf("absCmp |%s|, |%s|: got %d; want %d", &a, &b, got, want)
- }
- }
- }
- }
- }
- func TestIntCmpSelf(t *testing.T) {
- for _, s := range cmpAbsTests {
- x, ok := new(Int).SetString(s, 0)
- if !ok {
- t.Fatalf("SetString(%s, 0) failed", s)
- }
- got := x.Cmp(x)
- want := 0
- if got != want {
- t.Errorf("x = %s: x.Cmp(x): got %d; want %d", x, got, want)
- }
- }
- }
- var int64Tests = []string{
- // int64
- "0",
- "1",
- "-1",
- "4294967295",
- "-4294967295",
- "4294967296",
- "-4294967296",
- "9223372036854775807",
- "-9223372036854775807",
- "-9223372036854775808",
- // not int64
- "0x8000000000000000",
- "-0x8000000000000001",
- "38579843757496759476987459679745",
- "-38579843757496759476987459679745",
- }
- func TestInt64(t *testing.T) {
- for _, s := range int64Tests {
- var x Int
- _, ok := x.SetString(s, 0)
- if !ok {
- t.Errorf("SetString(%s, 0) failed", s)
- continue
- }
- want, err := strconv.ParseInt(s, 0, 64)
- if err != nil {
- if err.(*strconv.NumError).Err == strconv.ErrRange {
- if x.IsInt64() {
- t.Errorf("IsInt64(%s) succeeded unexpectedly", s)
- }
- } else {
- t.Errorf("ParseInt(%s) failed", s)
- }
- continue
- }
- if !x.IsInt64() {
- t.Errorf("IsInt64(%s) failed unexpectedly", s)
- }
- got := x.Int64()
- if got != want {
- t.Errorf("Int64(%s) = %d; want %d", s, got, want)
- }
- }
- }
- var uint64Tests = []string{
- // uint64
- "0",
- "1",
- "4294967295",
- "4294967296",
- "8589934591",
- "8589934592",
- "9223372036854775807",
- "9223372036854775808",
- "0x08000000000000000",
- // not uint64
- "0x10000000000000000",
- "-0x08000000000000000",
- "-1",
- }
- func TestUint64(t *testing.T) {
- for _, s := range uint64Tests {
- var x Int
- _, ok := x.SetString(s, 0)
- if !ok {
- t.Errorf("SetString(%s, 0) failed", s)
- continue
- }
- want, err := strconv.ParseUint(s, 0, 64)
- if err != nil {
- // check for sign explicitly (ErrRange doesn't cover signed input)
- if s[0] == '-' || err.(*strconv.NumError).Err == strconv.ErrRange {
- if x.IsUint64() {
- t.Errorf("IsUint64(%s) succeeded unexpectedly", s)
- }
- } else {
- t.Errorf("ParseUint(%s) failed", s)
- }
- continue
- }
- if !x.IsUint64() {
- t.Errorf("IsUint64(%s) failed unexpectedly", s)
- }
- got := x.Uint64()
- if got != want {
- t.Errorf("Uint64(%s) = %d; want %d", s, got, want)
- }
- }
- }
- var bitwiseTests = []struct {
- x, y string
- and, or, xor, andNot string
- }{
- {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
- {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
- {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
- {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
- {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
- {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
- {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
- {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
- {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
- {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
- {"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
- {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
- {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
- {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
- {
- "0x1000009dc6e3d9822cba04129bcbe3401",
- "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
- "0x1000001186210100001000009048c2001",
- "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
- "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
- "0x8c40c2d8822caa04120b8321400",
- },
- {
- "0x1000009dc6e3d9822cba04129bcbe3401",
- "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
- "0x8c40c2d8822caa04120b8321401",
- "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
- "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
- "0x1000001186210100001000009048c2000",
- },
- {
- "-0x1000009dc6e3d9822cba04129bcbe3401",
- "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
- "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
- "-0x1000001186210100001000009048c2001",
- "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
- "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
- },
- }
- type bitFun func(z, x, y *Int) *Int
- func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
- expected := new(Int)
- expected.SetString(exp, 0)
- out := f(new(Int), x, y)
- if out.Cmp(expected) != 0 {
- t.Errorf("%s: got %s want %s", msg, out, expected)
- }
- }
- func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
- self := new(Int)
- self.Set(x)
- expected := new(Int)
- expected.SetString(exp, 0)
- self = f(self, self, y)
- if self.Cmp(expected) != 0 {
- t.Errorf("%s: got %s want %s", msg, self, expected)
- }
- }
- func altBit(x *Int, i int) uint {
- z := new(Int).Rsh(x, uint(i))
- z = z.And(z, NewInt(1))
- if z.Cmp(new(Int)) != 0 {
- return 1
- }
- return 0
- }
- func altSetBit(z *Int, x *Int, i int, b uint) *Int {
- one := NewInt(1)
- m := one.Lsh(one, uint(i))
- switch b {
- case 1:
- return z.Or(x, m)
- case 0:
- return z.AndNot(x, m)
- }
- panic("set bit is not 0 or 1")
- }
- func testBitset(t *testing.T, x *Int) {
- n := x.BitLen()
- z := new(Int).Set(x)
- z1 := new(Int).Set(x)
- for i := 0; i < n+10; i++ {
- old := z.Bit(i)
- old1 := altBit(z1, i)
- if old != old1 {
- t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
- }
- z := new(Int).SetBit(z, i, 1)
- z1 := altSetBit(new(Int), z1, i, 1)
- if z.Bit(i) == 0 {
- t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
- }
- if z.Cmp(z1) != 0 {
- t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
- }
- z.SetBit(z, i, 0)
- altSetBit(z1, z1, i, 0)
- if z.Bit(i) != 0 {
- t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
- }
- if z.Cmp(z1) != 0 {
- t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
- }
- altSetBit(z1, z1, i, old)
- z.SetBit(z, i, old)
- if z.Cmp(z1) != 0 {
- t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
- }
- }
- if z.Cmp(x) != 0 {
- t.Errorf("bitset: got %s want %s", z, x)
- }
- }
- var bitsetTests = []struct {
- x string
- i int
- b uint
- }{
- {"0", 0, 0},
- {"0", 200, 0},
- {"1", 0, 1},
- {"1", 1, 0},
- {"-1", 0, 1},
- {"-1", 200, 1},
- {"0x2000000000000000000000000000", 108, 0},
- {"0x2000000000000000000000000000", 109, 1},
- {"0x2000000000000000000000000000", 110, 0},
- {"-0x2000000000000000000000000001", 108, 1},
- {"-0x2000000000000000000000000001", 109, 0},
- {"-0x2000000000000000000000000001", 110, 1},
- }
- func TestBitSet(t *testing.T) {
- for _, test := range bitwiseTests {
- x := new(Int)
- x.SetString(test.x, 0)
- testBitset(t, x)
- x = new(Int)
- x.SetString(test.y, 0)
- testBitset(t, x)
- }
- for i, test := range bitsetTests {
- x := new(Int)
- x.SetString(test.x, 0)
- b := x.Bit(test.i)
- if b != test.b {
- t.Errorf("#%d got %v want %v", i, b, test.b)
- }
- }
- z := NewInt(1)
- z.SetBit(NewInt(0), 2, 1)
- if z.Cmp(NewInt(4)) != 0 {
- t.Errorf("destination leaked into result; got %s want 4", z)
- }
- }
- var tzbTests = []struct {
- in string
- out uint
- }{
- {"0", 0},
- {"1", 0},
- {"-1", 0},
- {"4", 2},
- {"-8", 3},
- {"0x4000000000000000000", 74},
- {"-0x8000000000000000000", 75},
- }
- func TestTrailingZeroBits(t *testing.T) {
- for i, test := range tzbTests {
- in, _ := new(Int).SetString(test.in, 0)
- want := test.out
- got := in.TrailingZeroBits()
- if got != want {
- t.Errorf("#%d: got %v want %v", i, got, want)
- }
- }
- }
- func BenchmarkBitset(b *testing.B) {
- z := new(Int)
- z.SetBit(z, 512, 1)
- b.ResetTimer()
- b.StartTimer()
- for i := b.N - 1; i >= 0; i-- {
- z.SetBit(z, i&512, 1)
- }
- }
- func BenchmarkBitsetNeg(b *testing.B) {
- z := NewInt(-1)
- z.SetBit(z, 512, 0)
- b.ResetTimer()
- b.StartTimer()
- for i := b.N - 1; i >= 0; i-- {
- z.SetBit(z, i&512, 0)
- }
- }
- func BenchmarkBitsetOrig(b *testing.B) {
- z := new(Int)
- altSetBit(z, z, 512, 1)
- b.ResetTimer()
- b.StartTimer()
- for i := b.N - 1; i >= 0; i-- {
- altSetBit(z, z, i&512, 1)
- }
- }
- func BenchmarkBitsetNegOrig(b *testing.B) {
- z := NewInt(-1)
- altSetBit(z, z, 512, 0)
- b.ResetTimer()
- b.StartTimer()
- for i := b.N - 1; i >= 0; i-- {
- altSetBit(z, z, i&512, 0)
- }
- }
- // tri generates the trinomial 2**(n*2) - 2**n - 1, which is always 3 mod 4 and
- // 7 mod 8, so that 2 is always a quadratic residue.
- func tri(n uint) *Int {
- x := NewInt(1)
- x.Lsh(x, n)
- x2 := new(Int).Lsh(x, n)
- x2.Sub(x2, x)
- x2.Sub(x2, intOne)
- return x2
- }
- func BenchmarkModSqrt225_Tonelli(b *testing.B) {
- p := tri(225)
- x := NewInt(2)
- for i := 0; i < b.N; i++ {
- x.SetUint64(2)
- x.modSqrtTonelliShanks(x, p)
- }
- }
- func BenchmarkModSqrt225_3Mod4(b *testing.B) {
- p := tri(225)
- x := new(Int).SetUint64(2)
- for i := 0; i < b.N; i++ {
- x.SetUint64(2)
- x.modSqrt3Mod4Prime(x, p)
- }
- }
- func BenchmarkModSqrt231_Tonelli(b *testing.B) {
- p := tri(231)
- p.Sub(p, intOne)
- p.Sub(p, intOne) // tri(231) - 2 is a prime == 5 mod 8
- x := new(Int).SetUint64(7)
- for i := 0; i < b.N; i++ {
- x.SetUint64(7)
- x.modSqrtTonelliShanks(x, p)
- }
- }
- func BenchmarkModSqrt231_5Mod8(b *testing.B) {
- p := tri(231)
- p.Sub(p, intOne)
- p.Sub(p, intOne) // tri(231) - 2 is a prime == 5 mod 8
- x := new(Int).SetUint64(7)
- for i := 0; i < b.N; i++ {
- x.SetUint64(7)
- x.modSqrt5Mod8Prime(x, p)
- }
- }
- func TestBitwise(t *testing.T) {
- x := new(Int)
- y := new(Int)
- for _, test := range bitwiseTests {
- x.SetString(test.x, 0)
- y.SetString(test.y, 0)
- testBitFun(t, "and", (*Int).And, x, y, test.and)
- testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
- testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
- testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
- testBitFun(t, "or", (*Int).Or, x, y, test.or)
- testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
- testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
- testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
- }
- }
- var notTests = []struct {
- in string
- out string
- }{
- {"0", "-1"},
- {"1", "-2"},
- {"7", "-8"},
- {"0", "-1"},
- {"-81910", "81909"},
- {
- "298472983472983471903246121093472394872319615612417471234712061",
- "-298472983472983471903246121093472394872319615612417471234712062",
- },
- }
- func TestNot(t *testing.T) {
- in := new(Int)
- out := new(Int)
- expected := new(Int)
- for i, test := range notTests {
- in.SetString(test.in, 10)
- expected.SetString(test.out, 10)
- out = out.Not(in)
- if out.Cmp(expected) != 0 {
- t.Errorf("#%d: got %s want %s", i, out, expected)
- }
- out = out.Not(out)
- if out.Cmp(in) != 0 {
- t.Errorf("#%d: got %s want %s", i, out, in)
- }
- }
- }
- var modInverseTests = []struct {
- element string
- modulus string
- }{
- {"1234567", "458948883992"},
- {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
- {"-10", "13"}, // issue #16984
- {"10", "-13"},
- {"-17", "-13"},
- }
- func TestModInverse(t *testing.T) {
- var element, modulus, gcd, inverse Int
- one := NewInt(1)
- for _, test := range modInverseTests {
- (&element).SetString(test.element, 10)
- (&modulus).SetString(test.modulus, 10)
- (&inverse).ModInverse(&element, &modulus)
- (&inverse).Mul(&inverse, &element)
- (&inverse).Mod(&inverse, &modulus)
- if (&inverse).Cmp(one) != 0 {
- t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
- }
- }
- // exhaustive test for small values
- for n := 2; n < 100; n++ {
- (&modulus).SetInt64(int64(n))
- for x := 1; x < n; x++ {
- (&element).SetInt64(int64(x))
- (&gcd).GCD(nil, nil, &element, &modulus)
- if (&gcd).Cmp(one) != 0 {
- continue
- }
- (&inverse).ModInverse(&element, &modulus)
- (&inverse).Mul(&inverse, &element)
- (&inverse).Mod(&inverse, &modulus)
- if (&inverse).Cmp(one) != 0 {
- t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
- }
- }
- }
- }
- func BenchmarkModInverse(b *testing.B) {
- p := new(Int).SetInt64(1) // Mersenne prime 2**1279 -1
- p.abs = p.abs.shl(p.abs, 1279)
- p.Sub(p, intOne)
- x := new(Int).Sub(p, intOne)
- z := new(Int)
- for i := 0; i < b.N; i++ {
- z.ModInverse(x, p)
- }
- }
- // testModSqrt is a helper for TestModSqrt,
- // which checks that ModSqrt can compute a square-root of elt^2.
- func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
- var sqChk, sqrtChk, sqrtsq Int
- sq.Mul(elt, elt)
- sq.Mod(sq, mod)
- z := sqrt.ModSqrt(sq, mod)
- if z != sqrt {
- t.Errorf("ModSqrt returned wrong value %s", z)
- }
- // test ModSqrt arguments outside the range [0,mod)
- sqChk.Add(sq, mod)
- z = sqrtChk.ModSqrt(&sqChk, mod)
- if z != &sqrtChk || z.Cmp(sqrt) != 0 {
- t.Errorf("ModSqrt returned inconsistent value %s", z)
- }
- sqChk.Sub(sq, mod)
- z = sqrtChk.ModSqrt(&sqChk, mod)
- if z != &sqrtChk || z.Cmp(sqrt) != 0 {
- t.Errorf("ModSqrt returned inconsistent value %s", z)
- }
- // test x aliasing z
- z = sqrtChk.ModSqrt(sqrtChk.Set(sq), mod)
- if z != &sqrtChk || z.Cmp(sqrt) != 0 {
- t.Errorf("ModSqrt returned inconsistent value %s", z)
- }
- // make sure we actually got a square root
- if sqrt.Cmp(elt) == 0 {
- return true // we found the "desired" square root
- }
- sqrtsq.Mul(sqrt, sqrt) // make sure we found the "other" one
- sqrtsq.Mod(&sqrtsq, mod)
- return sq.Cmp(&sqrtsq) == 0
- }
- func TestModSqrt(t *testing.T) {
- var elt, mod, modx4, sq, sqrt Int
- r := rand.New(rand.NewSource(9))
- for i, s := range primes[1:] { // skip 2, use only odd primes
- mod.SetString(s, 10)
- modx4.Lsh(&mod, 2)
- // test a few random elements per prime
- for x := 1; x < 5; x++ {
- elt.Rand(r, &modx4)
- elt.Sub(&elt, &mod) // test range [-mod, 3*mod)
- if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
- t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
- }
- }
- if testing.Short() && i > 2 {
- break
- }
- }
- if testing.Short() {
- return
- }
- // exhaustive test for small values
- for n := 3; n < 100; n++ {
- mod.SetInt64(int64(n))
- if !mod.ProbablyPrime(10) {
- continue
- }
- isSquare := make([]bool, n)
- // test all the squares
- for x := 1; x < n; x++ {
- elt.SetInt64(int64(x))
- if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
- t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
- }
- isSquare[sq.Uint64()] = true
- }
- // test all non-squares
- for x := 1; x < n; x++ {
- sq.SetInt64(int64(x))
- z := sqrt.ModSqrt(&sq, &mod)
- if !isSquare[x] && z != nil {
- t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
- }
- }
- }
- }
- func TestJacobi(t *testing.T) {
- testCases := []struct {
- x, y int64
- result int
- }{
- {0, 1, 1},
- {0, -1, 1},
- {1, 1, 1},
- {1, -1, 1},
- {0, 5, 0},
- {1, 5, 1},
- {2, 5, -1},
- {-2, 5, -1},
- {2, -5, -1},
- {-2, -5, 1},
- {3, 5, -1},
- {5, 5, 0},
- {-5, 5, 0},
- {6, 5, 1},
- {6, -5, 1},
- {-6, 5, 1},
- {-6, -5, -1},
- }
- var x, y Int
- for i, test := range testCases {
- x.SetInt64(test.x)
- y.SetInt64(test.y)
- expected := test.result
- actual := Jacobi(&x, &y)
- if actual != expected {
- t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
- }
- }
- }
- func TestJacobiPanic(t *testing.T) {
- const failureMsg = "test failure"
- defer func() {
- msg := recover()
- if msg == nil || msg == failureMsg {
- panic(msg)
- }
- t.Log(msg)
- }()
- x := NewInt(1)
- y := NewInt(2)
- // Jacobi should panic when the second argument is even.
- Jacobi(x, y)
- panic(failureMsg)
- }
- func TestIssue2607(t *testing.T) {
- // This code sequence used to hang.
- n := NewInt(10)
- n.Rand(rand.New(rand.NewSource(9)), n)
- }
- func TestSqrt(t *testing.T) {
- root := 0
- r := new(Int)
- for i := 0; i < 10000; i++ {
- if (root+1)*(root+1) <= i {
- root++
- }
- n := NewInt(int64(i))
- r.SetInt64(-2)
- r.Sqrt(n)
- if r.Cmp(NewInt(int64(root))) != 0 {
- t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
- }
- }
- for i := 0; i < 1000; i += 10 {
- n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10)
- r := new(Int).Sqrt(n)
- root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10)
- if r.Cmp(root) != 0 {
- t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
- }
- }
- // Test aliasing.
- r.SetInt64(100)
- r.Sqrt(r)
- if r.Int64() != 10 {
- t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
- }
- }
- // We can't test this together with the other Exp tests above because
- // it requires a different receiver setup.
- func TestIssue22830(t *testing.T) {
- one := new(Int).SetInt64(1)
- base, _ := new(Int).SetString("84555555300000000000", 10)
- mod, _ := new(Int).SetString("66666670001111111111", 10)
- want, _ := new(Int).SetString("17888885298888888889", 10)
- var tests = []int64{
- 0, 1, -1,
- }
- for _, n := range tests {
- m := NewInt(n)
- if got := m.Exp(base, one, mod); got.Cmp(want) != 0 {
- t.Errorf("(%v).Exp(%s, 1, %s) = %s, want %s", n, base, mod, got, want)
- }
- }
- }
- func BenchmarkSqrt(b *testing.B) {
- n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10)
- b.ResetTimer()
- t := new(Int)
- for i := 0; i < b.N; i++ {
- t.Sqrt(n)
- }
- }
- func benchmarkIntSqr(b *testing.B, nwords int) {
- x := new(Int)
- x.abs = rndNat(nwords)
- t := new(Int)
- b.ResetTimer()
- for i := 0; i < b.N; i++ {
- t.Mul(x, x)
- }
- }
- func BenchmarkIntSqr(b *testing.B) {
- for _, n := range sqrBenchSizes {
- if isRaceBuilder && n > 1e3 {
- continue
- }
- b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
- benchmarkIntSqr(b, n)
- })
- }
- }
- func benchmarkDiv(b *testing.B, aSize, bSize int) {
- var r = rand.New(rand.NewSource(1234))
- aa := randInt(r, uint(aSize))
- bb := randInt(r, uint(bSize))
- if aa.Cmp(bb) < 0 {
- aa, bb = bb, aa
- }
- x := new(Int)
- y := new(Int)
- b.ResetTimer()
- for i := 0; i < b.N; i++ {
- x.DivMod(aa, bb, y)
- }
- }
- func BenchmarkDiv(b *testing.B) {
- sizes := []int{
- 10, 20, 50, 100, 200, 500, 1000,
- 1e4, 1e5, 1e6, 1e7,
- }
- for _, i := range sizes {
- j := 2 * i
- b.Run(fmt.Sprintf("%d/%d", j, i), func(b *testing.B) {
- benchmarkDiv(b, j, i)
- })
- }
- }
- func TestFillBytes(t *testing.T) {
- checkResult := func(t *testing.T, buf []byte, want *Int) {
- t.Helper()
- got := new(Int).SetBytes(buf)
- if got.CmpAbs(want) != 0 {
- t.Errorf("got 0x%x, want 0x%x: %x", got, want, buf)
- }
- }
- panics := func(f func()) (panic bool) {
- defer func() { panic = recover() != nil }()
- f()
- return
- }
- for _, n := range []string{
- "0",
- "1000",
- "0xffffffff",
- "-0xffffffff",
- "0xffffffffffffffff",
- "0x10000000000000000",
- "0xabababababababababababababababababababababababababa",
- "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
- } {
- t.Run(n, func(t *testing.T) {
- t.Logf(n)
- x, ok := new(Int).SetString(n, 0)
- if !ok {
- panic("invalid test entry")
- }
- // Perfectly sized buffer.
- byteLen := (x.BitLen() + 7) / 8
- buf := make([]byte, byteLen)
- checkResult(t, x.FillBytes(buf), x)
- // Way larger, checking all bytes get zeroed.
- buf = make([]byte, 100)
- for i := range buf {
- buf[i] = 0xff
- }
- checkResult(t, x.FillBytes(buf), x)
- // Too small.
- if byteLen > 0 {
- buf = make([]byte, byteLen-1)
- if !panics(func() { x.FillBytes(buf) }) {
- t.Errorf("expected panic for small buffer and value %x", x)
- }
- }
- })
- }
- }
|