Micro-GMP

[paul zimmermann]

       Dear Marco,

> Date: Fri, 30 Nov 2018 07:43:40 +0100
> From: Marco Bodrato <bodrato at mail.dm.unipi.it>
> 
> 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?

most changes for the _ui functions (including mpz_div_qr_ui) consist in first
converting the unsigned long argument into a mpz_t using mpz_set_ui, then
calling the corresponding function without _ui.

But indeed I don't remember why I changed the other mpz_?div_*_ui functions.
Maybe because it was simpler to just convert using mpz_set_ui, and do not have
to think at all.

>   - for similar reasons, was changing mpz_mul_si really needed? or 
> mpz_lcm_ui?

it seems mpz_mul_si does not need to be changed. Same for 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);
> }

indeed this is simpler.

Now there are only 18 that need to be modified.

> 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?

indeed, in several places I opted for simplicity, since speed was not
(at first) a goal. But when running "make check" of MPFR with micro-gmp-8,
I now realize speed is also important!

> 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?

yes of course!

Best regards,
Paul