GMP compared to JAVA

[Julien CLEMENT]

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
>
>