Question about the performance of the GMP on a specific integer division case

[Jeronimo Pellegrini]

Hello,

I have recently found one case that the GMP doesn't seem to optimize, in
the division functions, and I am curious about the reason.

When dividing A by B, and abs(A) is smaller than abs(B), it would be
faster to just return 0 as quotient and A as remainder, without actually
performing the division. Also, if abs(A)=abs(B), it could immediately
return quotient = sign(A) * sign(B) and remainder = 0...  But
apparently, the GMP doesn't do that.

I did a small experiment, and if seems that checking wether abs(A) <
abs(B) isn't expensive (or maybe I got something wrong?)

The program below computes the quotient of two numbers, 30^70 and 42^70
(I didn't do a full benchmark with a set of numbers etc, and I also only
have access to a x86_64 PC).  The program acepts a single character as
argument:

'x' = divide (larger / smaller), use mpz_tdiv_q
'X' = divide (larger / smaller), use the function 'd'
'y' = divide (smaller / larger), use mpz_tdiv_q
'Y' = divide (smaller / larger), use the function 'd'

The timings are shown below (average for 20 runs, on the same computer,
measured using the 'time' utility - it didn't seem to be necessary to
insert clock calls in the code).

GCC 12.2.0, optimization flag -O2:
x 0m7.105s
X 0m7.378s
y 0m6.303s
Y 0m0.672s

Looking at the y and Y cases it seems that it may be several times
faster to check if abs(A) < abs(B) and not do the full computation; and
the x and X cases seem to indicate that it may be just slightly slower
to do the verification if compiler optimization is on a reasonable level
(-O2).

I didn't include the test for abs(A)=abs(B), but this could be done
quickly, since a single call to mpz_cmpabs is enough to find out if
abs(A) < abs(B), abs(A)=abs(B), or otherwise.

So I was wondering why this case is not optimized. Are the mpz division
functions used in the implementation of mpz_powm_sec, or something like
that? Or is it because the small overhead of the verification is
considered already too much, and hence the user would have the
responsibility to do the check, if it's the case?

(I'm genuinely only asking why, and not really pushing for any changes
in the GMP code -- I have actually already implemented the check in the
application I was working on, and it works fine -- I'm ok with it the
way it is)

Thank you!
Jeronimo



#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

static inline void d(mpz_t q, mpz_t a, mpz_t b) {
    int cmp = mpz_cmpabs(a,b);
    if (cmp < 0)
	mpz_set_ui(q,0);
    else
	mpz_tdiv_q(q, a, b);
}

/*
  This program uses a single argument:

  x = divide (larger / smaller), use mpz_tdiv_q
  X = divide (larger / smaller), use the function 'd'
  y = divide (smaller / larger), use mpz_tdiv_q
  Y = divide (smaller / larger), use the function 'd'

  Argument checking is almost non-existent, since this is
  a proof-of-concept thing only.
*/
int main (int argc, char *argv[]) {
    if (argc != 2) exit(-1);
    
    mpz_t a;
    mpz_t b;
    mpz_t q;

    mpz_init_set_ui(a,30);
    mpz_init_set_ui(b,42);
    mpz_pow_ui(a,a,70);
    mpz_pow_ui(b,b,70);

    if (argv[1][0] == 'X' || argv[1][0] == 'x') 
	mpz_swap(a,b);

    if (argv[1][0] == 'X' || argv[1][0] == 'Y')
	for (long i=0; i < 100000000; i++)
	    d(q,a,b);
    else
	for (long i=0; i < 100000000; i++)
	    mpz_tdiv_q(q, a, b);

    mpz_out_str(stdout, 10, q);
    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(q);
}