speed of unbalanced division

[Zimmermann Paul]

       Hi,

on January 25 I reported efficiency issues with unbalanced multiplication.
Here I report similar issues with unbalanced division. Consider the program
below. I get on a 2Ghz Intel Xeon E7540 with GMP 5.1.0:

barbecue% ./bug2 2000001 1000001
mpz_tdiv_q(2000001,1000001) took 2244ms

barbecue% ./bug2 1698971 698971
mpz_tdiv_q(1698971,698971) took 3144ms

The first run computes the 10^6-limb quotient of the division of 2000001 limbs
by 1000001 limbs. The second run computes the 10^6-limb quotient of the
division of 1698971 limbs by 698971 limbs.

The second run should be faster (or equal in speed) to the first one, since
one can multiply both numerator and divisor by B^(1000001-698971) where B=2^64,
then perform a 2000001/1000001 division.

Instead the second run is 40% slower...

Paul Zimmermann

[1] http://gmplib.org/list-archives/gmp-devel/2013-January/002762.html

#include <stdio.h>
#include <stdlib.h>
#include "gmp.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 nn = atoi (argv[1]);
  unsigned long dn = atoi (argv[2]);
  mpz_t n, d, q;
  int st;

  mpz_init (n);
  mpz_init (d);
  mpz_init (q);

  mpz_random (n, nn);
  mpz_random (d, dn);

  st = cputime ();
  mpz_tdiv_q (q, n, d);
  printf ("mpz_tdiv_q(%lu,%lu) took %dms\n", mpz_size (n), mpz_size (d),
          cputime () - st);

  mpz_clear (n);
  mpz_clear (d);
  mpz_clear (q);

  return 0;
}