v / vlib / math / big / big_test.v
1004 lines · 903 sloc · 65.49 KB · 51630f179562687f27d1e5eb9f3c370de4f01622
Raw 


1import math.big


2


3struct IntegerRadix {


4    digit_string string


5    radix        u32


6}


7


8type TestInteger = IntegerRadix | []u8 | big.Integer | i64 | int | string | u32 | u64


9


10fn (a TestInteger) parse() big.Integer {


11    return match a {


12        big.Integer {


13            a


14        }


15        string {


16            big.integer_from_string(a) or { panic('Cannot read decimal') }


17        }


18        int {


19            big.integer_from_int(a)


20        }


21        u32 {


22            big.integer_from_u32(a)


23        }


24        u64 {


25            big.integer_from_u64(a)


26        }


27        i64 {


28            big.integer_from_i64(a)


29        }


30        []u8 {


31            big.integer_from_bytes(a)


32        }


33        IntegerRadix {


34            big.integer_from_radix(a.digit_string, a.radix) or {


35                panic('Cannot read decimal base ${a.radix}')


36            }


37        }


38    }


39}


40


41struct IntegerFromTest {


42    value    TestInteger


43    expected string // prefix with 0x for hex


44}


45


46// vfmt off


47const integer_from_int_test_data = [


48    // use int


49    IntegerFromTest{ 0, '0' },


50    IntegerFromTest{ 1, '1' },


51    IntegerFromTest{ 255, '255' },


52    IntegerFromTest{ 127, '127' },


53    IntegerFromTest{ 1024, '1024' },


54    IntegerFromTest{ 2147483647, '0x7fffffff' },


55    IntegerFromTest{ -2147483647, '-2147483647' },


56    IntegerFromTest{ -2147483648, '-2147483648' },


57]


58


59const integer_from_u64_test_data = [


60    // use u64


61    IntegerFromTest{ u64(0), '0' },


62    IntegerFromTest{ u64(1), '1' },


63    IntegerFromTest{ u64(255), '255' },


64    IntegerFromTest{ u64(127), '127' },


65    IntegerFromTest{ u64(1024), '1024' },


66    IntegerFromTest{ u64(4294967295), '0xffffffff' },


67    IntegerFromTest{ u64(4398046511104), '0x40000000000' },


68    IntegerFromTest{ u64(-1), '0xffffffffffffffff' },


69]


70


71const integer_from_bytes_test_data = [


72    // use []u8


73    IntegerFromTest{ []u8{}, '0' },


74    IntegerFromTest{ [u8(0)], '0' },


75    IntegerFromTest{ [u8(0x13), 0x37], '0x1337' },


76    IntegerFromTest{ [u8(0x13), 0x37, 0xca], '0x1337ca' },


77    IntegerFromTest{ [u8(0x13), 0x37, 0xca, 0xfe], '0x1337cafe' },


78    IntegerFromTest{ [u8(0x13), 0x37, 0xca, 0xfe, 0xba], '0x1337cafeba' },


79    IntegerFromTest{ [u8(0x13), 0x37, 0xca, 0xfe, 0xba, 0xbe], '0x1337cafebabe' },


80]


81


82const integer_from_string_test_data = [


83    // use string


84    IntegerFromTest{ '00000000', '0' },


85    IntegerFromTest{ '00', '0' },


86    IntegerFromTest{ '0', '0' },


87    IntegerFromTest{ '1', '1' },


88    IntegerFromTest{ '0012', '12' },


89    IntegerFromTest{ '1349173614', '1349173614' },


90    IntegerFromTest{ '+24', '24' },


91    IntegerFromTest{ '-325', '-325' },


92    IntegerFromTest{ '-2147483648', '-2147483648' },


93    IntegerFromTest{ '2147483647', '2147483647' },


94]


95


96const integer_from_radix_test_data = [


97    // use IntegerRadix


98    IntegerFromTest{ IntegerRadix{ '101010', 2 }, '42' },


99    IntegerFromTest{ IntegerRadix{ '1010', 2 }, '10' },


100    IntegerFromTest{ IntegerRadix{ '-0000101', 2 }, '-5' },


101    IntegerFromTest{ IntegerRadix{ 'CAFE', 16 }, '0xcafe' },


102    IntegerFromTest{ IntegerRadix{ 'DED', 16 }, '0xded' },


103    IntegerFromTest{ IntegerRadix{ '-abcd', 16 }, '-43981' },


104]


105// vfmt on


106


107// is_*


108struct IsXTest {


109    value    TestInteger


110    expected bool


111}


112


113// vfmt off


114const is_power_of_2_test_data = [


115    IsXTest{ "-4", false },


116    IsXTest{ u32(0b110000000000), false },


117    IsXTest{ "537502395172353242345", false },


118    IsXTest{ "590295810358705700000", false },


119    IsXTest{ "1125899906842624", true },


120    IsXTest{ "590295810358705651712", true },


121    IsXTest{ "4611686018427388002", false },


122    IsXTest{ "31195165372897259196222538898096203590151924108450147950531565441852619837316692843188389598728651769482088968838700984268947453885587967878549286444999755742573423371025356539077075265986419171772426279084559025861175301940492273427120221755816136975739916983004778387946699939545354293487098252428954036286183995782377175227121587657233553706589448547148066273280603243167958729707736664649187444136702017299877489729451997277875868782399735511520086969969766278182145454186690598629675562422923132555707758646587702550600894625696538109646366308973392363200122154242784576162149305816215109893613161331026672647000825615987247035266514313689413563779184515427920269935280569035788081552413007563772309295149800172031645681720569680154349893907395864528243629654386620034655445226295834594630792819545156798270599481573436039129275439653984521135652249263653985326577886990615665734998585216581730937090703518997669223802429711292740491797911117308280939507973715877108492303860661291987529284719391551256912380499409630332506454532263266457209921483705507359152839264852808182519011100934922492651373859423833024010283468753147686188675294998119637462200763443029190704825719342806119404339670408160210011918981038977425180213726646978883378058838510330816291941879581568740273684084511318422175006728346276489384220596694727036836687670632486602655240593463885077059375085482211864761344849868123074687509143827139683659102930877963676911995751113159944160296419825178911962487549670296207457410515598040046860567719116506974858703739531721991704589155513182996455827177472", true },


123]


124


125const is_odd_test_data = [


126    IsXTest{ u32(0), false },


127    IsXTest{ u32(1), true },


128    IsXTest{ u32(1805), true },


129    IsXTest{ "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111", true },


130    IsXTest{ "57495732561923751347562394571325712358054", false },


131]


132// vfmt on


133


134struct AddTest {


135    augend TestInteger


136    addend TestInteger


137    sum    TestInteger


138}


139


140// vfmt off


141const add_test_data = [


142    AddTest{ 0,  0, 0},


143    AddTest{ 1, -1, 0 },


144    AddTest{ -1, 1, 0 },


145    AddTest{ 0,  2, 2},


146    AddTest{ 2, 0, 2 },


147    AddTest{ 0, -2, -2},


148    AddTest{ -2, 0, -2 },


149    AddTest{ 2, -2, 0 },


150    AddTest{ -2, 2, 0 },


151    AddTest{ -1, 200, 199},


152    AddTest{ 200, -1, 199},


153    AddTest{ -2, 100, 98},


154    AddTest{ 100, -2, 98},


155    AddTest{ -100, -2, -102},


156    AddTest{ -2, -100, -102},


157    //


158    AddTest{ 1, 200, 201},


159    AddTest{ -200, -1, -201},


160    AddTest{ 2, 100, 102},


161    AddTest{ -100, -2, -102},


162    AddTest{ 100, -2, 98},


163    AddTest{ 2, -100, -98},


164    //


165    AddTest{ 2, 3, 5 },


166    AddTest{ 1024, 1024, 2048 },


167    AddTest{ 1024, 1024, 2048 },


168    AddTest{


169        '84885164052257330097714121751630835360966663883732297726369399',


170        '137347080577163115432025771710279131845700275212767467264610201',


171        '222232244629420445529739893461909967206666939096499764990979600'


172    },


173]


174// vfmt on


175


176struct SubTest {


177    minuend    TestInteger


178    subtrahend TestInteger


179    difference TestInteger


180}


181


182// vfmt off


