Micro-GMP

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> The test suite is a test suite and not a benchmark, I know... but, before 
> the patch you propose
>  make check-mini-gmp;time make check-mini-gmp
> reports (on a slow machine)
>  user	0m24.610s
>
> after the patch (on the same machine):
>  user	0m45.160s

That's a big difference. I wonder which functions are responsible. And
we'd have to make the tradeoff between code complexity and speed on a
function by function basis, I think.

> 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.
>
> I mean:
>  - you do not really need to touch mpz_mul_si nor mpz_lcm_ui;
>  - you can use compact functions like
>
> void mpz_ui_sub (mpz_t r, unsigned long a, const mpz_t b)
> { mpz_neg (r, b); mpz_add_ui (r, r, a); }
>
> void mpz_sub_ui (mpz_t r, const mpz_t a, unsigned long b)
> { mpz_ui_sub (r, b, a); mpz_neg (r, r); }

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.

>  - and reduce _fits_ to comparisons and then to cmpabs, as in
>
> 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;
}

> But I do not like the idea of implementing almost all _[su]i function with
> an _init_set, the corresponding non _?i function, _clear. It sounds like a
> too big waste.

In my patch, I think using it for add_ui looks like reasonable tradeoff.
Maybe not for div_*_ui.

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];
};

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.

Then, e.g.,

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

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.