Micro-GMP
Niels Möller
nisse at lysator.liu.se
Mon Dec 10 21:43:42 UTC 2018
nisse at lysator.liu.se (Niels Möller) writes:
> 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
150. If we go this way, might make sense with some magic like an
mpz_roinit_ui with everything stack allocated.
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.
Regards,
/Niels
diff -r 9a958f8b67e4 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Sun Dec 09 20:28:18 2018 +0100
+++ b/mini-gmp/mini-gmp.c Mon Dec 10 22:33:00 2018 +0100
@@ -964,36 +964,6 @@ mpn_div_qr_1_preinv (mp_ptr qp, mp_srcpt
return r >> inv->shift;
}
-static mp_limb_t
-mpn_div_qr_1 (mp_ptr qp, mp_srcptr np, mp_size_t nn, mp_limb_t d)
-{
- assert (d > 0);
-
- /* Special case for powers of two. */
- if ((d & (d-1)) == 0)
- {
- mp_limb_t r = np[0] & (d-1);
- if (qp)
- {
- if (d <= 1)
- mpn_copyi (qp, np, nn);
- else
- {
- unsigned shift;
- gmp_ctz (shift, d);
- mpn_rshift (qp, np, nn, shift);
- }
- }
- return r;
- }
- else
- {
- struct gmp_div_inverse inv;
- mpn_div_qr_1_invert (&inv, d);
- return mpn_div_qr_1_preinv (qp, np, nn, &inv);
- }
-}
-
static void
mpn_div_qr_2_preinv (mp_ptr qp, mp_ptr np, mp_size_t nn,
const struct gmp_div_inverse *inv)
@@ -1807,36 +1777,23 @@ mpz_sgn (const mpz_t u)
int
mpz_cmp_si (const mpz_t u, long v)
{
- mp_size_t usize = u->_mp_size;
-
- if (v >= 0)
- return mpz_cmp_ui (u, v);
- else if (usize >= 0)
- return 1;
- else if (usize < -1)
- return -1;
- else /* usize == -1 */
- {
- unsigned long uu = mpz_get_ui (u);
- unsigned long vv = GMP_NEG_CAST (mp_limb_t, v);
- return GMP_CMP(vv, uu);
- }
+ mpz_t t;
+ int res;
+ mpz_init_set_si (t, v);
+ res = mpz_cmp (u, t);
+ mpz_clear (t);
+ return res;
}
int
mpz_cmp_ui (const mpz_t u, unsigned long v)
{
- mp_size_t usize = u->_mp_size;
-
- if (usize < 0)
- return -1;
- else if (usize > 1)
- return 1;
- else
- {
- unsigned long uu = mpz_get_ui (u);
- return GMP_CMP(uu, v);
- }
+ mpz_t t;
+ int res;
+ mpz_init_set_ui (t, v);
+ res = mpz_cmp (u, t);
+ mpz_clear (t);
+ return res;
}
int
@@ -1856,13 +1813,12 @@ mpz_cmp (const mpz_t a, const mpz_t b)
int
mpz_cmpabs_ui (const mpz_t u, unsigned long v)
{
- if (GMP_ABS (u->_mp_size) > 1)
- return 1;
- else
- {
- unsigned long uu = mpz_get_ui (u);
- return GMP_CMP(uu, v);
- }
+ mpz_t t;
+ int res;
+ mpz_init_set_ui (t, v);
+ res = mpz_cmpabs (u, t);
+ mpz_clear (t);
+ return res;
}
int
@@ -1897,81 +1853,31 @@ mpz_swap (mpz_t u, mpz_t v)
/* MPZ addition and subtraction */
-/* Adds to the absolute value. Returns new size, but doesn't store it. */
-static mp_size_t
-mpz_abs_add_ui (mpz_t r, const mpz_t a, unsigned long b)
-{
- mp_size_t an;
- mp_ptr rp;
- mp_limb_t cy;
-
- an = GMP_ABS (a->_mp_size);
- if (an == 0)
- {
- MPZ_REALLOC (r, 1)[0] = b;
- return b > 0;
- }
-
- rp = MPZ_REALLOC (r, an + 1);
-
- cy = mpn_add_1 (rp, a->_mp_d, an, b);
- rp[an] = cy;
- an += cy;
-
- return an;
-}
-
-/* Subtract from the absolute value. Returns new size, (or -1 on underflow),
- but doesn't store it. */
-static mp_size_t
-mpz_abs_sub_ui (mpz_t r, const mpz_t a, unsigned long b)
-{
- mp_size_t an = GMP_ABS (a->_mp_size);
- mp_ptr rp;
-
- if (an == 0)
- {
- MPZ_REALLOC (r, 1)[0] = b;
- return -(b > 0);
- }
- rp = MPZ_REALLOC (r, an);
- if (an == 1 && a->_mp_d[0] < b)
- {
- rp[0] = b - a->_mp_d[0];
- return -1;
- }
- else
- {
- gmp_assert_nocarry (mpn_sub_1 (rp, a->_mp_d, an, b));
- return mpn_normalized_size (rp, an);
- }
-}
-
void
mpz_add_ui (mpz_t r, const mpz_t a, unsigned long b)
{
- if (a->_mp_size >= 0)
- r->_mp_size = mpz_abs_add_ui (r, a, b);
- else
- r->_mp_size = -mpz_abs_sub_ui (r, a, b);
+ mpz_t t;
+ mpz_init_set_ui (t, b);
+ mpz_add (r, a, t);
+ mpz_clear (t);
}
void
mpz_sub_ui (mpz_t r, const mpz_t a, unsigned long b)
{
- if (a->_mp_size < 0)
- r->_mp_size = -mpz_abs_add_ui (r, a, b);
- else
- r->_mp_size = mpz_abs_sub_ui (r, a, b);
+ mpz_t t;
+ mpz_init_set_ui (t, b);
+ mpz_sub (r, a, t);
+ mpz_clear (t);
}
void
mpz_ui_sub (mpz_t r, unsigned long a, const mpz_t b)
{
- if (b->_mp_size < 0)
- r->_mp_size = mpz_abs_add_ui (r, b, a);
- else
- r->_mp_size = -mpz_abs_sub_ui (r, b, a);
+ mpz_t t;
+ mpz_init_set_ui (t, a);
+ mpz_sub (r, t, b);
+ mpz_clear (t);
}
static mp_size_t
@@ -2052,38 +1958,19 @@ mpz_sub (mpz_t r, const mpz_t a, const m
void
mpz_mul_si (mpz_t r, const mpz_t u, long int v)
{
- if (v < 0)
- {
- mpz_mul_ui (r, u, GMP_NEG_CAST (unsigned long int, v));
- mpz_neg (r, r);
- }
- else
- mpz_mul_ui (r, u, v);
+ mpz_t t;
+ mpz_init_set_si (t, v);
+ mpz_mul (r, u, t);
+ mpz_clear (t);
}
void
mpz_mul_ui (mpz_t r, const mpz_t u, unsigned long int v)
{
- mp_size_t un, us;
- mp_ptr tp;
- mp_limb_t cy;
-
- us = u->_mp_size;
-
- if (us == 0 || v == 0)
- {
- r->_mp_size = 0;
- return;
- }
-
- un = GMP_ABS (us);
-
- tp = MPZ_REALLOC (r, un + 1);
- cy = mpn_mul_1 (tp, u->_mp_d, un, v);
- tp[un] = cy;
-
- un += (cy > 0);
- r->_mp_size = (us < 0) ? - un : un;
+ mpz_t t;
+ mpz_init_set_ui (t, v);
+ mpz_mul (r, u, t);
+ mpz_clear (t);
}
void
@@ -2162,8 +2049,8 @@ void
mpz_addmul_ui (mpz_t r, const mpz_t u, unsigned long int v)
{
mpz_t t;
- mpz_init (t);
- mpz_mul_ui (t, u, v);
+ mpz_init_set_ui (t, v);
+ mpz_mul (t, u, t);
mpz_add (r, r, t);
mpz_clear (t);
}
@@ -2172,8 +2059,8 @@ void
mpz_submul_ui (mpz_t r, const mpz_t u, unsigned long int v)
{
mpz_t t;
- mpz_init (t);
- mpz_mul_ui (t, u, v);
+ mpz_init_set_ui (t, v);
+ mpz_mul (t, u, t);
mpz_sub (r, r, t);
mpz_clear (t);
}
@@ -2567,57 +2454,25 @@ mpz_congruent_p (const mpz_t a, const mp
static unsigned long
mpz_div_qr_ui (mpz_t q, mpz_t r,
- const mpz_t n, unsigned long d, enum mpz_div_round_mode mode)
+ const mpz_t n, unsigned long dl, enum mpz_div_round_mode mode)
{
- mp_size_t ns, qn;
- mp_ptr qp;
- mp_limb_t rl;
- mp_size_t rs;
-
- ns = n->_mp_size;
- if (ns == 0)
- {
- if (q)
- q->_mp_size = 0;
- if (r)
- r->_mp_size = 0;
- return 0;
- }
-
- qn = GMP_ABS (ns);
- if (q)
- qp = MPZ_REALLOC (q, qn);
- else
- qp = NULL;
-
- rl = mpn_div_qr_1 (qp, n->_mp_d, qn, d);
- assert (rl < d);
-
- rs = rl > 0;
- rs = (ns < 0) ? -rs : rs;
-
- if (rl > 0 && ( (mode == GMP_DIV_FLOOR && ns < 0)
- || (mode == GMP_DIV_CEIL && ns >= 0)))
- {
- if (q)
- gmp_assert_nocarry (mpn_add_1 (qp, qp, qn, 1));
- rl = d - rl;
- rs = -rs;
- }
-
+ mpz_t d;
+ unsigned long rl;
+ mpz_init_set_ui (d, dl);
if (r)
{
- MPZ_REALLOC (r, 1)[0] = rl;
- r->_mp_size = rs;
+ mpz_div_qr (q, r, n, d, mode);
+ rl = mpz_get_ui (r);
}
- if (q)
+ else
{
- qn -= (qp[qn-1] == 0);
- assert (qn == 0 || qp[qn-1] > 0);
-
- q->_mp_size = (ns < 0) ? - qn : qn;
+ mpz_t t;
+ mpz_init (t);
+ mpz_div_qr (q, t, n, d, mode);
+ rl = mpz_get_ui (t);
+ mpz_clear (t);
}
-
+ mpz_clear (d);
return rl;
}
@@ -2757,22 +2612,16 @@ mpn_gcd_11 (mp_limb_t u, mp_limb_t v)
unsigned long
mpz_gcd_ui (mpz_t g, const mpz_t u, unsigned long v)
{
- mp_size_t un;
-
- if (v == 0)
- {
- if (g)
- mpz_abs (g, u);
- }
- else
- {
- un = GMP_ABS (u->_mp_size);
- if (un != 0)
- v = mpn_gcd_11 (mpn_div_qr_1 (NULL, u->_mp_d, un, v), v);
-
- if (g)
- mpz_set_ui (g, v);
- }
+ mpz_t t;
+ mpz_init_set_ui(t, v);
+ mpz_gcd (t, u, t);
+ if (v > 0)
+ v = mpz_get_ui (t);
+
+ if (g)
+ mpz_swap (t, g);
+
+ mpz_clear (t);
return v;
}
@@ -3059,16 +2908,10 @@ mpz_lcm (mpz_t r, const mpz_t u, const m
void
mpz_lcm_ui (mpz_t r, const mpz_t u, unsigned long v)
{
- if (v == 0 || u->_mp_size == 0)
- {
- r->_mp_size = 0;
- return;
- }
-
- v /= mpz_gcd_ui (NULL, u, v);
- mpz_mul_ui (r, u, v);
-
- mpz_abs (r, r);
+ mpz_t t;
+ mpz_init_set_ui (t, v);
+ mpz_lcm (r, u, t);
+ mpz_clear (t);
}
int
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list