183const sub_test_data = [


184    SubTest{ 0, 0, 0 },


185    SubTest{ 0, -1, 1 },


186    SubTest{ -1, 0, -1 },


187    SubTest{ 1, 1, 0},


188    SubTest{ 1, -1, 2},


189    SubTest{ 2, -1, 3},


190    SubTest{ -1, 2, -3},


191    SubTest{ -100, 100, -200},


192    SubTest{ 100, -100, 200},


193    SubTest{ -100, -100, 0},


194    //


195    SubTest{ 1, 200, -199},


196    SubTest{ -200, -1, -199},


197    SubTest{ 2, 100, -98},


198    SubTest{ -100, -2, -98},


199    SubTest{ 100, -2, 102},


200    SubTest{ 2, -100, 102},


201    //


202    SubTest{ 2, 3, -1 },


203    SubTest{ 3, 2, 1 },


204    SubTest{ 1024, 1024, 0 },


205    SubTest{ 1025, 1023, 2 },


206    SubTest{ -37, -54, 17 },


207    SubTest{


208        '606649970971701574041811686113740270202550876483709086148210605390116266828180223053050209778348894403980564356645388786075884763988241017548715303094260467104311496756419021350006724017740287475611178032365989622403609173077177580917766063674998982266831659846883191228163839505500376638406380518500245205640396836251745520989267049355350124770273420388742964392659042390255365913227741421167939209094197448839427828553490702868654886044542868294392357965495270538217024561541188096726845410444367476070654975991208949317364651403789852688275944360458918380026777837704864009506175958100724200063354587117724445105352507371251655385818390017704579668464509118556289300149193216670709993199698192433115976551775179800369638443387559604023762303996929773104264181192752852969235821274398832731350067075624797873057893457025900696931888413170836093304160937994690818677414459443711940357617086640671088053946435282979649549418554954712352988774810660384276492179755146895039071579530616412414312102806763864081256558973934032350169887606110957605908487251732839382994454544873238510239304731396067785963044777530602823206256913249732064244398147271369308044244332002083201889676311272588373015273349596481282728910186314212094495644361558295140446865360550851657930415001417226985487444959716363633445225371706716914389021896551395496211883459788574558837045534063579702308219870597512062392856506558380417078205327200246935706335015817156527870338168318120000713685289299174193726065869808768486103389894925715767295',


209        '7216848130098425850',


210        '606649970971701574041811686113740270202550876483709086148210605390116266828180223053050209778348894403980564356645388786075884763988241017548715303094260467104311496756419021350006724017740287475611178032365989622403609173077177580917766063674998982266831659846883191228163839505500376638406380518500245205640396836251745520989267049355350124770273420388742964392659042390255365913227741421167939209094197448839427828553490702868654886044542868294392357965495270538217024561541188096726845410444367476070654975991208949317364651403789852688275944360458918380026777837704864009506175958100724200063354587117724445105352507371251655385818390017704579668464509118556289300149193216670709993199698192433115976551775179800369638443387559604023762303996929773104264181192752852969235821274398832731350067075624797873057893457025900696931888413170836093304160937994690818677414459443711940357617086640671088053946435282979649549418554954712352988774810660384276492179755146895039071579530616412414312102806763864081256558973934032350169887606110957605908487251732839382994454544873238510239304731396067785963044777530602823206256913249732064244398147271369308044244332002083201889676311272588373015273349596481282728910186314212094495644361558295140446865360550851657930415001417226985487444959716363633445225371706716914389021896551395496211883459788574558837045534063579702308219870597512062392856506558380417078205327200246935706335015817156527870338168318120000713685289299174193726065869808768486096173046795617341445',


211    },


212]


213// vfmt on


214


215struct MulTest {


216    multiplicand TestInteger


217    multiplier   TestInteger


218    product      TestInteger


219}


220


221// vfmt off


