Micro-GMP
Marco Bodrato
bodrato at mail.dm.unipi.it
Fri Nov 30 06:43:40 UTC 2018
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/
More information about the gmp-devel
mailing list