README.md

Blogpost is hosted here:

http://donaldh.wtf/2018/09/a-twist-to-the-rational-story/

rational-twist.org

A Twist To The Rational Story

As a followup to brrt’s Curious Benchmark post, I wanted to explore some of the questions that were left unanswered.

A Reminder

This is the benchmark that we started with.

# reciprocal.pl
my $x = 0;
$x += 1/$_ for 1..50_000_000;
print "$x\n";
say "Took {now - BEGIN now} seconds";

18.304749238293297
Took 37.44224442 seconds

I ran this on a Perl 6 with all the nice MoarVM postrelease-opts performance improvements. Even still, it takes its leisurely time to complete the 50M iterations. In the samples below I am going to use a far smaller range, for reasons that will become clear.

Enforcing the Rat Type

Firstly, what happens if we require $x to be a Rat?

my Rat $x = 0.Rat;
$x += 1/$_ for 1..50_000;
say $x;
CATCH { default { .say } }

Type check failed in assignment to $x; expected Rat but got Num (4.437963841730785e0)
  in sub  at EVAL_0 line 4
  in block <unit> at EVAL_0 line 7
  in block <unit> at -e line 1

That’s a surprise! Partway through execution, the Rat must overflow and get promoted to a Num – or is that demoted?

Let’s Try FatRat

Okay, so Rat wasn’t big enough so let’s try a FatRat instead.

my FatRat $x = 0.FatRat;
$x += 1/$_ for 1..50_000;
say $x;
say "Took {now - BEGIN now} seconds";

