Micro-GMP
Marco Bodrato
bodrato at mail.dm.unipi.it
Sat Dec 8 12:33:11 UTC 2018
Ciao Paul,
Il Lun, 3 Dicembre 2018 3:06 pm, paul zimmermann ha scritto:
>> From: Marco Bodrato <bodrato at mail.dm.unipi.it>
>> Il 2018-11-23 13:38 paul zimmermann ha scritto:
>> 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.
I just pushed some adaptations that does not need additional code, but
should increase portability of the code-
>> 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.
... but looking at the whole library, I think that _cmp_si and _cmp_ui
should use _cmpabs_ui and not viceversa... So that I'd propose a
completely different implementation:
mpz_cmpabs_ui (const mpz_t u, unsigned long v)
{
int ulongsize = GMP_ULONG_BITS / GMP_LIMB_BITS;
mp_limb_t ulongrem = 0;
mp_size_t un = GMP_ABS (u->_mp_size);
if (GMP_ULONG_BITS % GMP_LIMB_BITS != 0)
ulongrem = (ULONG_MAX >> GMP_LIMB_BITS * ulongsize) + 1;
if (un > ulongsize && (u->_mp_d[ulongsize] >= ulongrem || un > ulongsize
+ 1))
return 1;
else
{
unsigned long uu = mpz_get_ui (u);
return GMP_CMP(uu, v);
}
}
When mp_limb_t is unsigned long, gcc -O2 compiles this code exactly as
if (GMP_ABS (u->_mp_size) > 1)
return 1;
else
GMP_CMP(mpz_get_ui (u), v)
[...]
The same as the current code. And it gets optimised also for uint16 or uint8.
>> 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!
A attach a possible implementation of mini-gmp that should support limbs
of "any" size. Can you test it with MPFR? Both correctness and speed...
The attached file is the result of "hg diff" compared with the *current*
development version
[https://gmplib.org/repo/gmp/file/230246fe9acd/mini-gmp/mini-gmp.c], and
it passes the current check-mini-gmp suite.
This code inherits some ideas from the micro- code you published, but I
reorganised it completely. Basically (except for mpz_cmpabs_ui, already
described) it is a collection of alternatives implementations. But only in
some cases they completely substitute the general code, often they handle
only some special cases.
Some of them are "protected" by
if (GMP_LIMB_BITS < GMP_ULONG_BITS)
or
if (sizeof (mp_limb_t) != sizeof (unsigned long))
so that the compiler can choose the right one by optimisation.
Others are "protected" by
if (value > GMP_LIMB_MAX)
so that the compiler can optimise them out if values larger that
GMP_LIMB_MAX can not occur, and the alternative code is used at run-time
only for values that are too large.
The goal of this proposal is to have a more generic code (wrt limb size)
that an optimising compiler should compile exactly as the current one if
mp_limb_t is unsigned long.
Is the proposed code too complex to belong to mini-gmp?
Ĝis,
m
--
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mini-suppurt-micro.diff
Type: text/x-patch
Size: 8089 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20181208/68e39229/attachment-0001.bin>
More information about the gmp-devel
mailing list