GMP compared to JAVA

[Patrick Pelissier]

I vote for (d) too:

If I change the line in the original JAVA program from
aux = aux.multiply(new BigDecimal("1024"));
to
aux = aux.multiply(new BigDecimal("1023"));

it changes the computed time from:

Bits=4815
P=1463868451165381911667460183358405388632972141347864930904885668357525216316259307716807842332588375686918685777413494559350437636703791672405242403137449414236157979789323289919248624028168420383251146931824123201595106990376561916166537224885532074415665644383936853520729731594300526725003396980693045533111524275875239690549683409188913745101540393255526220791098932519272234477464205831882364644476088225467659827496975781682516184763109450410845266157205256579563358321786053091888547911440861645622480408795859926284785067810711580646807167798604346091456749392837261564670341094847091406755007999524165024825953018611278989845427719515251984809103033999782880274863354740248851046092274169515751103539330417261684016640686580119688736907858253472713849520794107336372339198065933626058909458972772432260412790584724696087588269497579006172981912582179853594402113878741975637022033997655417273081917991959122212814023651424432761003789888035575274153139002316337345923191528277656877624291845597912265589649355022725798511533187456264439451806779948803766068933182720792268196564457428794882967004264775342220341304648587835673056410458189027592723065318747527310707526863340049685487689750767698104787780881385065552032930837682003019327088883534603384191922701533207961893063112188114636171169155849455375297541909014582142305667541842564780488070606972705929031773263226140367303413647079765796479600932651159786454179485091196456319057920
Q=2073018574415383615664425328564336255000927643463008639967446117159871371114574463501238323649124441366511022457032872442890553473086249884125866938928703817853575493756814336659431031781946648603251704308900390743772995496525121270203462445560639962025546646528920988187347597759698645165956896251115018373776611960272310912317137254193943503758934133765890023277563916576757757649819635937304205937754388682495634378995807088959048722063203228730950531316315612120123110323038101153935747797088127496592419799934061068177819592460776375656405365940816577440213746503496461808218788492862297706911220925570272469870463899085981151368801175896634766773478510076029366159476404291146361375289937236193325055616384656650079310337959332479694125605374636199360085789393117398478074684310330947847699428474289033632648842760096555510805294421428574736136025131982124936820601665837518032793524764210321548740173134689718127374935864793062741199606660555574956545125031270444506387622046651869065814925663137773635926906162526938755119831180132532744319443898049774130803460123432267351861653249762666027113346562038687847453995611115286443330829582720998537579910225421821039316943101996741141954704768087926823936644379715203550285974115261885768575255275387647525775545375683177534355185968832112453503928579899876358794967177724821420495384997743496415083428546091853274121006229133593868210406759032967237668175219121085983353314845508489022153949184
M=2856985191365970398198739116700372581917757600894774902986112307829488308737618610433632829544247185058322131683004402840819105426996574727509574339079368260001943442518490000059155613229775635376553186506628306730028516867132684245159272585719874130249559751126011170705871512877682349363312764504674625730156963736808275763108857360675635643155437211906215194034101802894721787817078128545424940897560539073814100284816188045657442432673007414481073744487449757895818844682428076985247595526866279248277542500572791453922843795544298236823864974426184294451854136495012747919438597248632602730148032325045515912239222531183181216338637748774103156170746761174288582790224993283998618310499344499305477021857390439899892369565194542237094958577933205683361638560634824912405397024344610881148314627634967454472206463132251366927738516025411452234278349196412431361811739162936203697685519042904951760620563947701840638440174769157856683332787265452041424468287336590719522676747472782017543467284513834189408890683850323115136634363553164759150466150601746538888708556027525105500551151497269959144929662635772387553757365189962622759865399456575100304669131002837757777826023368590643627094835441223284692628198192911116405525557745309905701283729138959626287052524262046309068520173933201035683484216437636334437930041587222281231748679642959081618534304858309401422318610735906608500323105794584642864447766178435771989964697124737328668588638208
R=1857314088720299927478205455982841046679579266362652535478000678013736242289287165604567755589550005255827841617025270601768309464100826414148998890711716485285432193116521984349545171055601894906137737052126618426741461349088335740668985802966623030302087661271101708233278994838579041106527738978864904863745227013802934868705569540823143289079750369107501248669759614453537783528735754862430516802525901700804262848131010609114578164715778306724767276743428768174444736930796518999101822037724397080855226933677333653879483312435535467105568315376671363152683477952664860568623635908017155687870058895902896847818479520238859224808249426022695719863435893372926430815423825378340845805755999688546879505498058923379476064699394967847092342437507074923444012803677078460169862238556746453962402587957686507134277599693109822455057357689823643267932940122812203481182616158389599574285398996713313217580354374398315602440976560142176422849414588625284449972728922897779364641430761339058365347242652527449566137999864148470009818238836330194533175014619165157179032819159163907549857826657922964102408608492013850388390188240598245245515184984851941441809455799501070080948228254432464221352089092846708722092579254233927966937844324663274850248402914245381435832414662739060619271857127127299038983269569731110947384621491437748567417337876033382552054085503158153482895794017000253917693163900962436164081727384850740507969953681136106977080901632
time=3ms

to