11.39700394927848263794723724204579293271830505742186834750693578144465183531290496913748510727570775070058686438785753373472816524003689477778418417449218342586002887149134757360258497418431668625047881023241923443605684025701592626446377998766294011642454781091728212201574721432415046263777496948540914639958507450091241565616210098690370499110808738567858930441605773678975300621854275794569259805492076847896257824136227606259608083311775632944471689981909846078048753336947544753235041376792210867534316336359608587161871857798597055555519583606612618969324454220094510617208906186054144002433098900027526628875443569926253281889469311244526731099881809629716366488870204296571934907364565903448441703210061775623159445180430546074238003671788828939795588581849420278384803427057743552336323978179752533086538267918726735101334213611544536109504560343938607417727597869643305220479063875777090858806933853320874828221870304360786296651556740286778637508577406915634652698237985188152827668086907259693198257769563699368257325100905228699895267214996084361795519563787845603768495022019192493939116749921323325065261318310776357786493115895046275736693430031331278351091701698414765858371880629889559569877555499739898083149192356947926517021772251418947236808568105154087725571392196529318733728638123288386793295308180583027233855446520603238343984421733536374255149003435809099540819109947751893497364132734081056718362776207394531439607391418243164533991436116747797931485021349632885309531609895887801693074174469791283964664881778551024712372504778476625207432884862077599040828975864600356477807590194007479989663099556596846181287130594238331732748024212515581435219988069678563942060556523698559844461660883628222086790352656961983096480796268587048236025708130749103679025760105337667432874024152301375646400264599439353058130789490186159699713450038230732807381990836146317184342542464515615797537928044431704513697142312490054429012581368967225154099591941153570622805559133774313386540902168223221384740595168428666045552985758070056248838506028320321298918969440135708239757484479017219955415360425183740787901723167988687444602433649913644519211816423944275673657207918193049120335301526482954680161022766264453348674076769854973383447403661090017722977169915469707714296175098986883552558356212713658530130214515446231323039476924084367464869959747859744904954583569234123637016083103603211402615320916183022334244349275203764693871690743892300829913475421847049443587069954503966956288924852441268806129632250765264140255186286402807483536245991372492976343595172116534101447617908201199277654558640040905299496333861103019970143388090079572632448317771481944602644573464763559125843619522933451163921750677075000204832323237690185492945906556357560482781574625426701770627246033246108863282371096031642354524330671750186519245099938369784790978864446263141189902485687535931950571063083733163313085852312112175815172028103292793871467684956446205828328818709544952000456562191915522353683009980555451352322990207643332661306477139104850363616220208299461238837582125838650534135295786152817364839142852203887972141114465379520808171357977982021917413580239474674391308622740461106272504013210228445088743765311752245080145294035645680616868883049619884594718629675836376792044910855295027129328032653699008651799440701461166934292259325838576414180464170285282741585320913031737214365307592226129680335738267521186056376121931712130816268802890479370802581847440657588952701299985538841054638820598846594644521413707675283997278317462421922650156006794594876879462297625488000168773023215281317727597329901562669268954501990933068761341719485582315864405509406356152534063764698287347268732627511094493371621209775884235788916800899363132042029294750959831318237752963894312372159896249138837226157093354800498686854694875692465037184386256304812124087768155086337119555735388714665990532625553972308110792543436107946959891122994705631830446103604823422997310888461319243112385692393055332277420581486796081519472377123093942437471687125619157650577676808703042376369567567994491810889517763459862953187712052796686627509800755740412220060569808811694235598746254990342473448283762262837550092952047100867726394278452124067102105854212445061473521239268116585804916830975612048314714918017119482432062639800566437337791979082506317410266375722026482902153131100240433362934924561788354328509378711757835779086667519989060894790630039997644788410032666026185542946719919393742191769550322155038187228150583043519130967649547742472715498660584345037616705586696448972855290107113055268501991880233369641312556839034994486234121014120530745474335735467471930914270337338922492941868006244772177589360315359417757428130667659853284801731653635600273622322459353692885215398077819055234769547403456816608950374852567155759331288709067407762394287492268773694850894936304455553236760029174614418930038846531093007830280521444946224936426750872819728742029619056706576019398899663478884959762435429656019089332244111269697829285822753109081449831877592362167024920600005451729898640865389565452135857154038083256040234937583901585749983037632331246285239896400641200856216031502891498650845783089831059977306685386259894222143888925953884622921384885828217294685105368836108379804390472055510441999142780779171743825474315018832100239339671769588659055435792011380935799317509813544570871202699709977079358546111698304804120132272844815433878612051156753733036897476035954292969560405934625911179759272213859652894908546983123396745432989042150338347370230334864425458251960824871822499903224858922695709426328844413465837976005947616034416533044696045359556817954212311259562249867373394261241123438248288595467478413376868957525422381591368648346620151661404624519718731755342440719228425180055133975147235037465893892013114179745112208793761179743165677057746205932526518157850611343244251404845161069369549902322841859359807007661449120546405840828272559602348914318530985507829867204680035040795402492939346448285159212465762987164755289315258236713053690297998556585008657584108044586459247365507459413037838742547715678976850958978465634188923097931934922315811138999540367509192322933254127159964717241368036800576672763356322048209811500198175143302929712178702997634278846463261305105794606003672032873041973443675965974969813473823905078554729061002342949876379278834851940871252447003783816164063167955638824090828667186835133580836681192559376693108672426890889857372140145629125577809563320890376015893658306014138689151872673962941348782914099957808529632234251281233242257467411551883018527632773866891538078256116988316573092725993253950732432376152038206793931040913287360001065901568459745250860324091088639756759023413909020227803146304429507889635024493826483662146487185561803980992254733475784472376518813126938556340778537880464280555045942183964100092236114867026061621665876693080482338318903860549184484579295080291788271339121530200803581965605138787620220467309408508498465549437714396935675754253972131881032253204431207450560196674378373702563627999019879657565066471175999389387734044666157216911915172226261949089417649211551843539649475474005518038126450956624430019233595628106048576012794415305792441460080643598534397842570358674480726745934140492148045061018487905030273299747486593723889535713604247897432853210532576850495672048513306297002351268394572946506052879305121927867382522749191914884734632963984823079288057988824723606305712490219346373741015894853371482314479371001115003226717996359242543272337582570448617745480895689402752936075915518561261416195317418357297896277952066729678803070485373550971308029728696321417415944701287898941230409129630589216927457520031117726363871061782184361874765411244564796001078854060732377557198997391289962030144586792824406645531162648352744528118203716227954604736407223893788772966852247258874028986549172135814379510784482040098535290614212538922203724364919583211719024834654995140174090233553469416450791301429776809804014895238836276182421012143163995883264036952008295344191149147816181708300645766895832810017485252793270113022921063044301320695561366321667523526880148898865612859915758167932947700987056094198562032785768609677316897056131446882421343892357641812682942209570320016551838018189399170797807781229947901138261819708412925127731438146156314270912238735011742876128824535384783129781195975212394901454086023546540478864185696276170734632855819515611665553698785248472389155946710197317086452106978853361054976086882908661157946774066095528831659000190497414827219724971583809170853615595033405589785744775865613524456842978090270859425001920215575409704211135148774336683208256523167082406563909755831697211783497906697104335809374645779497573342635862876182304453697603122889357954281933027312267158651093393153308464397653592774767132458954101355662721672374116691072283642268488321259065809538282437903925644125904300683883310614541716471724826392361216841005404462303384453287962837086802454072901499320431169289272852303878919375327433609584377050726136937588964712072287819796682860072692828449255161688401203535222607495782984685159810559309309212253173631951175507986235266965480172184512407788436076800420841216609450835376142146981134392745352922684987457782717135637017547192019243821223873685070557193724574775868974620973526671435393827670048466371031308823506473605922748695639393635291074562203655411686833086365044825027230788193279893979559959096731882020113778192025473595398197995443603207989203351378084431023894779342793717463259845555265411611178800733867290178512595351841308626448616174445449480604175029059681209897052754035009791474957198626998686502055571033733316725207218702848848714834028275238884032018587664740247569256961374503982622455728545780391695491073572498808564189003215613365386204469507516614637366820703384202355643476291242811666753340913035027823632694921744631239998897375082927154230370031202486588348386683122502163905031080084734497424678553527214955787717141220698473349911754286757100504510727862319563195870616390661471338720000755526395889857052750720053756490247571883465185886160012368848262373205901799649634496657116336545799122395438596438700173850952277247276707496025254611392578979767988734463473596611650823926649134666664740731465888578527003555623993976617494088363748522170558094539148513957057465291359160779447683295807674777213114833996792835078417928879220652895517830606456370022021755574034298416190273889505525847804284909935450824110674789766820615963815649722679706100269780614067798546438096995020175776609788981278036128556942957710664451174711002202463978740431449181279671801127308833583804110377512770594506453322907882823371607643163729286308538854392483523355743670480084953534587114140848736945550621727815997323869020066650984410732819686931704588670680094700819179677228193463608197702295306748850035182264443764259650417135283508905743361762913040973591885371137010076931412173734934570483143622874651718601076006802544657682809954888186102234461639171011700786619508663327395970672251712232363346634402777831593191018229869120355193449916329012298926557795907167374097042131056832664788782329778303517393605654291230776617939074624186238135765583917264263153537105510251807171590142953815442805515931796347159537597491026911480412568203862361617907220425505110545116411514048519194715083625022062894234317528318913264465290246417449856151534210222439887374942326798846393362428367862502684528825580778694863912001922461242813277788790109276857431783670866353841495073062892207528946378367395992267794504948259760653545180617301147926620565020801202534955265553351781123474808345681394466038643313566256980912358745939513790527626751533397420877356414779546621123128680251453637510257803735627042866582000330991694814377851005544300604060914783983372835385000176839424869529109125560760903374405790431962415582569995688300375676704353313169102512458682923971946504718103515524863156774227493067017924778995193036612699306924975099637112779128320515106469391848831363714651936692817190651136428764748289550304524413901513546881517331961623880156342624938933635525348890755594292253188306104677963403052859983365244541275616967205100253388280787616338373677788711833904297275613956224234591921303250752275358709166858802468611073995008362237529774264982020302922050524938642308056156537158592345468013433735567111147506154730273921892871743820276080963075928098073190891028526161113718801513409753311063922385410909917842459093526427761381966609003880447342229236023538841861590307965221440788828321918500255864252987637633238140167162862571546374684725239206996114852885402173486350752715168502363948930648322961956883050858033610965655178526278821387318539758107659293234401780672834683670735957548948762737887125653147702272250788192599849271883837410318819425136148969871759772078242895614566296610807078425254897364942620114575830014732786879234381406310667442978511493065990505382406757352448928550744534514914038890087771131249051698209231636042814282436989104813019136811506315678619612000423456360679110554742593610906285035670354911455199266515397278304196573468338373752793248691997243361808710140646890441390026869634534885539093008067364324089165437119927688262118726194616385784164388471667194133783097240104685517292393582693602682988186751449313927309499765726959883636530124979327559475833534984072344776111465110776328513968327012119437120193220340160284828472785003706347532678953879756123203070153547788593399954445060413920916093876403444854033076276751999198395528746442478198050223599602953236156120662570459716657501865108796169939970378631802999953747930184625088899500218236313179241628066609378316539967036070075887260348024633162257816628546262736643199077818623879713558995227375406513900784180459799551488500693780025116437566242961322475469230962156513352314774068487278897908340411560823231316584678953667817304188597584711045065280538906970439024415484730128715567481093616988754669739342356046167192176271920594014187901204340681302565100296295965850782679614602900791561620044769211372779838294244897181001357000045174849961019953681804195855091758953243059781846898807555708691954457641104433460455196864004317858224277788256097368592868548639971565280944821791565049822800619461555603965571571351770347764779741265171443550673622064499083347278912193770027232205044181518635931922908420564959484515916493912310575577263024832062933150097310654456940475048538219683938984265197399311139870758582960209229572984214859824308907965699590163492014159842850858917020547428596761112803858253167300567932189072689550471998044651355085875235894375291179304024323428894291213419178823958991473474753594555255031843264117771694500432147674782964546762409853746651544187348218674273927761240619502778366575673716049051196918337049090453384497606457486823071288859726696070948047490832895941477925218059545919483653059409910449397504803667680699222070212199112233603744875407585144094242876446821443427564367174239672087539089397863377115792485634814056464638678044911477330769524451570075905510766866371443751452436778708137070784564837832384837494464963480478126593630971539931766019911441106205809359349208583955867659688770217362709349583061072637753704767956788860206565567338767307341847595654420732504113354855918463520981571208723518848389538998445392884511792160451789406463581994608172839019438201318131257236468862053857731229600601331203968474387139126487941949078134819146075878224655306686179488645962109077649294345270388236688801925459034393269639918462720468743768012465251500194007423227820799864403209739621257597168045229082906682689017597922987193442003678851374891809450419898425574321624643291120381558546815922509304145859134567389488436918749128662372509637077597428697507118275770103553886771427542777280464080265811852772865552748971705142196224084520965765443499060883972599967067208873785057616254768245045175768511840838057656479578610669014685076693385594863998065230925225897273427030437245863792745238426103693277322024709492805286250680186233571985411394239003091825964070309579967292408771952817954487513595563656666799882820860269961441396544089329751023082656908917638107285659089721542200931253708573000833173167061045812300817170616200732269819222431128460969602717482201395231845427963999625643901287576483957384534636163423749427448042601302897768908651487565782316946721772126129173284014848611283136708909335972775474731624823738025090698002042424547301231242691267079768448853207449414813381017164719376659871713560166005215721249227070307666223535876913647233402442348272144184441061029546715633282293378342607688746640219693633723077006528876557406888633233142222262060768865085751018390714876080025270097171610409803508457083811798262732004988904694345513297626788404119659149770460396270190906052570391613386017017049024766736084425737876565335042972709314978850104113978779976336409549487239886260180557522375657422470617686569967251443709903649163601434278660189797469566860292147659019273626132402411828710166873532475722745430858559686654351775467864897906238936240229339487376679083265798578264497198395322676610671776499389151467888166233354407827709301946273279580513081992296425752982312669446694309327022667388032748400304056803812578353600103933126102332245905535494964219084415520808270988075832912970955069217796634600894736740353481595498679037491225141810170219189952977900057830104388762356166317033851340478413816507333708728574768645471850056524130881758143532933446843444313821665189328746661954104470773688694394376975148121498028304549805105764082804381743944902569076620495434835541279699627815641133769953452519073353688168438725146919401607933983099910590829944421973722436987174323512982560278472882576280075082263395686260697929287176587449231596052547099780652671600934752304764409340205500288418902243792890237998457353615455707803060704863652998032987255717533596925209863772742258673068169613781637864031179787497993101171222461672161524585125616209867578178771152386281571394776643272088412543322925781708071681795612113844051457285765494378375515097122255142507232109828285106553688266048308523156171254918147301103424145951908451384365828590565993314036683791401130389015692369700972413830474975980321694492767229270882327121637096367885989074006607737339786598406586184755993097426084552424262728083752865927297183551616571612651013437521189443617125479226001759378576820244433994853224733964412696832879312537549987263722256459826496540841943111414565573060042616725611101895021686121866534267849174131576001733481506152140292569221126919125942558900126032481693638677065805099406807377921111785818132689907063914165919593467286175393293515872454668337249707672111964506073374256609328550791942470839191650345987382972973237274407923838607557408799845865424006798459524709410885954617194345889298694194426771746430320032373015036539611088730375142997420687999414790908020824554696801506921222312742303173751051506808504539661845479646002355864657839514241051733686034223855288407988663066085936812316373159077274043342632048607850832486942643500868088580081051018691876588864866136380649433109197913402070937943407871545899674174731222739746980484448732152552326651359332354087463357439012864019868086306598852203213964911543261345195926371694766494275935950964768273637832016466547567178722021664014325605483456324683107297513209835844913552683538041520144074935164772443277103431832930987245680197033734255832523492347494630669313322568386150567238239964816884545996679635704083842214058100823283900869189527409150917695178750261058168771449360404619134935228376000786166821884410673881716943362934317621342858870379717260189094369853277124631490534519937253016592737434295429284847378119145771145798352751476187871803519099322498857967222728663266766014453193455872832121268605622446362308508102079756022214210152017696428452294625585858786932889906112310799243780637921567040442080170531267093169017447194208311534181229609067901402484767307157487664383525426851334835249111325031724540548958580758861500426431647457835251401217734886647375384581114583920867272033796293415635766301403286123659176683203905775372186601951762168183703715892827249379297192984205333636722917253146890207737527893935263547790757406704443961932642778168178277278245718464587933850248421925604646861101963059707188831735741793034169250031037820729656029073854702411046981289125998796083001313565977866831740367077158247241215437229471933235528764351816040797770376829813377326212179908862818418137588072104785033252745593399413360299716654920022660972684891295174237582661300067511256239587592390729077495886818005094787672006561217668947856605919487216441346041749895223596428734195786098851413232477133020319881286637705830012132826010997810702183410574988682291813634874821978536424825831533522361302790031344161183819183449518361492719459133491447017368212705386587515600336416676372792801360028609862543825235384681408347985719579543952665022460615866282332725281523619541593271884051200000317442208903985804217668508563799176999968151775538825593688606747816732352823609149574904765128046209615202081236740186950730684271167206341192106319015025496794755766170223606281954261185114069080910993094893417788373970042475343130398110656868534783392806497366567408855309139927571437349284365375039397207728221882605691056888401754794113534209793831576017601109573482739349883615746023457152419167015926398742499239329813505806838224832608650992726421551596229067346240000846149173244205168114204426365846776797436941341177419627623937005217620919351017425725474521296220333349118088652193888387411292685958
Took 767.158196 seconds

