Performace de BigInteger

Programação Java
#1

Olá, estou trabalhando com números grandes, aí encontrei um caso no mínimo curioso, usando o método modPow (que realiza a operação p^q mod m) de BigInteger com dois conjuntos de números diferentes, encontrei diferenças estranhas no tempo de execução delas, onde o tempo para o conjunto de números menores é bem maior que o tempo para o conjunto de números maiores.
Mostrando o código aqui:

import java.math.BigInteger;
import java.util.Calendar;


public class TesteBig {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		BigInteger p1 = new BigInteger("1463868451165381911667460183358405388632972141347864930904885668357525216316259307716807842332588375686918685777413494559350437636703791672405242403137449414236157979789323289919248624028168420383251146931824123201595106990376561916166537224885532074415665644383936853520729731594300526725003396980693045533111524275875239690549683409188913745101540393255526220791098932519272234477464205831882364644476088225467659827496975781682516184763109450410845266157205256579563358321786053091888547911440861645622480408795859926284785067810711580646807167798604346091456749392837261564670341094847091406755007999524165024825953018611278989845427719515251984809103033999782880274863354740248851046092274169515751103539330417261684016640686580119688736907858253472713849520794107336372339198065933626058909458972772432260412790584724696087588269497579006172981912582179853594402113878741975637022033997655417273081917991959122212814023651424432761003789888035575274153139002316337345923191528277656877624291845597912265589649355022725798511533187456264439451806779948803766068933182720792268196564457428794882967004264775342220341304648587835673056410458189027592723065318747527310707526863340049685487689750767698104787780881385065552032930837682003019327088883534603384191922701533207961893063112188114636171169155849455375297541909014582142305667541842564780488070606972705929031773263226140367303413647079765796479600932651159786454179485091196456319057920");
		BigInteger q1 = new BigInteger("2073018574415383615664425328564336255000927643463008639967446117159871371114574463501238323649124441366511022457032872442890553473086249884125866938928703817853575493756814336659431031781946648603251704308900390743772995496525121270203462445560639962025546646528920988187347597759698645165956896251115018373776611960272310912317137254193943503758934133765890023277563916576757757649819635937304205937754388682495634378995807088959048722063203228730950531316315612120123110323038101153935747797088127496592419799934061068177819592460776375656405365940816577440213746503496461808218788492862297706911220925570272469870463899085981151368801175896634766773478510076029366159476404291146361375289937236193325055616384656650079310337959332479694125605374636199360085789393117398478074684310330947847699428474289033632648842760096555510805294421428574736136025131982124936820601665837518032793524764210321548740173134689718127374935864793062741199606660555574956545125031270444506387622046651869065814925663137773635926906162526938755119831180132532744319443898049774130803460123432267351861653249762666027113346562038687847453995611115286443330829582720998537579910225421821039316943101996741141954704768087926823936644379715203550285974115261885768575255275387647525775545375683177534355185968832112453503928579899876358794967177724821420495384997743496415083428546091853274121006229133593868210406759032967237668175219121085983353314845508489022153949184");
		BigInteger m1 = new BigInteger("2856985191365970398198739116700372581917757600894774902986112307829488308737618610433632829544247185058322131683004402840819105426996574727509574339079368260001943442518490000059155613229775635376553186506628306730028516867132684245159272585719874130249559751126011170705871512877682349363312764504674625730156963736808275763108857360675635643155437211906215194034101802894721787817078128545424940897560539073814100284816188045657442432673007414481073744487449757895818844682428076985247595526866279248277542500572791453922843795544298236823864974426184294451854136495012747919438597248632602730148032325045515912239222531183181216338637748774103156170746761174288582790224993283998618310499344499305477021857390439899892369565194542237094958577933205683361638560634824912405397024344610881148314627634967454472206463132251366927738516025411452234278349196412431361811739162936203697685519042904951760620563947701840638440174769157856683332787265452041424468287336590719522676747472782017543467284513834189408890683850323115136634363553164759150466150601746538888708556027525105500551151497269959144929662635772387553757365189962622759865399456575100304669131002837757777826023368590643627094835441223284692628198192911116405525557745309905701283729138959626287052524262046309068520173933201035683484216437636334437930041587222281231748679642959081618534304858309401422318610735906608500323105794584642864447766178435771989964697124737328668588638208");
		long t1 = Calendar.getInstance().getTimeInMillis();
		BigInteger r1 = p1.modPow(q1, m1);
		long t2 = Calendar.getInstance().getTimeInMillis();
		System.out.println("Resultado 1: "+(t2 - t1));
		
