Micro-GMP

[Marco Bodrato]

Ciao,

Il Lun, 10 Dicembre 2018 10:43 pm, Niels Möller ha scritto:
>> For the various _ui and _si functions, I think performance is less
>> important. For mini-gmp, I think it would make some sense to have a
>> non-trivial implementation only for mpz_set_ui and mpz_get_ui, and
>> implement all other _ui and _si functions in terms of that.
>
> Patch to do that below. What do you think? Reduces line count by about

> My gut feeling is that the performance loss might be acceptable, since
> any time consuming operations using mini-gmp will likely spend the bulk
> of the time in multi-limb multiplication or division. Not calling _ui
> and _si functions. But I don't know what a relevant banchmark would be.

Maybe a loop looking for the longest Collatz sequence (n->(3*n+1)/2^s)
with the starting value in a given interval? :-P

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

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

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

int mpz_cmp_ui (const mpz_t u, unsigned long v)
{ return (u->_mp_size < 0) ? -1 : mpz_cmpabs_ui (u, v); }

(You can find the code of the two last functions in my proposed patch,
used if (GMP_LIMB_BITS < GMP_ULONG_BITS). We can remove the other options,
if we want shorter code.)

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.

PS: with the patch I proposed and typedef unsigned long mp_limb_t;
user	0m24.520s (not a sensible change)
with typedef unsigned short mp_limb_t;
user	0m46.720s

Of course it can be simplified...


Ĝis,
m

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