Micro-GMP

[Marco Bodrato]

Ciao Niels,

Il Mar, 11 Dicembre 2018 9:57 am, Niels Möller ha scritto:
>> I like the idea of reducing most of the _ui and _si functions to a small
>> set, so that only a few of them need special code.

> Looks nice. Would that also let us simplify mpz_add_ui? It's now 58
> lines, including the helper functions mpz_abs_{add,sub}_ui. Which might
> be more complexity than it's worth.

Once _add_ui is the only function calling them, you can get rid of the
helper functions, integrate them in the calling one and avoid duplications
in the code (slightly) simplifying it. Something like the following (that
already incorporate the block for ulongs larger than a limb).


void
mpz_add_ui (mpz_t r, const mpz_t a, unsigned long b)
{
  if (b > GMP_LIMB_MAX)
    {
      mpz_t bb;
      mpz_init_set_ui (bb, b);
      mpz_add (r, a, bb);
      mpz_clear (bb);
    }
  else
    {
      mp_size_t an = a->_mp_size;

      if (an == 0)
	mpz_set_ui (r, b);
      else if (an > 0)
	{
	  mp_ptr rp = MPZ_REALLOC (r, an + 1);
	  mp_limb_t cy = mpn_add_1 (rp, a->_mp_d, an, b);
	  rp[an] = cy;
	  r->_mp_size = an + cy;
	}
      else
	{
	  mp_ptr rp = MPZ_REALLOC (r, -an);
	  an = -an;

	  if (mpn_sub_1 (rp, a->_mp_d, an, b) != 0)
	    {
	      *rp = - *rp;
	      r->_mp_size = 1;
	    }
	  else
	    r->_mp_size = - mpn_normalized_size (rp, an);
	}
    }
}

void
mpz_sub_ui (mpz_t r, const mpz_t a, unsigned long b)
{
  mpz_ui_sub (r, b, a);
  mpz_neg (r, r);
}

void
mpz_ui_sub (mpz_t r, unsigned long a, const mpz_t b)
{
  mpz_neg (r, b);
  mpz_add_ui (r, r, a);
}


It would be more symmetrical with both _add_ui and _sub_ui using a single
_neg and a call to _ui_sub, but...

Something similar can be done also for _add and _sub, rewriting

void
mpz_sub (mpz_t r, const mpz_t a, const mpz_t b)
{
  mpz_t t;

  mpz_add (r, a, mpz_roinit_normal_n (t, b->_mp_d, - b->_mp_size));
}

and integrating both _abs_add and _abs_sub into _add.
Or more symmetrically integrating them into a single static void mpz_add_n
and defining

void
mpz_add (mpz_t r, const mpz_t a, const mpz_t b)
{
  mpz_add_n (r, a, b->_mp_d, b->_mp_size);
}

void
mpz_sub (mpz_t r, const mpz_t a, const mpz_t b)
{
  mpz_add_n (r, a, b->_mp_d, - b->_mp_size);
}

>> mpz_fits_slong_p (const mpz_t u)
>> {
>>   return (LONG_MAX + LONG_MIN == 0 || mpz_cmp_ui (u, LONG_MAX) <= 0) &&
>>     mpz_cmpabs_ui (u, GMP_NEG_CAST (unsigned long int, LONG_MIN)) <= 0;
>> }
>
> I find that a bit hard to read. If we're willing to have two cmp calls,
> we could do it simpler as
>
> int
> mpz_fits_slong_p (const mpz_t u)
> {
>   return mpz_cmp_si (u, LONG_MAX) <= 0 && mpz_cmp_si (LONG_MIN) >= 0;
> }

I'd define _cmp_si as a few branches and a call to _cmp_ui or _cmpabs_ui.
I'd define _cmp_ui as a couple of branches and a call to _cmpabs_ui.

That's why I'd reread it twice, then I'd use my version :-)

> If we add implementations with mpz_init_set_ui in more places (either
> conditionally or unconditionally), we could make that a bit more concise
> with
>
> struct mpz_ulong
> {
>   mpz_t x;
>   mp_limb_t xp[ULONG_SIZE_IN_LIMBS];
> };

Interesting. It should be portable even if ULONG_SIZE_IN_LIMBS is not a
configured constant (mini- avoids the ./configure step), but an expression
that can be computed at compile time, right?

> mpz_srcptr
> mpz_roinit_ui (struct mpz_ulong *m, unsigned long xl)
> {
>   return mpz_roinit_normal_n (m->x, m->xp, mpn_set_ui (m->xp, xl));
> }
>
> where mpn_set_ui converts the unsigned long to limbs (trivial in the
> usual case that mp_limb_t == unsigned long) and returns the normalized
> size.

Maybe one can also try to avoid to copy the value in the trivial case?

#define MPZ_ROINIT_UI (m,x) \
(sizeof(x) == sizeof(mp_limb_t) ? \
mpz_roinit_normal_n ((m)->x, &(x), (x) != 0): \
mpz_roinit_normal_n ((m)->x, (m)->xp, mpn_set_ui ((m)->xp, x)))

> void
> mpz_add_ui (mpz_t r, const mpz_t a, unsigned long b)
> { struct mpz_ulong t; mpz_add (r, a, mpz_roinit_ui (&t, b)); }

Sounds interesting...

We might start trying to rewrite all _ui functions with a
mpz_roinit_normal_n call and see the impact on speed.

Could this strategy be applied also to _div functions? And what about _si?

Ĝis,
m

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