		BigInteger p2 = new BigInteger("1340915414275984090961803496924681471333086533535521848196778023668459619572303727900461934093146713945901818160986684949244726836364256832780540870076874893456738213124578351719454237883361424870194723222353900017805047063063230400541339485970816655011141554318715710232992117377185510004475951489691473249909317580717136328937720453934890667429797107107011545763170946790342717846881183006467351100141962437070856007359514362638427961373415345824846634340185706651269525038121636274779401588973080124105967045163853839756112436376931870615374943967249150600633547652415920751860989852647337719074668990783870597324932096731302643426920533150749937747852793726344385671532618526481448753068282320714445281632750228864031834256185392374812647286513324138725756643330402203027581039613110703385431678572532182619280624956032364327422387302213384013836098775595348856020370690990137375886197606875073361739066878499045447214501627017228329084471061253794564699920520906992674206613978463720275808565499494864649368560161254495059102614186519067553333308195236929524109985876688373232982063072076384589581062029127927576165352556140968782572064346586600634949641977185240487930447922772267690590918961217200648980538632989109312982942112511596598173036146094702290356726794413463405684647586634510200064069043336548821602501630635748110238447840394904685270978455689397749971734803755102360887566070133473585875544113129817808256011365472894215861657445");
		BigInteger q2 = new BigInteger("1426314332070463954628095917525180431524968405855605810476243447369355036486244660997213599943766420612093765349173853436853440756303445703758938722002267911512121145362995559866491173384373116748075483338060931892591727110983541088915355541595860137149309659912562518292284124825961631207166555367157584570386766664697538645505004623907782107503103754227297498953619248566655771010196875792386711046550017910545298261567658469466018229037973828626939020527265496001506399387546646035798679244556040851169951074833512096842227410162668007842231631257513959745911285415307963132338732943352222503247100428562031455863524937185719737986778473253382420051040979254855050193972019563438351710211883754798050399876634019294560325930118314494660459054658672695139091734600493856592122643287707045861025320873839012899097879378771321690340393623426125229824387202210805377894013230187404407920569346740530991539319286554462813802730402350242026228494814682253853595402509329713833563937848984024545727044955893486402161715781157362402874100073372853284232871825069563691862111629515700085574915483660833682573962782047833646013050173944495088824738065868471273420218480884343472539998600116083549680144507143282949301741664784707744215470531865791765857186756272595939049984023252243427503851531769325430970022270001917641719471523524929019166599409921501527028771708175401844712801092914202361227033774592363586258308830077055832972947278631234231707263761");
		BigInteger m2 = new BigInteger("1613678685445083492873094910395548305783956210137034734692720497720876034682738935973856336603187764945738834851677316349528631934200517598440201233505919490302942896998020404358535035377548227847902792915228229467033515113298424101439955883342479856705105967387130711407854827204796041556100685646284192473160393812890996166285929286841078938282353117567097968261987805472367540862484306886878448029467321553141844117934816650506852918346745726573077468474136202911240755866008078303608648753480922754258945080587534523167337239491936750992824694935282815018245947440497194020831943145425120073203559292174486396162256771209038231402858557724322703204384349894878963779152533343755725397835906144547159004297017372570726048975204775224214093542209469146718079480862063531773022975464526649410922853012808719173629859671376859384401086986333856116300908236867648109873149399202123166662900832891599635317839439131446630588441629463744334118417227723368835284714244713700642679803190655012573329843937642342041422886643043407777771321891293865062919335248477046883333956299322597501277233658803753395695555031256203070955514236546135900310649069908726396473939440104839317224032789734938718766183653317804049998557983956592591232205217262324590727841404243226004249503616068795994256531412551353757785703250958125938574928074755458155552137045954590652668530551659035633669432601167139879660208529249079941721936151226124092088463404341949662931167800");
		t1 = Calendar.getInstance().getTimeInMillis();
		BigInteger r2 = p2.modPow(q2, m2);
		t2 = Calendar.getInstance().getTimeInMillis();
		System.out.println("Resultado 2: "+(t2 - t1));
		
