Micro-GMP

[Marco Bodrato]

Ciao Paul,

Il Lun, 10 Dicembre 2018 4:13 pm, paul zimmermann ha scritto:
>> 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...

> it passes all MPFR tests, both with uint16 and uint8. It is also faster
> than micro-gmp

I believe that most of the speed (compared to your micro-) comes from the
trivial:

#define gmp_umul_ppmm(w1, w0, u, v)                                     \
  do {                                                                  \
    int LOCAL_GMP_LIMB_BITS = GMP_LIMB_BITS;                            \
    if (sizeof (unsigned int) >= 2 * sizeof (mp_limb_t))                \
      {                                                                 \
        unsigned int __ww = (unsigned int) (u) * (v);                   \
        w0 = (mp_limb_t) __ww;                                          \
        w1 = (mp_limb_t) (__ww >> LOCAL_GMP_LIMB_BITS);                 \
      }                                                                 \
    else if (sizeof (unsigned long int) >= 2 * sizeof (mp_limb_t))      \
      {                                                                 \
        unsigned long int __ww = (unsigned long int) (u) * (v);         \
        w0 = (mp_limb_t) __ww;                                          \
        w1 = (mp_limb_t) (__ww >> LOCAL_GMP_LIMB_BITS);                 \
      }                                                                 \
    else {                                                              \
...

>            tdiv        tcos          tdiv       tcos
> uint8      7.1s       21m40s         3.8s       7m26s

Minutes for a single test!

Does that test use "large" numbers? If a limb is 8 bits, you need 20 limbs
to represent a 160-bits number. And mini- will never implement Karatsuba
nor any other "non-basecase" algorithm.

You really need asl.h!

> PS: it would be nice to indicate in mini-gmp.h the places to modify to
> enable 16-bit or 8-bit limbs.

It should be enough to change the line
typedef unsigned long mp_limb_t;
to
typedef unsigned short mp_limb_t;
or
typedef unsigned char mp_limb_t;

Ĝis,
m

-- 
http://bodrato.it/artikloj/