222const mul_test_data = [


223    MulTest{ 2, 3, 6 },


224    MulTest{ -2, 0, 0},


225    MulTest{  2, 0, 0},


226    MulTest{ 0, -2, 0},


227    MulTest{ 0, -2, 0},


228    MulTest{ -869, 789, -685641 },


229    MulTest{ 869, -789, -685641 },


230    MulTest{ -869, -789, 685641 },


231    MulTest{


232        '58347508324752098346789015701837509173586123875823769823749056132786590812379812508163208610983759827349812730',


233        '14213098571932561236783245987342583245873465877179284713298718093758173895718957198751983759745983467856287759872365123980571298307512352359812753907',


234        '829298887246357277468549979504958437413899799327432161171392486113084301523868147373815625368847440980180012682723545766706164916763514684200098693771786210459637448034580321756504306033681868059717237409850393775584813902875585559881251293651935822025836110',


235    },


236    MulTest{


237        '157894047392519583862123936251422583282863434486161035821830453040785097509971311098714713467802515421581208662454854025309513312726555776113715381698473216141765400957534609297819356059233676661532235280302251223761244857785344705006637894902125836430726519102261679054112732204572631900384085596495981525783',


238        '172750769107109861232750661741561572021207635860888814481781323903637921618217893620438648685692072759912890797284948206448457977080536627892119852493829355756035584640064060706092098984542716937323104336194056741403356304500304286336281585594296381344018535478383343176463402322692068381151973870461499748949',


239        '27276318124492212465432029043652584179286098914879267159076000142724287743892530142734241126306064189405321580796475224876708675570413592358715948396724932685085972846389975012793388131866028332508690735727488135870026351955805826642739703000986587467280495743559787380135296551334471419857554510187338555406214731430906002559624746468831645485763335047438526317636794466414295301915951975626967409997005043887959717124157434636781107429998249363525957258509402650503217872035874896065023377356660153975719637017472701236397203173555796145677008784279961849944450443054513670798899182054747598702569678446196470652067',


240    },


241    MulTest{


242        '164171010688258216356020741663906501410127235530735881272116103087925094171390144280159034536439457734870419127140401667195510331085657185332721089236401193044493457116299768844344303479235489462436380672117015123283299131391904179287678259173308536738761981139958654880852234908448338817289014166774169869251339379828599748492918775437864739032217778051333882990074116246281269364933724892342134504702491040016637557429810893780765197418589477584716543480995722533317862352141459217781316266211186486157019262080414077670264642736018426998113523445732680856144329876972273300703392584997729207197971083945700345494092400147186997307012069454068489589035676979448169848060836924945824197706493306108258511936030341393221586423523264452449403781993352421885094664052270795527632721896121424813173522474674395886155092203404036730748474781710715745446135468098139831824083259647919175273503681561172684624283384438504776503000432241604550454374116320822227191911322123484085063926350606342197146407841178028071147192533942517270553513988142925976090769695456221159699052583533011331652079347093098173086975483539274464023357456484465482927479569437320368592222760278170306076733438801098370797675711274671054970711442158930561684343135774118741612806419906031631601266266528538520924083161856865743302334249701407315310271018388258886432135273827859691733059369978643041918967442197313534697497404277350224866705804878433671262763482023400349043259178916572687989162930903779045078287573241909420120175442471703679516781197223112216572138640838928909745860699538278329256643602865002960800914563144124971099443335826150972157276451120655954671045954561868041854882824297821929166520068974703653272620867577906523992874996338253216963333346753434848676176334066388995978444434383568257588867823277644840815468397633199054967729800149549182806977698239412258835996851311070873503482289001486370524332318228425883088614099902710492272286924686293234474771490822760225994669314033129796588388559938376504519357876526207739824571643922272657401623465041482584188509253569882124046470363144411921518246416624724749905231440644997507666770400152259424985923818812142693481946120458476848688265618957991911827715393356088636270325443851034622105141544646198235918882925122792559855912557079094394123423520644892444598598382078381161104113085486556201098925110067360753401358261464776577606903832478339589245804354508579087454162252694910844773344482611021149046116480354455617601305942523594483024855696034938579749778676423303176347347340888151177304988777650344799235158668778873655761927959467569060076066072141671787427033055911592569177110108260910246683849221598266832809998266670667496151841679241795933186305511292585313329789010406328741552521015186335892928959457352185210813706585793586655431835891916663865991383787060819588518563583863708252865070444576697776679046010833807029569591348215890550165411598509381309327227435222644862430930229016269154648515310921604137823785068951323692515705020432705359040238577897883574592171044699141069510442621429004794500509511164629247377310724138812839948146966014875865442002316316147115822535873869666457623686808443012969266429403451480342554038729339523589198931048749201138547833872346632292790389972480203315668048506830004489963474939936865962713230081702234756288583317445417488060638503911953948752192577969339481782002204627524507475657361770841692340030079253938076572038965695553701689311893564901777963171410092537042768312674959903738742767629763355851912035193112645928966314357454371342743116099157217558740986764594149942742163671005121600737607969017218138001028636328155384350303672943227090754877409301936853603040377097713234172254531565106020239802368',


243        '164171010688258216356020741663906501410127235530735881272116103087925094171390144280159034536439457734870419127140401667195510331085657185332721089236401193044493457116299768844344303479235489462436380672117015123283299131391904179287678259173308536738761981139958654880852234908448338817289014166774169869251339379828599748492918775437864739032217778051333882990074116246281269364933724892342134504702491040016637557429810893780765197418589477584716543480995722533317862352141459217781316266211186486157019262080414077670264642736018426998113523445732680856144329876972273300703392584997729207197971083945700345494092400147186997307012069454068489589035676979448169848060836924945824197706493306108258511936030341393221586423523264452449403781993352421885094664052270795527632721896121424813173522474674395886155092203404036730748474781710715745446135468098139831824083259647919175273503681561172684624283384438504776503000432241604550454374116320822227191911322123484085063926350606342197146407841178028071147192533942517270553513988142925976090769695456221159699052583533011331652079347093098173086975483539274464023357456484465482927479569437320368592222760278170306076733438801098370797675711274671054970711442158930561684343135774118741594506702833147396758825015850042983343690345185995956235143825771620543546030664562647854656431302644574119873820215595718618624485232422006575550007068883734241454686368856734496265385908809403972494685137741122866896719678053937285818409751670320140501843039224040735870096889596273419106389103662095318937990625980136711988237421962315266686856089505981438440850638067589321141759499017023839596858455548192000140085142294166987063499024792681334843159790936321351919859758669569200541507612099780909705198902176026219872201715422096090343686272984351441594569506778041062663266799342793856313801540959815845788584759033248828248561586450271172777240971795656082001848115815260930521663167480173886064019118572778281516735157779555888167787064432558595410843987446497881666288423233170060413025924629950477303342180149398926073618582715358742250388958231281694757980523791263699450732952325727664209947786063982561775327638504516918570101319391698412388607603742484414748268389669129118026878969735782286841116842656410574647607524418900720328045377993386279808768990376289424757351052369393977137871998119168898493037938756635621557623138404459266598837784229325799838782026060481496865561757031839002257091802876949248392744175669112242088439883248336310597001257385980776961529351198877747193531054956881808332177946751404038228718567911769630971553915410012677600002457982207465176670752102117002773980548089696530972476439694599881281812973217265853884727906535479745854085338851105144585481994156206497436745899944877732531412541279014300324594890623941145509856940982863769834430048120562966797907114102689879364945689860493474954538422367719507882513166051007352994068319251450666676648368200564329382998758875760414259654004977261309988267319806354856051784553990936610634733375984159028722378614984450255386315585631994503350002142910493190254825610707400589976364985748467955131077971641882672895854571236368282811336220769174784720113331269084746524204124263475054112841630933586166195036115696469686075600480420563557567616835633252622327172811002146392754445051182169805284630259703542633955126179520113059629914229833688535925729676778028406897316106101038469119090984567152591962365415039646394591503830797626339246986057077758611413664914168745375266786298141171496573941614387744125843685677063619782918759823106021054037757857761587472240835040580447360544029064930412569943169729238102162312218687930203068055400275795180972382856696655279408212344832',


244        '26952120750404193513632261861396278924079113968766952876432881795989952773064717517023547582462602935861988343151554953944136541732655742330344989715209032364790613993477992341015538315419979331157634679343214071675070272395846031050203990104416181306504888110677311345026982121311496900694993981896839097431416270736937100764483879691603475885150790913382009428152150677416837810025855012562604552257734907950240215423643722920841320085070969159836995287070087420490979348953287935459923512005502958342051104035727152157034501872596309497091807346831534602296739237000381981019425624127797257428795930313308723276992913170326233270996326474955890573590440983689956983091520247822856749856820965867151327989623777624602572912120388034513739443184281299447784120922392413596992920178190422947851327532150609341086404785058445916781202298840013744572277995937219260793226200101547804156066660550285603334189758481973110179753448682028957898790867330285566013316232853414644614046984553042091064852269504063338721280356430534362274115530450091697615931104386348165503547977506883150962456655568148350174378900644954808571193522853482254105207391043768826214265699942108058612042527547825232804870924409920355692212828892863846898524675998477589207679627913426446911721636181076105773289579082001255169089756739791438011116518233115849097737157581281333580664166552977845960545954723805566039806442684931440076772740156280813903751559368611983279879027372690912528122650045008005005809343307282215075359167739564986702643979470063161755939428463215178956585736792740691950620097366581157756475030693880639628028957564717506748388201460479934997075131639772156110050292383682801311501912272752251146034896908669589822188561182421548567626442405902050737934260444280400808091464891948286615235680364697810945744811260658644380752469468836186050949182213434987088443266923626493072368804684047208628736100483353498142871019538184448301514555455010870017957531222712151602595676715076786235173047351215526266074242232161952576329350969226099826143111340343868870776877764034804728697456714672752694955488362666813205601556848124569582733894829010185412078368158205633679452772740325245039148128091807268340159268190332390713116057956368833309632262724886914292004136532397863207156676423356271923268788997230183054983059464198418861749695567960894202252252428985718482550976909314126235919259431415097735142937056722180867395933758463429791251108228353506370378738883720057492392037062821199203576669507492379745663106636034141603529648250152072791795482426726847812075334671757150236305208856903602455132348260148117295696786160355352582815449613577389346464373705124445269845460300288087567879763606935329100064117928257129252417621314419004760295848797915067238834947059440036300737231196862875219470421825117891378677739697421559711211629645270252793111734441650294153890976657767935712751203970943075020427006224205578839537057762673700366813557873687195377885524377489413547417966336038733668837250885045180743821511112631400632585671166459524266991554490866854531282544830112396457787644133453547856918930267859252150666726303020818421604707816925326976802969324733095651243384448217063086179891052711416102828902776777800575003340232129652988185822691921315007186111366967324619073300429154583580635182127032049900544244545877614607444202238535981253295792569233858056209849105015633097827466842007884364230830675959668956019416191744176273361652039495912566102173045501639186081539123978052600644656251454292831580163089995965156233995220589648586920484863866827793184837626067415823731083525652620669832827156376121692170869677070642914646861380391369585780688443200170048259608955804667153883910612516726213308610915717138614799386761520965945787127839457050969293052466264047315624091114595035121852015667880592176144651859725075932198615571560789839214709994586617323564833873826223285742144757371088512442294526818322560870149959071359649404990835260598668977487201391641043166495938834420563709960733615372690590955459181016613349571195006677610310002583941425268713657639502302803341273127570270640425767468628392567564760410981218311866726323025932458512505099003963583291824276379468077888588991880595511218503954977878133134979730471068872384092380589477389509938459514027145041834618844513493123450381617418440276701681286746028194024840212540436669375081186633501602178611269022208447096228181869444834504966501924555225696054544947206129816153131308335205416097203955681491548390262577040628244205265357720428630108475623343162491975302169920528121320528957901449810640978556725429813475199342692168963973253340960441915172016945686990705723008204739699363476332881074090180937394437542797628356677310043665712274506350688717886042284479518244686074959646346047403964455232532814174782630231938398909137493083955097318419378310781800343570308447561516825855786344789474629888793013470201743911722403671905785779851302951521921132715319986089541487934077691955482266807220271193537633086592882151150308693220488018175636884029840866394624403205565579590057527962012921266347225994979367899377208497520620936129908581263574751820276075465651145907167542331242133958382307096322911199736769597988300118662979347125708251012250130548531693570552624584154336043221663856927311119801227444935344728459975797444666683477304304565466799558739413214142745624868296093021840548408108284133874907162149854774961961427584595743817051618155142326168647056011338867898006827285744302239476116375199315336737573543155497019204012481403238908281049354957812260853879180351380194157400769663673812155953436673765910376334004666292477853537867662871238308187390899260490523967153636265268799510554541618376865163856548884752741759505726850279884726397853487909152060637968595571006650653455483279642541396711835514962791318266675127774800981248980551879698727644799613397656625541551710897466658456664422128462459317246909558705620849301799110441260238810244824269149895725661100522155256385441891068194026627970889014197024276645561363292170822142584766005537947377013084637179443743260546363616665310256887925165785266204306690292438898120371494508505316637646069386959561273837790540798539752405236061152352862816042538854769587005440351339714760090162072113995509567157488906861196780594046290353099182073183613284430701084935002839752590550751562907742484518683997180734853476722099449673240962819930529932444168559077769000316841734766444816028799535673071675338228964188255114321594468218878208314581807542614629089851073096897231513024947406152399667303062490554608082062728352653787956017464487187973175435276455438354935592052167112322604392662045767918388805257954592744043455097699580368600917403323813475962872048741029144684051016765558592279266497621805828487724797698180628421670657972769274936562693990701778769245014493873070983648996255754271338304680209337765482626114795132189802426201979332758083613325788234699620295352040580332040824799909539814474800169863581704020475493961264321714819246847318743352835136103926806505544549908267250237738233812823453475627188921057250941636157067180515026083437510656852380716390684473449594460330458925616289093713297296170931498389442936383986610935498709801397585871717062958941748357812271705754879617475612535882476104585221272969815038430888621530428764313341480567925789660550772911037726992636455102674850865267643942347482222424003636645592271860976670047577546162176'


245    }


246]


