efficiency bug in mpz_powm_ui?

[paul zimmermann]

       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 at 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 at 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;
}