		//preguica de verificar que os numeros da classe 1 sao maiores que os numeros da classe 2 no "olho" =P
		System.out.println("p1 eh maior que p2? "+(p1.compareTo(p2)>0));
		System.out.println("q1 eh maior que q2? "+(q1.compareTo(q2)>0));
		System.out.println("m1 eh maior que m2? "+(m1.compareTo(m2)>0));

	}

}

Resultado rodando em um pentium 4 3.06, 512 de RAM, windows, Java 1.6:
Resultado 1: 31
Resultado 2: 3281
p1 eh maior que p2? true
q1 eh maior que q2? true
m1 eh maior que m2? true

Por que isso ocorre?
Seria algum algoritmo interno de BigInteger que só funciona bem para certas classes de números, e por coincidência eu peguei uma delas? Se for, alguem sabe como funciona esse algoritmo?

Muito obrigado!

#2

…

#3

Não de up em tópicos, não é de bom tom.

Quanto ao seu problema. Primeiro que os números são de mesma grandesa, a diferença é muito pequena para os números do teu exemplo.

O jdk da sun usa uma versão parecida do algoritmo de janela do Colin Plumb, que pode ter tempo de execução bem diferentes para entradas do mesmo tamanho. Outro ponto é teus módulios são pares e o número de bits inferiores que são zero tem relação quase que direta com o tempo de exeção do algorítmo. Não me dei ao trabalho de verificar quantos são, mas isso explica parte da diferença.

Se você realmente precisa trabalhar com APM eficiente, sugiro que escreva um binding para a GMP e use no lugar de BigInteger.

#4

Olá. No caso, desculpe-me ter upado o tópico, é porque ele estava já na segunda página, ia ficar no esquecimento, aí preferi upar esse tópico que criar outro…
Bem, a questão da minha dúvida era que com algoritmos semelhantes, os meus resultados com java estavam saindo muito melhores que os de GMP, aí de repente encontro esses casos de teste em que o tempo é muito maior que os tempos que eu estava obtendo, e resolvi perguntar. No caso, você me atentou para o fato de os números serem pares, realmente, quando peguei meu código e pedi pra imprimir os números que eu estou gerando (estou gerando números aleatórios), eles, a partir de um determinado momento logo após o inicio da execução, só gera números pares (eu coloquei pra imprimir várias vezes para não tirar conclusões precipitadas…).

No caso, a geração de números aleatórios é feita nessa linha pra cada p, q e m

aleatorio = (new BigDecimal(Math.random()).multiply(aux)).add(aux);

Onde aleatorio é um BigDecimal (eu pego a parte inteira dele transformando-o em BigInteger), e aux é um BigDecimal que cresce a cada laço na potência de 2 (16, 32, 64, etc…), e o laço vai de 5 a 25000.

#5

O GMP chega a ser 3x mais rápido que BigInteger se você realizar muitas contas. Coisas até que simples, como resolver uma equação do segundo grau é muito mais eficiente com GMP pois é feito muito menos alocação. O fato de mpz_t ser mutavel facilita muita coisa.

#6