247// vfmt on


248


249struct DivModTest {


250    dividend  TestInteger


251    divisor   TestInteger


252    quotient  TestInteger


253    remainder TestInteger


254}


255


256// vfmt off


257const div_mod_test_data = [


258    DivModTest{0, 7, 0, 0},


259    DivModTest{0, -7, 0, 0},


260    DivModTest{3, 7, 0, 3},


261    DivModTest{-3, -7, 0, -3},


262    DivModTest{-3, 7, 0, -3},


263    DivModTest{3, -7, 0, 3},


264    DivModTest{7, 3, 2, 1},


265    DivModTest{-7, -3, 2, -1},


266    DivModTest{-7, 3, -2, -1},


267    DivModTest{7, -3, -2, 1},


268    DivModTest{8, 2, 4, 0},


269    DivModTest{-8, -2, 4, 0},


270    DivModTest{-8, 2, -4, 0},


271    DivModTest{8, -2, -4, 0},


272    DivModTest{13, 10, 1, 3},


273    DivModTest{13, 9, 1, 4},


274    DivModTest{7, 5, 1, 2},


275    DivModTest{'2103180314840157', '1631403814113', 1289, '300798448500'},


276    DivModTest{'21408410031413414147401', '3130541314113413', '6838564', '2900204736088469'}


277    DivModTest{


278        '13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096',


279        '13407807926845237209807376456131917626043958556151178674833163543294276330515137663421134775482798690129946803802212663956180562088664022929883876655300863',


280        1,


281        '3097359889766648542073928501435407264441214702890397900427487699558409313380739522684104737560085054384273386897573320723282547016549772350783233',


282    },


283    DivModTest{


284        '24388660549343689307666288436614463270948472382596516055139370678271628439810393042585576900667596857198513726355043536294702186342478937800831',


285        '38733748171303628844838787580045178098452927239062690602450784467058896912531690007767956310348951731921168881868406259712',


286        '629648864382619361826',


287        '2724578611525334851445652767465274410979805962941953382558409365935061481311529445551691298696266856092833571769883246719',


288    },


289     DivModTest{'1', '115792089237316195423570985008687907853269984665640564039457584007908834671663', '0', '1'},


290]


291// vfmt on


292


293struct DivTest {


294    dividend TestInteger


295    divisor  TestInteger


296    quotient TestInteger


297}


298


299// vfmt off


300const div_test_data = [


301    DivTest{0, 1, 0},


302    DivTest{0, -1, 0},


303    DivTest{1234, 10, 123},


304    DivTest{-1234, 10, -123},


305    DivTest{1234, -10, -123},


306    DivTest{-1234, -10, 123},


307]


308// vfmt on


309


310struct ModEuclidTest {


311    dividend TestInteger


312    divisor  TestInteger


313    modulus  TestInteger


314}


315


316// vfmt off


317const mod_euclid_test_data = [


318    ModEuclidTest{-7, 3, 2},


319    ModEuclidTest{7, 3, 1},


320    ModEuclidTest{7, -3, 1},


321    ModEuclidTest{-7, -3, 2},


322]


323// vfmt on


324


325enum Comparison {


326    less    = -1


327    equal   = 0


328    greater = 1


329}


330


331struct ComparisonTest {


332    lhs TestInteger


333    rhs TestInteger


334    cmp Comparison


335}


336


337// vfmt off


338const comparison_test_data = [


339    ComparisonTest{ -45, 35, .less },


340    ComparisonTest{ -3, 13, .less },


341    ComparisonTest{ u32(352395), u32(51830), .greater },


342    ComparisonTest{ u32(52395), u32(52395), .equal },


343    ComparisonTest{ '574720348957234098573049571938519023857709',


344        '58745908123509182375091823601928385712908347298341752397182643294', .less },


345]


346// vfmt on


347


348struct StrTest {


349    value    TestInteger


350    expected string


351}


352


353// vfmt off


354const str_test_data = [


355    StrTest{ 255, '255' },


356    StrTest{ 127, '127' },


357    StrTest{ 1024, '1024' },


358    StrTest{ u64(4294967295), '4294967295' },


359    StrTest{ u64(4398046511104), '4398046511104' },


360    StrTest{ u64(-1), '18446744073709551615' },


361    StrTest{ IntegerRadix{ 'e'.repeat(80), 16 }, '1993587900192849410235353592424915306962524220866209251950572167300738410728597846688097947807470' },


362]


363// vfmt on


364


365struct BytesTest {


366    value           TestInteger


367    expected        []u8


368    expected_signum int


369}


370


371// vfmt off


372const bytes_test_data = [


373    BytesTest{ u64(0x1337cafebabe), [u8(0x13), 0x37, 0xca, 0xfe, 0xba, 0xbe], 1 },


374]


375// vfmt on


376


377struct HexTest {


378    // `value` must be in hex, as we get a big.Integer with radix 16, then


379    // check if the output of .hex() is the same as the original `value`.


380    value string


381}


382


383// vfmt off


384const hex_test_data = [


385    HexTest{ '123' },


386    HexTest{ 'a'.repeat(11) },


387    HexTest{ 'b'.repeat(15) },


388    HexTest{ 'c'.repeat(32) },


389    HexTest{ 'd'.repeat(5185) },


390    HexTest{ 'e'.repeat(5185) },


391    HexTest{ 'cafe'.repeat(85) },


392    HexTest{ '0' },


393]


394// vfmt on


395


396struct PowTest {


397    base     TestInteger


398    exponent u32


399    power    TestInteger


400}


401


402// vfmt off


