Hi, it seems that mpz_powm_ui is highly inefficient when BASE^EXP has about the same size as MOD, in which case it could first compute BASE^EXP exactly, then perform only one reduction:
zimmerma@tomate:/tmp$ ./a.out 100000 GMP version: 6.2.0 mpz_ui_pow_ui+mpz_mod took 100ms set_ui+mpz_powm_ui took 2048ms zimmerma@tomate:/tmp$ ./a.out 1000000 GMP version: 6.2.0 mpz_ui_pow_ui+mpz_mod took 1005ms set_ui+mpz_powm_ui took 31138ms This was detected in the mpfr_remainder function, which is called from mpfr_sin to reduce huge arguments modulo Pi. Paul #include <stdio.h> #include <stdlib.h> #include <gmp.h> #include <assert.h> #include <sys/types.h> #include <sys/resource.h> int cputime () { struct rusage rus; getrusage (0, &rus); return rus.ru_utime.tv_sec * 1000 + rus.ru_utime.tv_usec / 1000; } int main (int argc, char *argv[]) { unsigned long n = atoi (argv[1]), e; mpz_t x, y, r1, r2; int t; printf ("GMP version: %s\n", gmp_version); /* compute x mod y in two ways, where x=2^e is twice as large as y */ mpz_init (x); mpz_init (y); mpz_init (r1); mpz_init (r2); mpz_random (y, n); e = 2 * mpz_size (y) * mp_bits_per_limb; t = cputime (); mpz_ui_pow_ui (x, 2, e); mpz_mod (r1, x, y); t = cputime () - t; printf ("mpz_ui_pow_ui+mpz_mod took %dms\n", t); t = cputime (); mpz_set_ui (x, 2); mpz_powm_ui (r2, x, e, y); t = cputime () - t; printf ("set_ui+mpz_powm_ui took %dms\n", t); assert (mpz_cmp (r1, r2) == 0); mpz_clear (x); mpz_clear (y); mpz_clear (r1); mpz_clear (r2); return 0; } _______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs