mini-gmp and mpq

Bradley Lucier lucier at math.purdue.edu
Tue Feb 27 22:42:35 UTC 2018


Thanks.  I tried this test on my machine:

#include "mini-gmp.h"
#include "mini-mpq.h"

int main ()
{

   int j;

   for (j = 1000; --j >= 0; )
     {
       mpq_t  x, u;
       int    i;

       mpq_init (x);
       mpq_init (u);

       mpq_set_ui (x, 1, 1);
       mpq_set (u, x);
       for (i = 1000; --i >= 0; )
         {
           mpq_inv (x, x);
           mpq_add (x, u, x);
         }

       mpq_clear (x);
       mpq_clear (u);
     }
}

compiled with

firefly:~/programs/mini-gmp> gcc -Ofast -Wall -W -o test mini-mpq.c test.c

(-Ofast adds -fast-math, which you probably don't want in general, but I 
wanted a quick choice of options.)  With the original mpq_add I got

firefly:~/programs/mini-gmp> time ./test
8.044u 0.000s 0:08.04 100.0%	0+0k 0+0io 0pf+0w

with the upgraded one I got

time ./test
0.331u 0.000s 0:00.33 100.0%	0+0k 0+0io 0pf+0w

So this is a factor 25 in speed on numbers of size 695 bits.

If I increase i to 15,000 and do only one iteration, I get

time ./test
8.479u 0.000s 0:08.48 99.8%	0+0k 0+0io 0pf+0w

versus

firefly:~/programs/mini-gmp> time ./test
0.037u 0.000s 0:00.03 100.0%	0+0k 0+0io 0pf+0w

so a factor of about 229 (similar to your numbers).

on my machine:

model name	: Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
firefly:~/programs/mini-gmp> uname -a
Linux firefly 4.13.0-36-generic #40-Ubuntu SMP Fri Feb 16 20:07:48 UTC 
2018 x86_64 x86_64 x86_64 GNU/Linux

with

gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3.2)

My opinion is that factor of 25 on integers of about 10 times the word 
size for 16 extra lines of code is worth it.

You suggest:

 > The realway to speed-up that loop is to use the suggestion in gmpxx.h to
 > compute a rational+1, both for mini-gmp and the full GMP library:

That is, in fact, the change the mzscheme folks did at the time.  But 
the problem is more general, if you change 1 to 1/2, for example, the 
issue comes back.  (I submitted a issue report to the current Racket 
about this, but the bug reports seem to be password protected now.)  And 
the speedup occurs whenever the gcd of the denominators is 1, which 
happens a lot of you're adding an addend with small denominator to a 
running sum of rationals.

Brad


More information about the gmp-devel mailing list