403const pow_test_data = [


404    PowTest{ 0, 0, 1},


405    PowTest{ 0, 1, 0},


406    PowTest{ 1, 0, 1},


407    PowTest{ 1, 1, 1},


408    PowTest{ 2, 0, 1 },


409    PowTest{ 2, 1, 2 },


410    PowTest{ 2, 5, 32 },


411    PowTest{ 2, 10, 1024 },


412    PowTest{ 2, 30, 1073741824 },


413    PowTest{ 2, 234, '27606985387162255149739023449108101809804435888681546220650096895197184' },


414    PowTest{ 2, 524, '54918381281044877719855206392651145738155482401146443275155707673484345467181248416980477125291636439818370491131846864296975903997733150500592226328920457216' },


415    PowTest{ 2, 291, '3978585891278293137243057985174566720803649206378781739523711815145275976100267004264448' },


416    PowTest{ 2, 13051, '55267956948146482939580690892144167523198080345777838207973892310290788736821578114330455608899403999039109810492889769112675765371767842822434294904209432777633054910495035098236995390194172097907719098491142950680893121170415521376299250142695723393227633360829843822866024641522563385984082711736391348667978440753913719338262829073043347247299392139063557930790932287363651577574134082253690763995791163252208415844758727346329281304595424562991322680879863770722706799961809876056054813814521080566806686543718660613598426151803438498674178140121315919034857314115503781267190616565875833106631659285123886667080327050174176636018357664222092316439777145540128647880814336995055642164733977751410563822190384321689041057299634727749812974144023207025653904438780374867988942510987313912358915642077631661267839921263001062107729173356916478717702317027506423498272334490092958377684733699662429071107215486273972618250534115869723283498114137145525373906475082833289104669492127120264073453925068828669125794548775264089233042803009595366761575381131720150020416662597433270991992738498853512916968911947303026796659580500368762437079002069661349769285545784372450396095376496629526120146056228969588758257289220372378463001533895184835727768908852564233327092981929411751106985223047814350329661006786989543912993534105514927316542621884655977620130711246926843567109456472355504038497809114457931293164130666363146093971664611970414478485192994816264742799354431903294883107927606299200191395563965045258006700385533997784569469661002395464091760511030079955508794507716517333922113296290807049250301483689712907877303498967096232669748824940257740874215641972642675515304831959934847559373172772025875939941676740275689817054162918846662455567085919928556650978239087803483530882408322645489433079587537294621171822004369279659604911446107164265409771411479042191057214450986176256578104398112366947709868794481776078240442638184240046590399307658325666682824402555546582169125084299171911366515003536406493880562467793738217233554231178610461637407108387422104493358650812565981939865004194724312308819851360505832016659131404286536166604042995985362843053197530692653760538388205506347898194204185268035169011980847365832662902833167362084522724032944503999606348026648228492541892525660287991575613769500299950657228084617208982541726107251394954812792421965613075539830944521759805581201863306109230481535735866977702920938163637191044218917218763676996478413703527738808285760128085267402333007136279283870165611587883351595579551530437487879301447035074519559776804970191650066388050122761542282202772884141794482588913487773583646082244648646898935682167457258599202486566745556266587599528210145725708324833027469913664602498185234663551855895508091756784116786760256088764788750159984191050146275837122761351322740020869396023016337700936855961260331330031678574208143275974341369638055331776401934895373348591440122433244331646746067969385005236926872015898048323445768868147713435873976237988151319143506783129013204847868879150394120372376677277312144782189330256123263292237715700439809503932239415509520929779856708018666527067600827221597869399175438321388641981165828368557419771140117333070030872143102607788421073131616871657178020327435898081376870580959579623464843234800465871796556467456341474610533391530095305196315887535933316836459037786625667180354374811843995688474490608169113180680143676925870456310071925085465713774179009107449991929491343540484244181606094673172473788660554675839157004904589906389801922612312350223513086754383162398737177774230411158150377305076748192396441454734336654918968445280484743879759859090769539002965788922965135895758979301734303194298909826556775859142046683115828058122817136236184480127270446495870009273426474586242661860904296452193946364822434632085953525238418258226591281397400949183681177585810194950485799542968112294068369136156497511211228725248' },


417    PowTest{ 324, 315, '66325146064916587705822805477951823674769212922003325230500180789514487101799702287247301347816140714887582527826252837635296749781071351621748491469338347097923896026211183517655658952346069454893422558286798338709431368762851475568899541999504754550056265493269010870696623999709399529395247064542825851568385196637089440522882877102429945439977107582295420418108331098961838419917230847980056560488541780255425015021238743932289115066701337398107639567748102191005710201353615093246958907555634902309636451244444952203735074916066229982498598205421944122042066749035283837586883383420374291325389757869347147357807188516650352693616763867685354382631931356465247637321960345782811272139101785279798666504361229957479336436466489780129445016691164329417001378480690804715301830926348058624' },


418    PowTest{ '68973377060666327208300998134976245269331422613575559102002431189859063751444117873216302679385447519268197493634614796410525545235779538750217378947422409274212222649954053354836156', 40, '35258157541008739895331135586163782978774260107060350863053496129803595902499520940913245496659764125837663081609116693664859066121240222710455090772654236305161593582934388795922429749725757888593191060785569873278223392217676911081371575408698209198487574208133504092628962419627719435594361886665948512724378730193034883682168393683858735816474842100358088758399284368135640873191297579994494530855391610253450197112507337023973260390114533551942575098377704162567050376536430239009068399198141851190687786692855878006471015617730177140564368490211125304311492626663371442064896009452985346147238789927023952155765874191186509560387099879963058580458175561206837610198181475959286262651094184535935843622210514022579661392260730979033525048986082578378757345674162044090708247493623847265486608083275091608623071230279318646779316496782411478544030608676817377643527831062728898442877397153923451755987019024165148269190403334041384095965099409973404146520908147697493051017569834287683508859619614820718839901473820225092359044663170397185665222505521573782264521807940918163830187995079966398797834892374540329644161011839047312660408041075233827338195607721484103616473925700064580565891872491802099275924411222757546424787635592046987870959737279307319356334181603750301494352434527308393706898772379215484237398245418863149959467744064471526937704836205865867678040592702295144785801441309292006081240708835717111188736116077625711594150435701058724546928000620650885222066533349258673109739859759612800975406051665452593729572474029949396850025034721391155268272910460099672143460177826856963197730677959657469514888519160035227448297269382534435799272102328415501312356111831947752575670395475105022420187733034171502887359638152057876379771261999121543335479247633748144423214477698449199446169433490219980784078516768935903866137328947352936172402921848772002674322630245635026231629454706048753547546902225014320540104977155736944657399787940439035277957092279432489442361800063891355739406363001782622680936832010543170656715775452062089081852640884272056572152042908273232284891160722405506506925047900433631369352240575822425084000954380503324509277410828459755147240727523792066016952349310027090166657648299162430936093103120333183134330248812717816439403194436580527262279045316890050092161084522990205107250830319663209486820407463781212079072171125202655959768122491168090453120012969830867004575480551791284934079004033495761485325184899900038803474124601794212496136498280996063010402993132647266142814962192181619151827932124894236921088644522787656602462050326681805844438219230755707199226244584366270014878488134597806515533702003407174379138958404132228268468415855937695923909093324159910887747556292181906257010119373908909281031098335560145512862280651673879872429356095545191263033441020104833977186041802651653142739004325260453065487714226086302334925470018494814279647772696732751413492938129340193390870371914405132971752944771382425547764289488463024568565047205504469195296554979731615888034588174368312122402232599112594230523742220097645109619918997486658429331785718355443479680146829664055646997657939426194000103378913037286846713039443955792103079259450246916434767428300921600590858128004218244953067853605711134269179529138347808509232974732360192374463207085903368535685042319215946964616538267824251199799335578316284176334931243032435271890535306860625400974970800196067356950499429899623903038882907645186739157691937393868001954217068677405564876964259777068576274955960434304735331332727337942605330662700571524428729266514174137948899430401136194700301206200551515499664922638963028270893302781587131748991793976526030657152281703854200233227924967926571276661994874579099755225676717805006216569595520566828236321367761203653020465515401663214232518761474223110777886389720199103747449349499503400895567044624612530615359244422254804356461625965858659146045123680314611311068802319473327814245022783376966016661309117610975157629715943310597824424800462948268112526010321134293021657131436472752011710620253048339957169295446502441751862148811884121265645084802972835434430500666554560667426728304121819451042399317183881953483237660080276310900310609399239782487398889813072240297043891794998893001786233968869912478411537501683017172187740347782175947175330986012037410594509842385173934376073883704392390066195094586380644822566323337063806458420270229827713462151670514123181768373835781491371536706582982089663589356740349371026605036928057179599547510869011654375677928737943079864386098501933754834569076969459522907991122865834472316075011973279443310747045576723382195820376147552983791746734829752811505837765374961937584859088696438357582609441168579224373232538884336186944109656062668354958262471022386307605217481710783595873812958322692301637767626905751159343436670100901639626281237260581520402478166789720378200977977591043846005303066270994585484308872635398698206784922087791315869659668470550750672041440181846921937878737954369397741595712732557836089455119269549939304717990844018805341426733137219366976467073055703514345869726491666687917740218342964217322837128666044618309225468654622198231241735033740025000833039365889040210467381631582635008903317248408687515878944562462103899122853122282077536393859736678126798284896936745206987705406162201111434866485708471709121620748864731821841498499097932663197004613917962363847058188708935507962599345315904755192312885153454959868456584090394953490529701708225758187924021653717046235748081644499911269567590535014838235292295638849624380239182552648037518233234630924354382791335743589786044871629805970609844860052222008562149922586920233688221038240158947965090122365291307769963243469486471480976812917614890560320724900635565696327855056530135961774334692292338693195704454096038710058676180521224229217340225496509476508946611845834909161932831898098821430336348772505879016381899870043035683249316508108617843133439016918107763134987853201904389395477535249692909938456858665886155150195584515422711040259472814260855939483496834006050935205671281977481531908760417170523135516028527539444163160573194971206959625166833408764832574810255735634834363957899317195483566233828249891102020662519608925798051078615457621971822365495901117747375145048348614866478147644564817801751372420581094557535616477014993403293835622275791359197059201243272901787903487483825695988147058737185860181150381743018939858230502180587316663351024125733956328873574985787891695924518737336301071771593783442839325168387680903413878668606904467043759169383257006087574325785908578823397586231203787496335131359918746993718914006871027887598302839973090822047886906908431573569039736038250163656132301560418543891406517287043442644328121923996383111070947282060547074035037933135808930649423603110117360018001877349840800296558270695890794753087083525850557161190187608610387510161000273695896242816085985017009465480555075198416753288507556316216285114056684935945988548526597279887832288588727265282867869907650516070481891621446962371494964005298779179376792868773282807097284115930818770799203719816032512376608176221517386343418001080528568223383975802920001284696679468308086909698604190274805636772843836377041111569722570010440042124020486157215597592576' },


419]


420// vfmt on


421


422struct ModPowTest {


423    base     TestInteger


424    exponent u32


425    modulus  TestInteger


426    power    TestInteger


427}


428


429// vfmt off