Bits=4815
P=1340915414275984090961803496924681471333086533535521848196778023668459619572303727900461934093146713945901818160986684949244726836364256832780540870076874893456738213124578351719454237883361424870194723222353900017805047063063230400541339485970816655011141554318715710232992117377185510004475951489691473249909317580717136328937720453934890667429797107107011545763170946790342717846881183006467351100141962437070856007359514362638427961373415345824846634340185706651269525038121636274779401588973080124105967045163853839756112436376931870615374943967249150600633547652415920751860989852647337719074668990783870597324932096731302643426920533150749937747852793726344385671532618526481448753068282320714445281632750228864031834256185392374812647286513324138725756643330402203027581039613110703385431678572532182619280624956032364327422387302213384013836098775595348856020370690990137375886197606875073361739066878499045447214501627017228329084471061253794564699920520906992674206613978463720275808565499494864649368560161254495059102614186519067553333308195236929524109985876688373232982063072076384589581062029127927576165352556140968782572064346586600634949641977185240487930447922772267690590918961217200648980538632989109312982942112511596598173036146094702290356726794413463405684647586634510200064069043336548821602501630635748110238447840394904685270978455689397749971734803755102360887566070133473585875544113129817808256011365472894215861657445
Q=1426314332070463954628095917525180431524968405855605810476243447369355036486244660997213599943766420612093765349173853436853440756303445703758938722002267911512121145362995559866491173384373116748075483338060931892591727110983541088915355541595860137149309659912562518292284124825961631207166555367157584570386766664697538645505004623907782107503103754227297498953619248566655771010196875792386711046550017910545298261567658469466018229037973828626939020527265496001506399387546646035798679244556040851169951074833512096842227410162668007842231631257513959745911285415307963132338732943352222503247100428562031455863524937185719737986778473253382420051040979254855050193972019563438351710211883754798050399876634019294560325930118314494660459054658672695139091734600493856592122643287707045861025320873839012899097879378771321690340393623426125229824387202210805377894013230187404407920569346740530991539319286554462813802730402350242026228494814682253853595402509329713833563937848984024545727044955893486402161715781157362402874100073372853284232871825069563691862111629515700085574915483660833682573962782047833646013050173944495088824738065868471273420218480884343472539998600116083549680144507143282949301741664784707744215470531865791765857186756272595939049984023252243427503851531769325430970022270001917641719471523524929019166599409921501527028771708175401844712801092914202361227033774592363586258308830077055832972947278631234231707263761
M=1613678685445083492873094910395548305783956210137034734692720497720876034682738935973856336603187764945738834851677316349528631934200517598440201233505919490302942896998020404358535035377548227847902792915228229467033515113298424101439955883342479856705105967387130711407854827204796041556100685646284192473160393812890996166285929286841078938282353117567097968261987805472367540862484306886878448029467321553141844117934816650506852918346745726573077468474136202911240755866008078303608648753480922754258945080587534523167337239491936750992824694935282815018245947440497194020831943145425120073203559292174486396162256771209038231402858557724322703204384349894878963779152533343755725397835906144547159004297017372570726048975204775224214093542209469146718079480862063531773022975464526649410922853012808719173629859671376859384401086986333856116300908236867648109873149399202123166662900832891599635317839439131446630588441629463744334118417227723368835284714244713700642679803190655012573329843937642342041422886643043407777771321891293865062919335248477046883333956299322597501277233658803753395695555031256203070955514236546135900310649069908726396473939440104839317224032789734938718766183653317804049998557983956592591232205217262324590727841404243226004249503616068795994256531412551353757785703250958125938574928074755458155552137045954590652668530551659035633669432601167139879660208529249079941721936151226124092088463404341949662931167800
R=373752593371579212285953645686248481019059062604534194419012835599512755811262818308339740116009929252360124086124772024523606109707277498799425481121948885653158917837910294133035996575637215293531931758231092470751122396282300734340963679260761294461134775964997953100144099346491832444181286738217762832308949867759717689274978074877731187634055000455238962934338232858152494632491015396524613882078585921994228701540711816367332510590754411412004950320632724340996770007320150043520293552249038853832253975767390902628885776038300595754645022128141844554501804621576151055333550387370098990316952195817523411123221087196289194382849333151689317211489435339610029301950911225842316944381264982047620650205146822335147853558983112274270976041247754490766266441232469992012855329248450095617415461149989092410875966855336658143019510910856587244514470618017079743807355015368248811745411513661861594922572048317425612500823416292273753636402259343837485356743633274062380048824367242428134965512643953189627650912152222541350278511580043470150962276796271511529867836545118651492305904866898957968023177023639100631191797070206263221049558679465810916807144692939922026502599605577755440594773614358120024338808373162819472251341797632912585914497198828014239616461307275621644894918350034861488681346075249254622377587916987992412337803112366125799871673746933729912161557836910197532457874285539253092885800635036006270950093805970196785560435325
time=7689ms

(JDK 1.6.0_03 on linux 2.6.20 / pentium M 1.7 GHz)

--
 Sincerely,
  Patrick Pelissier

On Dec 21, 2007 6:19 PM, Torbjorn Granlund <tg at swox.com> wrote:
> Paul Zimmermann wrote:
>
>   I see three possible explanations:
>
>   (a) JAVA is much more efficient than GMP
>   (b) your computer is very efficient for JAVA applications
>   (c) your JAVA exponent (q) has much less than 10005 bits
>
> Let me add:
>
>   (d) The ring is trivially factorable.
>
> GMP doesn't attempt to factor the ring, as this is seen as the task pf
> the caller.
>
> If the tested java implementation's bignum code is tailored against
> speeding up naive benchmarks, it might actually try to factor the
> ring.
>
> --
> Torbjörn
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at swox.com
> https://gmplib.org/mailman/listinfo/gmp-discuss
>