Micro-GMP

[Marco Bodrato]

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>