430const mod_pow_test_data = [


431    ModPowTest{ 0, 0, 123, 1 },


432    ModPowTest{ 0, 1, 123, 0 },


433    ModPowTest{ 1, 0, 123, 1 },


434    ModPowTest{ 1, 1, 123, 1 },


435    ModPowTest{ 324, 315, 632, 512 },


436    ModPowTest{ 65, 17, 3233, 2790 },


437    ModPowTest{ 2790, 413, 3233, 65 },


438]


439// vfmt on


440


441struct BigModPowTest {


442    base     TestInteger


443    exponent TestInteger


444    modulus  TestInteger


445    power    TestInteger


446}


447


448// vfmt off


449const big_mod_pow_test_data = [


450    BigModPowTest{  0,  0, 4205,   1 },


451    BigModPowTest{  0,  1, 4205,   0 },


452    BigModPowTest{  1,  0, 4205,   1 },


453    BigModPowTest{  1,  1, 4205,   1 },


454    BigModPowTest{ 23, 35, 4205, 552 }, // passed to mod_pow


455    BigModPowTest{


456        '5155371529688',


457        '2791323022555160232601405723625177570767523893639864538140315412',


458        '108959927459825236754563833',


459        '26860526814751021488886966'


460    },


461    BigModPowTest{ // odd modulus


462        '352374589237450928347609812740958719304509123759871239856523745782375908723095729758275893947985713250128357912349123412939358823582385385198351236046127834612374812370491327508137250913279785120956123875610235871239857198203659081236598012735981327096129836712397538257324587324658973246586212305713209851290386517823650983',


463        '1435987139846732486843289483294829493285238539385476982375980650172394182703846128975612083751298035612365812378908579834576456739458768754674674758467957697513267415734673649713598712634987126359872685236563875',


464        '235091287508475298347528357901372598012305123512513252139683276908769284375274983274732895287478365817326581273509823651087861235876123563725193512827341395182375612384723587131912725187352562171235812387132578235385239913578132684794719844871326571632561325617256983275689175687132487134894717895941563769587165871727358791326578126587261589732165781623578921653625871256781326587132658716237561235612783569812358791263985688921356634756374561398756298576128463875627',


465        '169366899917096971139137080261692248176119100321982279129907315595573960531869689311776921667033660828498254917762241531493510090131310371752611041591194730984721766392649610729748330695093443476931010397820703902902374473806912248240019857777647140275706106146415293419050004306619925031697942412075960435433660980502714238024766862370671258678169869169308956145487178274009104771385352022837969419172440632584754050020898915411115587200113298960058827089497449758704',


466    },


467    BigModPowTest{


468        '65963856903485603485069234860923480925798172358172309571298347102836578126398512837409812375712637895612379856123981237510298356120347129803401236571623978561287347129837563453245983475983457439573985398456987356198236481727340813259182735619827356189723658763578623842342348791856178236598273498213492641265929375983589324658972364587869871263587612387568767345727346273647235738786247865198746132879461234613284823467',


469        '83272598179813257612837472873648237598405840629839475914921364871236813258573298457912734897123942134273981',


470        '5839857294085157278513295172390857198203571235213752396329429342385198326512374982374982394818327590816263059612397512983479812378951235123571239857908674389573485791835127834617823648791263587321501273958734987520983475818586128374612837589734985729073459081628387561982736547958729875923652356138756183576',


471        '1473628912328925119498300555459646092229919432628304743927027840523966896206312866878166443381090567655363186687840805386391819767096022910509388879763843632740700147538366282034781700814905320520871339523971198789410048087451530293781098724024347130773477767285944506944257502250353223975013799044669645147',


472    },


473    BigModPowTest{


474        '113242346235324852305823906832570234458325884382848882352385183957109823579028553482572308468203945823946234096234056990567506978059607985823049523458273598234750329857',


475        '8' + '0'.repeat(304),


476        '538232475982347092375235252304678234670293486732980467394932151374571938467459586739087429813752353459823475982375983259823495510986571430996238476587342658172851235761398456398765813459801238751782351252542389712789568712342749837482748292340120120350125012352859821657823501275012365123985761983576123561273561257632958127659327160124712350123571029356123512507123598321797',


477        '192406008638594029999856291470760872362212741932343638540342189789173751505083836385843995643278520411152869906156437055678588013127671381619800101872065097151880787029771615331116606406595932983669815757450573569058422413443800383057849205750667577751024330669200452034408252515262931175662782786664172617789499914619948520343146045783354828154425927051367644302499369000252',


478    },


479    BigModPowTest{ // even modulus


480        '235823052395732458137502345873250',


481        '9247324572804102889565555777311914057954687482673431192869682151395651003606366864848904841770165182604035932529621174486515688424932060959148379649412557',


482        '2176617445861743577319100889181907668374255538511144643224689886235383840957210909013086056401571399717235807266581649606472148410291413364152197364477180887395655483738115072677402235101762521901569820740293149529620419333266262073471054548368736039519702486226506248861060256971802984953561121442680157668000761429988222457090413873973970171927093992114751765168063614761119615476233422096442783117971236371647333871414335895773474667308967050807005509320424799678417036867928316761272274230314067548291133582479583061439577559347101961771406173684378522703483495337037655006751328447510550299250924469288818',


483        '442997670902441289693502035236411859724060788065895656400579052337406446773758010436855122951259016429941998670112046510440662262181776245572088822784133641469508278250883828352296420961829921453124482851450238472747959697964344812370952273954391788494014188845640003786259215718720844436373044245757220429613176387487778233231542432645946351180509817097194411903946161272789482180797502735809791321387092632573236334305080001390892058454801700346356574718281589228939135660037060121182304974907075601193595994210348704718150369101358547875357900995290428579291079564736470284970163062216850888677989344123412'


484    },


485    BigModPowTest{


486        '5155342534532472457235424353715296885321784212092346234575235718572938457284759829789708703754094283682345782309123940810923850923745723498672398459023845028309402347698798128209480234598716824503042159',


487        '86088201503667039039649712985497870124991029230637396538140315482910296196688861780721773488400937149055855947456947824680518799310618149812585881185273945728945238450238465982768132749812308932579342985729345798328459832591982374981237590923882894732852358383128938192888912389148132163716923461512177401900495710673973552425181964932538140315421936569702910921834517138450159290932430254268769414',


488        '274591906405224388599271723580726658164960647214841029141336415219736447718088739565548373811507267740223510760319632557286907774120057322163752385728943578236484780326508234652347012734098132747829056238742677853836742172732148487951998402235107603196866575250296113164460906849287604912497386435248807205228608',


489        '191409711082233170599206818399072245570776992384487887400529042633340865718475272702984694979757086140971619519330041885966232600204343618098862571914303534164078578922423233100444505069197147657365390879382972696958855409999020160689093198793125749417593529720182526801136320146027275209623807723638007207345057',


490    },


491    BigModPowTest{ // power of 2 modulus


492        '853475230582304956623462734587234857',


493        '583752847502934572695871320598123057810835791832765601237490813250912360591237591247132543095792347598327957137481023974819237887128577123758127912735720912735708362178561027835610235610256231201472309873219800321951',


494        '31195165372897259196222538898096203590151924108450147950531565441852619837316692843188389598728651769482088968838700984268947453885587967878549286444999755742573423371025356539077075265986419171772426279084559025861175301940492273427120221755816136975739916983004778387946699939545354293487098252428954036286183995782377175227121587657233553706589448547148066273280603243167958729707736664649187444136702017299877489729451997277875868782399735511520086969969766278182145454186690598629675562422923132555707758646587702550600894625696538109646366308973392363200122154242784576162149305816215109893613161331026672647000825615987247035266514313689413563779184515427920269935280569035788081552413007563772309295149800172031645681720569680154349893907395864528243629654386620034655445226295834594630792819545156798270599481573436039129275439653984521135652249263653985326577886990615665734998585216581730937090703518997669223802429711292740491797911117308280939507973715877108492303860661291987529284719391551256912380499409630332506454532263266457209921483705507359152839264852808182519011100934922492651373859423833024010283468753147686188675294998119637462200763443029190704825719342806119404339670408160210011918981038977425180213726646978883378058838510330816291941879581568740273684084511318422175006728346276489384220596694727036836687670632486602655240593463885077059375085482211864761344849868123074687509143827139683659102930877963676911995751113159944160296419825178911962487549670296207457410515598040046860567719116506974858703739531721991704589155513182996455827177472',


495        '20080128881481836026329919458482291336427826856257996902940216961274769492432457342329585911526680598599706497937330675336231322550089070961997878231160797014417182095610964306078005177657705895303701167263611016504813896879268670353690809857529479048652197026092060293580162938995900771157020773980149060390600886988165389386800313399935681668574561849644795370126640258861886083152431680309682414362667647047408205246634496700184520404072535696087062725321498879508195864728319264953502905783599235208616928912295007582161378604427602444176983900856363236858555001132922259491209136145654862306503211818341793436738181575298025051779368026867674815572620689517665845691581156037531328681002192885908572782500210185856071870996928958700199226442991667291661898788475465881534872952976564959204125435567408766407069080824764398534937188392006557445009391997597405999602710062336419706104598663078108578494090878260551511868925451048198114479011315931259263368212342695453474607592164864833976245439378166385649596428707473508482940426102862136582304433403471613967149235623865180698593404828164563801111816849132293956996556247415009648932020221786934682827799748481777622180801590275002765776928805756187584952776044614940158088391767782343033313716059721086499569092199761880797791493764006487948292742803823944731896556184944138299575510183812680359579022267096795084742403276965131310267236257021618824374001979653996305168583849734973984410291953747451176667816227487401602863864660642232048020325795772190251487050535547981550465960228478297407995702324941118877701015321',


496    },


497    BigModPowTest{


498        '919883988246145022313927375667609631628',


499        '11258911920206359584',


500        '10961431611736082634',


501        '3987973861467626556',


502    },


503    BigModPowTest{


504        '319978239103006490429056663053051872523340306',


505        '3450311374119871456',


506        '16136980157234240016',


507        '6495281920355297920',


508    },


509    BigModPowTest{


510        '6572721605915324110691520672890333438736158723396',


511        '8598931276445806048',


512        '6234270195866676796',


513        '2267960990325264040',


514    },


515]


