Micro-GMP

[Marco Bodrato]

Ciao Paul!

Il 2018-11-23 13:38 paul zimmermann ha scritto:
> I presented some work in progress on "Micro-GMP", a modified
> version of Mini-GMP which works with 16-bit or even 8-bit limbs:

Great!
It is always interesting to see a further development based on some code 
we wrote!

> https://members.loria.fr/PZimmermann/talks/microgmp.pdf

In your presentation you write that "27 functions from mini-gmp.c need 
to be modified".

Of course the code in mini-gmp exploits the fact that mp_limb_t is 
defined as unsigned long, to keep the code as simple and as effective as 
possible. If you need to define a different mp_limb_t type, some 
modifications are obviously needed.

But... are you sure you need to change that many? I mean:
  - you changed mpz_div_qr_ui, did you really need to change also most of 
the functions mpz_?div_*_ui originally implemented as a simple call to 
mpz_div_qr_ui?
  - for similar reasons, was changing mpz_mul_si really needed? or 
mpz_lcm_ui?

I looked at the code and I'd suggest a couple of simpler 
implementations:

mpz_set_si (mpz_t r, signed long int x)
{
   if (x >= 0)
     mpz_set_ui (r, x);
   else /* (x < 0) */
     {
       mpz_set_ui (r, GMP_NEG_CAST (unsigned long int, x));
       mpz_neg (r, r);
     }
}

int
mpz_cmpabs_ui (const mpz_t u, unsigned long v)
{
   mpz_t absu;
   mpz_roinit_n (absu, u->_mp_d, GMP_ABS (u->_mp_size));
   return mpz_cmp_ui (absu, v);
}

You also changed mpn_invert_3by2. Maybe a handful of (mp_limb_t) casts 
could be added to the original function to make it work... but your 
rewrite is simpler and faster. Maybe the same could be done on 
gmp_umul_ppmm? for speed?



Unfortunately, writing a micro-gmp implementation outside of the 
project, has the bad effect that you will have to rewrite it for any new 
release.
Your micro- does not benefit of the improvement in mini- since the 
release of GMP-6.1.2, and some of your modifications might be 
superfluous now.
E.g. you changed in mpz_probab_prime_p the line:

   nm1->_mp_size = mpz_abs_sub_ui (nm1, n, 1);

into

   mpz_abs (nm1, n);
   mpz_sub_ui (nm1, nm1, 1);

but the current code reads 
https://gmplib.org/repo/gmp/file/17701/mini-gmp/mini-gmp.c#l3648

   mpz_abs (nm1, n);
   nm1->_mp_d[0] -= 1;

which works for any limb size (n is odd, -=1 on the lowest limb is 
always possible) and is faster than calling _sub_ui.

Maybe we can find a strategy to release also micro- as a part of the 
project, reducing code duplication. Would you like to cooperate on this?

Ĝis,
m

-- 
http://bodrato.it/papers/