Benchmarks: Java vs C (Part 3)

Here is the (nearly) same program (factorize3.mac.c) coded in C (also copyright JGW). It needs to be compiled with -lgmp, the GMP math library.

/* Factoring with WEP method using random base(s).
*/

#include
#include
#include

#include

#include "gmp.h"

int flag_verbose = 0;

int
factor_using_random_wep (mpz_t s, unsigned long p, unsigned long T)
{
mpz_t V, v1, v2, v3, b, bb, bbb, bbbb, wanless;
long numtrials;
int flag;

gmp_randstate_t rstate;



if (flag_verbose)
{
printf ("[wep ");
printf ("s=");
mpz_out_str (stdout, 10, s);
printf ("\tp=");
printf ("%ld", p);
printf ("\tT=");
printf ("%ld", T);
printf ("]\n\r");
fflush (stdout);
}


if (mpz_probab_prime_p (s, 3))
{
printf ("P%ld\tT0\t", p);
mpz_out_str (stdout, 10, s);
fflush (stdout);
flag=2;
return(flag);
}



gmp_randinit (rstate, GMP_RAND_ALG_LC, 128);

{
#if HAVE_GETTIMEOFDAY
struct timeval tv;
gettimeofday (&tv, NULL);
gmp_randseed_ui (rstate, tv.tv_sec + tv.tv_usec);
#else
time_t t;
time (&t);
gmp_randseed_ui (rstate, t);
#endif
}






numtrials=0;

mpz_init_set_si (b, 1);
mpz_init_set_si (bb, 1);
mpz_init_set_si (bbb, 1);
mpz_init_set_si (bbbb, 1);
mpz_init_set_si (V, 1);
mpz_init_set_si (v1, 1);
mpz_init_set_si (v2, 1);
mpz_init_set_si (v3, 1);
mpz_init_set_si (wanless, 2);

while (mpz_cmp (wanless, s) < 0)
mpz_mul_ui (wanless, wanless, 2);


while (numtrials < T && (mpz_cmp_ui (V, 1) == 0 || mpz_cmp (V, s) == 0))
{


mpz_urandomb (b, rstate, 100L);
mpz_mul_ui(bb, b, p);
mpz_mul_ui(bbb, bb, 2);
mpz_add_ui(bbbb, bbb, 1);


mpz_powm (v1, bbbb, wanless, s);
mpz_powm (v2, v1, s, s);
mpz_sub (v3, v2, v1);
mpz_gcd (V, s, v3);

if (flag_verbose)
if (numtrials%1000 == 0)
{
printf ("numtrials=%ld\tb=", numtrials);
mpz_out_str (stdout, 10, b);
printf ("\r");
fflush (stdout);
}

numtrials++;

}

if (flag_verbose)
printf("\n\r");


if (mpz_cmp_ui (V, 1) > 0 && mpz_cmp (V, s) < 0)
{
printf ("P%ld\tT%ld\t", p, numtrials);
mpz_out_str (stdout, 10, V);
printf("\tbase=");
mpz_out_str (stdout, 10, bbbb);
printf ("\n");
fflush (stdout);

flag=3;
}

else
{
printf ("P%ld\tT%ld\n", p, T);
flag=0;
}



mpz_clear (b);
mpz_clear (bb);
mpz_clear (bbb);
mpz_clear (bbbb);
mpz_clear (V);
mpz_clear (v1);
mpz_clear (v2);
mpz_clear (v3);
mpz_clear (wanless);

return (flag);

}

main (int argc, char *argv[])
{
mpz_t r, s, t, F, f;
unsigned long p, T;
int i;
int flag;

if (argc > 1 && !strcmp (argv[1], "-v"))
{
flag_verbose = 1;
argv++;
argc--;
}

mpz_init (r);
mpz_init (s);
mpz_init (t);
mpz_init (F);
mpz_init (f);

mpz_set_ui (F, 1);
mpz_set_ui (f, 1);

if (argc > 1)
{
p = 0;
for (i = 1; i < argc; i++)
{
if (!strncmp (argv[i], "-M", 2))
{
p = atoi (argv[i] + 2);
mpz_set_ui (t, 1);
mpz_mul_2exp (t, t, p);
mpz_sub_ui (t, t, 1);
}
else if (!strncmp (argv[i], "-P", 2))
{
p = atoi (argv[i] + 2);
mpz_set_ui (t, 1);
mpz_mul_2exp (t, t, p);
mpz_add_ui (t, t, 1);
}
else if (!strncmp (argv[i], "-T", 2))
{
T = atoi (argv[i] + 2);
}
else
{
mpz_set_str (f, argv[i], 0);
mpz_mul (F, F, f);
}
}


mpz_mod (r, t, F);

if (mpz_cmp_si (r, 0) != 0) {
printf ("Wrong known factors!\n");
flag =1;
}
else {

mpz_div (s, t, F);

flag = factor_using_random_wep (s, p, T);

}
}

mpz_clear(r);
mpz_clear(s);
mpz_clear(t);
mpz_clear(F);
mpz_clear(f);

exit (flag);
}