GMP compared to JAVA
Nustenil Segundo
nustenilsegundo at gmail.com
Sat Dec 22 16:51:27 CET 2007
Hi,
The architecture of the my computer is 3,06GHz, 512MB with GCC.
The algorithms aren't exactly, but they do the same operation. For
each loop, the auxiliar variables (exp in C and aux in JAVA) are
multiplying to 2^10 (1024), the difference is that exp is calculate in
a loop, and aux is multiplying directly for 1024.
But the time that I want to calculate is the same for both:
ini = clock();
mpz_powm (x, op1, op2, mod);
fim = clock();
temp = fim - ini;
long tempoInicial = Calendar.getInstance().getTimeInMillis();
BigInteger calculo = p.modPow(q, m);
long tempoFinal = Calendar.getInstance().getTimeInMillis();
return tempoFinal - tempoInicial;
Can I optimizing GMP for this will be same JAVA?
2007/12/21, Julien CLEMENT <julien.clement at loria.fr>:
> On which architecture are you running those programs ?
> I tried them on my 3GHz Dual Core machine with GCC, and got the
> following bench
>
> Java version: 2 minutes 37 seconds
> C version (no optimization flags) I'm still waiting for the program
> to stop ( > 10 minutes)
>
> Are you sure you're using exactly the same algorithm for both
> implementations ?
> I see that the C version have a nested loop for calculating 2^exp, while
> the Java version doesn't. Such
> a nested loop is very costly as "i" grows.
>
> Also, in the Java version you have a multiplication of "aux" by 1024 and
> I couldn't find an equivalent
> in the C version.
>
> Am I missing something ?
>
> Regards
>
> Nustenil Segundo a écrit :
> > Hi,
> >
> > I did a aplication with GMP and other same in JAVA.
> > This aplication calculates the value of the operation a^b mod m, for
> > a, b and m randomical numbers of n bits, n in interval [5, 25000).
> >
> > The code in C (using GMP):
> >
> > #include <gmp.h>
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <time.h>
> >
> >
> > int main()
> > {
> > //Declaração de variáveis
> > mpz_t op1, op2, mod, x, aux, exp;
> > gmp_randstate_t state;
> > unsigned long int n = 4, seed, i, j;
> > clock_t ini, fim, temp;
> > FILE *p;
> >
> > srand(time(NULL));
> >
> > //inicialização das variáveis do tipo GMP
> > mpz_init(op2);
> > mpz_init(x);
> > mpz_init(op1);
> > mpz_init(mod);
> > mpz_init(aux);
> > mpz_init(exp);
> > gmp_randinit_default(state);
> > //abre o arquivo "arquivo.txt" para escrita
> > p = fopen("arquivomassa.txt", "w");
> >
> > //laço para medir os bits e o tempo
> > for(i=5 ; i<25000; i+=10){
> >
> > mpz_init_set_ui (exp, 1);
> > seed= rand();
> > gmp_randseed_ui (state,seed);
> > //laço para o cálculo de 2^exp
> > for(j=1; j<=i; j++){
> > mpz_mul_ui(exp, exp, 2);
> > }
> >
> > mpz_urandomb(aux, state, i); //aux Ã(c) um número
> > aleatório de 0 a 2^i-1
> > mpz_add (op1, aux, exp); //op1 Ã(c) um número de (i+1) bits
> >
> > mpz_urandomb(aux, state, i); //aux Ã(c) um número
> > aleatório de 0 a 2^i-1
> > mpz_add (op2, aux, exp); //op2 Ã(c) um número de (i+1) bits
> >
> > mpz_urandomb(aux, state, i); //aux Ã(c) um número
> > aleatório de 0 a 2^i-1
> > mpz_add (mod, aux, exp); //mod Ã(c) um número de (i+1) bits
> >
> > //calcula o tempo de [((op1)^(p2)) mod (mod)] e armazena em temp
> > ini = clock();
> > mpz_powm (x, op1, op2, mod);
> > fim = clock();
> > temp = fim - ini;
> >
> > printf("%lu\n", 1000*(unsigned long) temp/CLOCKS_PER_SEC);
> > //armazena em arquivo.txt a quantidade de bits e o tempo
> > da operação
> > fprintf(p, "%lu\t%lu\n", i+1, 1000*(unsigned
> > long)temp/CLOCKS_PER_SEC);
> > }
> >
> > gmp_randclear (state);
> > mpz_clear (op1);
> > mpz_clear (op2);
> > mpz_clear (mod);
> > mpz_clear (x);
> > mpz_clear (aux);
> > mpz_clear (exp);
> >
> >
> > return 0;
> > }
> >
> > The code in JAVA:
> >
> > import java.io.IOException ;
> > import java.io.RandomAccessFile;
> > import java.math.BigDecimal;
> > import java.math.BigInteger;
> > import java.util.Calendar;
> >
> >
> >
> > public class Big {
> >
> > /**
> > * @param args
> > * @throws IOException
> > */
> > public static void main(String[] args) throws IOException {
> > // String saida = "";
> > BigDecimal aux = new BigDecimal("16");
> > // BigDecimal condicaoParada = new BigDecimal("10").pow(1000);
> > long cont = 5;
> > String fimDeLinha = System.getProperty(" line.separator");
> > RandomAccessFile arquivo = new RandomAccessFile("tabela.txt","rw");
> > while(cont < 25000){
> > BigDecimal aleatorio = (new BigDecimal(
> > Math.random()).multiply(aux)).add(aux);
> > BigInteger p = new
> > BigInteger(aleatorio.toString().substring(0, aleatorio.toString
> > ().indexOf(".")));
> > aleatorio = (new BigDecimal(Math.random()).multiply(aux)).add(aux);
> > BigInteger q = new
> > BigInteger(aleatorio.toString().substring(0,
> > aleatorio.toString().indexOf(".")));
> > aleatorio = (new BigDecimal(Math.random()).multiply(aux)).add(aux);
> > BigInteger m = new BigInteger(
> > aleatorio.toString().substring(0, aleatorio.toString().indexOf(".")));
> > // saida += ;
> > String saida = cont+" \t"+calculaTempo(p, q, m)+fimDeLinha;
> > arquivo.seek (arquivo.length());
> > arquivo.write(saida.getBytes());
> > System.out.print(saida);
> > cont+=10;
> > aux = aux.multiply(new BigDecimal("1024"));
> > }
> > // System.out.println(saida);
> > }
> >
> > private static long calculaTempo(BigInteger p, BigInteger q, BigInteger m) {
> > long tempoInicial = Calendar.getInstance().getTimeInMillis();
> > BigInteger calculo = p.modPow(q, m);
> > // BigInteger calculo = powBigInteger(p, q).mod(m);
> > // q.
> > long tempoFinal = Calendar.getInstance().getTimeInMillis();
> > // System.out.println("------ "+calculo);
> > return tempoFinal - tempoInicial;
> > }
> >
> >
> > }
> >
> >
> > For the result in C with n = 10005 bits the time was 2800 ms (a example).
> >
> > For the result in JAVA with n = 10005 bits the time was 10 ms (a example).
> >
> >
> > Why this difference?
> >
> > Thanks,
> >
> > Nustenil Segundo de Moraes Lima Marinus
> > _______________________________________________
> > gmp-discuss mailing list
> > gmp-discuss at swox.com
> > https://gmplib.org/mailman/listinfo/gmp-discuss
> >
> >
>
More information about the gmp-discuss
mailing list