516// vfmt on


517


518struct GCDTest {


519    a        TestInteger


520    b        TestInteger


521    expected TestInteger


522}


523


524// vfmt off


525const gcd_test_data = [


526    GCDTest{ 0, 0, 0 },


527    GCDTest{ 10, 0, 10 },


528    GCDTest{ 10, 0, 10 },


529    GCDTest{ 1, 1, 1 },


530    GCDTest{ 0, 1, 1 },


531    GCDTest{ 0, -18, 18 },


532    GCDTest{ 51, 22, 1 },


533    GCDTest{ 98, 56, 14 },


534    GCDTest{ '67116917544110', '60943431483592', '6299482' },


535]


536// vfmt on


537


538struct FactorialTest {


539    base     TestInteger


540    expected TestInteger


541}


542


543// vfmt off


544const factorial_test_data = [


545    FactorialTest{ 5, 120 },


546    FactorialTest{ 100, '93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000' },


547]


548// vfmt on


549


550// for left_shift and right_shift


551struct ShiftTest {


552    base     TestInteger


553    amount   u32


554    expected TestInteger


555}


556


557// vfmt off


558const left_shift_test_data = [


559    ShiftTest{ 45, 2, 45 * 4 },


560    ShiftTest{ 45, 3, 45 * 8 },


561    ShiftTest{ 45, 4, 45 * 16 },


562    ShiftTest{ 45, 5, 45 * 32 },


563    ShiftTest{ u64(0xabcedabcde), 20, u64(0xabcedabcde00000) },


564    ShiftTest{ [u8(1), 1, 1], 56, [u8(1), 1, 1, 0, 0, 0, 0, 0, 0, 0] },


565]


566


567const right_shift_test_data = [


568    ShiftTest{ -8, 4, 0 },


569    ShiftTest{ -8, 40, 0 },


570    ShiftTest{ 45, 3, 5 },


571    ShiftTest{ 0x13374956, 16, 0x1337 },


572    ShiftTest{ [u8(1), 1, 1, 0, 0, 0, 0, 0, 0, 0], 56, [u8(1), 1, 1] },


573]


574// vfmt on


575


576struct ISqrtTest {


577    base     TestInteger


578    expected TestInteger


579}


580


581// vfmt off


582const isqrt_test_data = [


583    ISqrtTest{ '32653970479009599018236258903443284683789766179879955366041757982300361890625826551918485225', '5714365273502351023665817936982376512387569235' },


584    ISqrtTest{ '1234567901234567901234567901234567901234567901234567901234567901234567901234567901234567901234567654320987654320987654320987654320987654320987654320987654320987654320987654320987654320987654321', '1'.repeat(97) },


585]


586// vfmt on


587


588struct BitLenTest {


589    value    TestInteger


590    expected u32


591}


592


593// vfmt off


594const bit_len_test_data = [


595    BitLenTest{ big.zero_int, 0 },


596    BitLenTest{ big.one_int, 1 },


597    BitLenTest{ u32(0xffffffff), 32 },


598    BitLenTest{ big.one_int.left_shift(1239), 1240 },


599    BitLenTest{ '4338476092346017364013796407961305761039463198075691378460917856', 212 },


600]


601// vfmt on


602


603struct ModInverseTest {


604    value   string


605    modulus string


606}


607


608// vfmt off


609const mod_inverse_test_data = [


610    ModInverseTest{'1234567', '458948883992'},


611    ModInverseTest{


612        '239487239847',


613        '2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919',


614    },


615]


616// vfmt on


617


618fn test_integer_from() {


619    for test_data in [


620        // add integer_from_..._test_data to this array


621        integer_from_int_test_data,


622        integer_from_u64_test_data,


623        integer_from_bytes_test_data,


624        integer_from_string_test_data,


625        integer_from_radix_test_data,


626    ] {


627        for t in test_data {


628            assert t.expected.trim_string_left('0x') == if t.expected.starts_with('0x') {


629                t.value.parse().hex()


630            } else {


631                t.value.parse().str()


632            }


633        }


634    }


635}


636


637fn test_bytes() {


638    for t in bytes_test_data {


639        r, s := t.value.parse().bytes()


640        assert r == t.expected


641        assert s == t.expected_signum


642    }


643


644    mut bytes := []u8{cap: 1024}


645    for i in 0 .. bytes.cap {


646        bytes << u8(i | 1)


647    }


648    result, sign := big.integer_from_bytes(bytes).bytes()


649    assert result == bytes


650    assert sign == 1


651}


652


653fn test_is_power_of_2() {


654    for t in is_power_of_2_test_data {


655        assert t.value.parse().is_power_of_2() == t.expected


656    }


657}


658


659fn test_is_odd() {


660    for t in is_odd_test_data {


661        assert t.value.parse().is_odd() == t.expected


662    }


663}


664


665fn test_addition() {


666    for t in add_test_data {


667        assert t.augend.parse() + t.addend.parse() == t.sum.parse(), 't.augend: ${t.augend}  + t.addend: ${t.addend}'


668    }


669}


670


671fn test_add_sign() {


672    for a in -10 .. 10 {


673        for b in -10 .. 10 {


674            big_a := big.integer_from_int(a)


675            big_b := big.integer_from_int(b)


676            assert (big_a + big_b).str() == (a + b).str()


677        }


678    }


679}


680


681fn test_subtraction() {


682    for t in sub_test_data {


683        assert t.minuend.parse() - t.subtrahend.parse() == t.difference.parse(), 't.minuend: ${t.minuend}  - t.subtrahend: ${t.subtrahend}'


684    }


685}


686


687fn test_mul() {


688    for t in mul_test_data {


689        assert t.multiplicand.parse() * t.multiplier.parse() == t.product.parse()


690    }


691


692    for t in div_mod_test_data {


693        assert t.divisor.parse() * t.quotient.parse() == t.dividend.parse() - t.remainder.parse()


694    }


695}


696


697fn test_div() {


698    for t in div_mod_test_data {


699        assert t.dividend.parse() / t.divisor.parse() == t.quotient.parse()


700    }


701    for t in div_test_data {


702        assert t.dividend.parse() / t.divisor.parse() == t.quotient.parse()


703    }


704}


705


706fn test_mod() {


707    for t in div_mod_test_data {


708        assert t.dividend.parse() % t.divisor.parse() == t.remainder.parse()


709    }


710}


711


712fn test_mod_euclid() {


713    for t in mod_euclid_test_data {


714        assert t.dividend.parse().mod_euclid(t.divisor.parse()) == t.modulus.parse()


715    }


716}


717


718fn test_mod_sign() {


719    for a in -10 .. 10 {


720        for b in -10 .. 10 {


721            if b == 0 {


722                continue


723            }


724            big_a := big.integer_from_int(a)


725            big_b := big.integer_from_int(b)


726            assert (big_a % big_b).str() == (a % b).str()


727        }


728    }


729}


730