There are two things to note here. Firstly, the precision of the result is far greater. Secondly, it runs like treacle. It’s taken nearly 13 min for just 50K iterations. You’re welcome to try a 500K or more, but the run time deteriorates non-linearly.

Reducing Hyper Fun

Okay, that was interesting. And we’ve uncovered just how slow Rat and FatRat are just now. But questions. What would be a more idiomatic way to write this in Perl 6?

say [+] [1..50_000] »**» -1;
say "Took {now - BEGIN now} seconds";

11.397003949278504
Took 0.32804122 seconds

That was pretty slick. Why not run it for more iterations, I hear you ask.

say [+] [1..500_000] »**» -1;
CATCH { default { .say } }

Too many arguments in flattening array.
  in sub  at EVAL_0 line 3
  in block <unit> at EVAL_0 line 5
  in block <unit> at -e line 1

Sadface. I’m not sure why this flattens before the reduce operator.

It’s a Race

Could we speed things up a bit with a .race? Yes we can!

say [+] [1..50_000].race.map(1 / *);
say "Took {now - BEGIN now} seconds";

11.397003949278504
Took 0.2375065 seconds

The sequence of FatRat's can be generated fairly quickly, but the reduce operation is quite slow when the denominators get large. Trying to race the map portion isn't that effective at speedup. I tried partitioning the FatRat lists (pretty much classic map/reduce) to get about a 6-fold speedup.
FatRat's may be relatively slow, but this benchmark compounds it by doing most of the additions on large-denominator rationals. The precision is pretty incredible, though. :-)

