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);

    ulongrem = (ULONG_MAX >> GMP_LIMB_BITS * ulongsize) + 1;

  if (un > ulongsize && (u->_mp_d[ulongsize] >= ulongrem || un > ulongsize
+ 1))
    return 1;
      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;
    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 (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?


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