731fn test_div_mod() {


732    for t in div_mod_test_data {


733        a := t.dividend.parse()


734        b := t.divisor.parse()


735        eq := t.quotient.parse()


736        er := t.remainder.parse()


737


738        q, r := a.div_mod(b)


739        assert q == eq


740        assert r == er


741    }


742


743    // an extra test for checked division by zero


744    if _, _ := div_mod_test_data[0].dividend.parse().div_mod_checked(TestInteger(0).parse()) {


745        assert false, 'Division by 0 should return an error'


746    }


747}


748


749fn test_comparison() {


750    for t in comparison_test_data {


751        a := t.lhs.parse()


752        b := t.rhs.parse()


753


754        assert a == a


755        assert a <= a


756        assert a >= a


757


758        assert b == b


759        assert b <= b


760        assert b >= b


761


762        lt := t.cmp == Comparison.less


763        gt := t.cmp == Comparison.greater


764        eq := t.cmp == Comparison.equal


765


766        assert (a < b) == lt


767        assert (a > b) == gt


768        assert (a <= b) == !gt


769        assert (a >= b) == !lt


770        assert (a == b) == eq


771        assert (a != b) == !eq


772    }


773}


774


775fn test_conversion() {


776    ten := big.integer_from_int(10)


777


778    mut n := big.integer_from_u64(u64(-1))


779


780    mut digits := []rune{}


781    for n.signum != 0 {


782        quot, rem := n.div_mod(ten)


783        digits << rune(rem.int()) + `0`


784        n = quot


785    }


786


787    assert digits.reverse().string() == '18446744073709551615'


788}


789


790fn test_from_and_to_hex() {


791    for t in hex_test_data {


792        assert (big.integer_from_radix(t.value, 16) or { panic('Cannot read hexadecimal') }.hex()) == t.value


793    }


794}


795


796fn test_radix() {


797    number := '1234567890123456789012345678901234567890'


798    a := big.integer_from_radix(number, 10)!


799    for radix in 2 .. 37 {


800        str := a.radix_str(radix)


801        b := big.integer_from_radix(str, radix)!


802        assert b.str() == number


803    }


804}


805


806fn test_str() {


807    for t in str_test_data {


808        assert t.value.parse().str() == t.expected


809    }


810}


811


812fn test_pow() {


813    for t in pow_test_data {


814        assert t.base.parse().pow(t.exponent) == t.power.parse()


815    }


816}


817


818fn test_mod_pow() {


819    for t in mod_pow_test_data {


820        assert t.base.parse().mod_pow(t.exponent, t.modulus.parse()) == t.power.parse()


821    }


822}


823


824fn test_big_mod_pow() {


825    for t in big_mod_pow_test_data {


826        a := t.base.parse()


827        e := t.exponent.parse()


828        m := t.modulus.parse()


829        r := t.power.parse()


830        assert a.big_mod_pow(e, m) or { panic(err) } == r


831    }


832}


833


834fn test_gcd_vs_gcd_binary_vs_gcd_euclid() {


835    for t in gcd_test_data {


836        a := t.a.parse()


837        b := t.b.parse()


838        expected := t.expected.parse()


839        assert a.gcd(b) == expected


840        assert a.gcd_binary(b) == expected


841        assert a.gcd_euclid(b) == expected


842    }


843}


844


845fn test_factorial() {


846    for t in factorial_test_data {


847        a := t.base.parse()


848        r := t.expected.parse()


849        assert a.factorial() == r


850    }


851}


852


853fn test_inc_and_dec() {


854    mut a := big.integer_from_int(2)


855    mut b := big.integer_from_int(3)


856    mut c := big.integer_from_int(4)


857


858    a.inc()


859    c.dec()


860    assert a == b


861    assert b == c


862}


863


864fn test_left_shift() {


865    for t in left_shift_test_data {


866        assert t.base.parse().left_shift(t.amount) == t.expected.parse()


867    }


868}


869


870fn test_right_shift() {


871    for t in right_shift_test_data {


872        assert t.base.parse().right_shift(t.amount) == t.expected.parse()


873    }


874}


875


876fn test_bit_len() ? {


877    for t in bit_len_test_data {


878        assert t.value.parse().bit_len() == t.expected


879    }


880}


881


882fn test_mod_inverse() ? {


883    for t in mod_inverse_test_data {


884        a := big.integer_from_string(t.value) or { panic('Could not read decimal') }


885        m := big.integer_from_string(t.modulus) or { panic('Could not read decimal') }


886        r := a.mod_inverse(m) or { panic('No multiplicative inverse in ring Z/mZ') }


887        assert (r * a) % m == big.one_int


888    }


889}


890


891fn test_isqrt() {


892    for i in 0 .. 1000 {


893        a := big.integer_from_int(i)


894        b := big.integer_from_int(i * i)


895        assert b.isqrt() == a


896    }


897    values := [


898        TestInteger(314),


899        '213149',


900        '2198614',


901        '318014',


902        '1000000000',


903        '1000131039410',


904        '2148170394871039847019843349714981',


905    ]


906    for value in values {


907        a := value.parse()


908        b := a * a


909        assert b.isqrt() == a


910    }


911


912    for t in isqrt_test_data {


913        assert t.base.parse().isqrt() == t.expected.parse()


914    }


915}


916


917fn test_bitwise_ops() {


918    a := big.integer_from_int(1).left_shift(big.digit_bits * 10)


919    b := a - big.one_int


920    assert a.bitwise_and(b) == big.zero_int


921    assert b.bitwise_xor(b) == big.zero_int


922    assert b.bitwise_or(b) == b


923    assert b.bitwise_and(b) == b


924    assert b.bitwise_not() == big.zero_int


925    assert big.three_int.neg().bitwise_com() == big.two_int


926    assert big.two_int.neg().bitwise_com() == big.one_int


927    assert big.one_int.neg().bitwise_com() == big.zero_int


928    assert big.zero_int.bitwise_com() == big.one_int.neg()


929    assert big.one_int.bitwise_com() == big.two_int.neg()


930    assert big.two_int.bitwise_com() == big.three_int.neg()


931}


932


933fn test_get_bit() {


934    x := big.integer_from_int(42)


935    assert x.get_bit(0) == false


936    assert x.get_bit(1) == true


937    assert x.get_bit(2) == false


938    assert x.get_bit(3) == true


939    assert x.get_bit(4) == false


940    assert x.get_bit(5) == true


941    assert x.get_bit(10) == false


942


943    values := ['1001001001001010010010100100100101011101001001010',


944        '1111111111111111111111111111111111111111111111111',


945        '0000000000000000000000000000000000000000010000', '1110010', '0001001']


946    for value in values {


947        a := big.integer_from_radix(value, 2) or { panic('Could not read binary') }


948        bits := []bool{len: value.len, init: value[value.len - 1 - index] == `1`}


949        for i in 0 .. value.len {


950            assert a.get_bit(i) == bits[i]


951        }


952    }


953}


954


955fn test_set_bit() {


956    mut a := big.integer_from_int(32)


957    a.set_bit(1, true)


958    assert a.int() == 34


959    a.set_bit(1, false)


960    a.set_bit(3, true)


961    assert a.int() == 40


962    a.set_bit(50, true)


963    assert a == big.one_int.left_shift(50) + big.integer_from_int(40)


964    b := a


965    a.set_bit(100, false)


966    assert a == b


967}


968


969fn test_integer_from_bytes_ignores_potential_leading_zero_bytes() {


970    bint0 := big.integer_from_int(0)


971    for j in 0 .. 10 {


972        assert bint0 == big.integer_from_bytes([]u8{len: j}, signum: 1)


973        assert bint0 == big.integer_from_bytes([]u8{len: j}, signum: 0)


974        assert bint0 == big.integer_from_bytes([]u8{len: j}, signum: -1)


975    }


976    for i in 0 .. 10 {


977        bint := big.integer_from_int(i)


978        nbint := big.integer_from_int(-i)


979        for j in 0 .. 15 {


980            mut input := []u8{len: j}


981            input << i


982            assert bint == big.integer_from_bytes(input)


983            assert bint == big.integer_from_bytes(input, signum: 1)


984            assert nbint == big.integer_from_bytes(input, signum: -1)


985        }


986    }


987}


988


989fn test_pow2_is_power_of_2() {


990    for n in 22000 .. 22010 {


991        assert big.two_int.pow(n).is_power_of_2(), 'pow2: ${n}'


992    }


993}


994


995fn test_bytes_from_bytes() {


996    input := ['0', '9999999999999999999999999999999999999', '783086277830859384',


997        '890810171456467012368983335296321559']


998    for n in input {


999        a := big.integer_from_string(n)!


1000        b, _ := a.bytes()


1001        c := big.integer_from_bytes(b)


1002        assert a.str() == c.str()


1003    }


1004}


1005