{
    my $p = (1...50_000).classify( * % 8 ).values.map: { .map({ FatRat.new(1, $_) }) };
    say "Map Took ", (now - ENTER now), " seconds";
    {
        my FatRat $x = [+] $p.map( { [+] $_ } );
        say "Reduce Took ", (now - ENTER now), " seconds";
        {
            say $x;
            say "Print Took ", (now - ENTER now), " seconds";
        }
    }
}
# Map Took 0.8337299 seconds
# Reduce Took 250.31103172 seconds
# 11.3970039492784826379472372420457929327183050574218683475069357814446518353129049691374851072757077507...
# Print Took 1.89496162 seconds

Time on the original script with my slow machine (but running 2018.08) was 1585 seconds.

{
    # create the FatRats
    my $a = (1..50_000).race.map: -> $_ --> FatRat:D {FatRat.new: 1, $_};

    # sum them up 1,000 at a time
    my $b = $a.rotor(1_000, :partial).race(:batch(1)).map: *.sum;

    my FatRat $x = $b.sum;

    say "Took ", (now - ENTER now), " seconds";
    {
        say $x;
        say "Took ", (now - ENTER now), " seconds";
    }
}

Took 11.438193 seconds
11.397003949278482637947237242045792932718305057421868347506935781444651835312904969137485107275707750700…
Took 1.7931441 seconds

Note that $a and $b run concurrently, starting when $b.sum is called.