[Gmp-commit] /var/hg/gmp: 5 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri May 25 10:41:03 CEST 2012
details: /var/hg/gmp/rev/f028552a9851
changeset: 15006:f028552a9851
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri May 25 10:28:23 2012 +0200
description:
mini-gmp/tests/t-div.c: Test all _qr, _q, _r variants.
details: /var/hg/gmp/rev/565196842be9
changeset: 15007:565196842be9
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri May 25 10:29:21 2012 +0200
description:
mini-gmp/mini-gmp.[ch] (mpz_mod, mpz_mod_ui): New functions.
details: /var/hg/gmp/rev/edbd6fea345d
changeset: 15008:edbd6fea345d
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri May 25 10:31:40 2012 +0200
description:
mpz/scan1.c: Simplify.
details: /var/hg/gmp/rev/90135c5c415e
changeset: 15009:90135c5c415e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri May 25 10:37:55 2012 +0200
description:
mpz/scan1.c: Add a shortcut for scan1(z, 0).
details: /var/hg/gmp/rev/7bf8ca53869b
changeset: 15010:7bf8ca53869b
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri May 25 10:40:47 2012 +0200
description:
mini-gmp/tests/t-lcm.c: Test the _ui variant.
diffstat:
ChangeLog | 10 +++++
mini-gmp/mini-gmp.c | 15 +++++++
mini-gmp/mini-gmp.h | 4 ++
mini-gmp/tests/t-div.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++---
mini-gmp/tests/t-lcm.c | 14 +++++++
mpz/scan1.c | 66 +++++++++++-----------------------
6 files changed, 153 insertions(+), 51 deletions(-)
diffs (truncated from 352 to 300 lines):
diff -r d94adfcddabb -r 7bf8ca53869b ChangeLog
--- a/ChangeLog Thu May 24 15:28:25 2012 +0200
+++ b/ChangeLog Fri May 25 10:40:47 2012 +0200
@@ -1,3 +1,13 @@
+2012-05-25 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp/tests/t-div.c: Test all _qr, _q, _r variants.
+ * mini-gmp/tests/t-lcm.c: Test the _ui variant.
+
+ * mini-gmp/mini-gmp.c (mpz_mod, mpz_mod_ui): New functions.
+ * mini-gmp/mini-gmp.h (mpz_mod, mpz_mod_ui): Prototypes.
+
+ * mpz/scan1.c: Simplify, and add a shortcut for scan1(z, 0).
+
2012-05-24 Torbjorn Granlund <tege at gmplib.org>
* mpz/n_pow_ui.c: Cast non-limb count_leading_zeros argument.
diff -r d94adfcddabb -r 7bf8ca53869b mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Thu May 24 15:28:25 2012 +0200
+++ b/mini-gmp/mini-gmp.c Fri May 25 10:40:47 2012 +0200
@@ -2205,6 +2205,15 @@
mpz_div_qr (NULL, r, n, d, DIV_TRUNC);
}
+void
+mpz_mod (mpz_t r, const mpz_t n, const mpz_t d)
+{
+ if (d->_mp_size >= 0)
+ mpz_div_qr (NULL, r, n, d, DIV_FLOOR);
+ else
+ mpz_div_qr (NULL, r, n, d, DIV_CEIL);
+}
+
static void
mpz_div_q_2exp (mpz_t q, const mpz_t u, mp_bitcnt_t bit_index,
enum mpz_div_round_mode mode)
@@ -2521,6 +2530,12 @@
return mpz_div_qr_ui (NULL, NULL, n, d, DIV_TRUNC);
}
+unsigned long
+mpz_mod_ui (mpz_t r, const mpz_t n, unsigned long d)
+{
+ return mpz_div_qr_ui (NULL, r, n, d, DIV_FLOOR);
+}
+
void
mpz_divexact_ui (mpz_t q, const mpz_t n, unsigned long d)
{
diff -r d94adfcddabb -r 7bf8ca53869b mini-gmp/mini-gmp.h
--- a/mini-gmp/mini-gmp.h Thu May 24 15:28:25 2012 +0200
+++ b/mini-gmp/mini-gmp.h Fri May 25 10:40:47 2012 +0200
@@ -141,6 +141,8 @@
void mpz_fdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t);
void mpz_tdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t);
+void mpz_mod (mpz_t, const mpz_t, const mpz_t);
+
void mpz_divexact (mpz_t, const mpz_t, const mpz_t);
int mpz_divisible_p (const mpz_t, const mpz_t);
@@ -158,6 +160,8 @@
unsigned long mpz_fdiv_ui (const mpz_t, unsigned long);
unsigned long mpz_tdiv_ui (const mpz_t, unsigned long);
+unsigned long mpz_mod_ui (mpz_t, const mpz_t, unsigned long);
+
void mpz_divexact_ui (mpz_t, const mpz_t, unsigned long);
int mpz_divisible_ui_p (const mpz_t, unsigned long);
diff -r d94adfcddabb -r 7bf8ca53869b mini-gmp/tests/t-div.c
--- a/mini-gmp/tests/t-div.c Thu May 24 15:28:25 2012 +0200
+++ b/mini-gmp/tests/t-div.c Fri May 25 10:40:47 2012 +0200
@@ -15,8 +15,11 @@
free (buf);
}
-typedef void div_func (mpz_t, mpz_t, const mpz_t, const mpz_t);
-typedef unsigned long div_ui_func (mpz_t, mpz_t, const mpz_t, unsigned long);
+typedef void div_qr_func (mpz_t, mpz_t, const mpz_t, const mpz_t);
+typedef unsigned long div_qr_ui_func (mpz_t, mpz_t, const mpz_t, unsigned long);
+typedef void div_func (mpz_t, const mpz_t, const mpz_t);
+typedef unsigned long div_x_ui_func (mpz_t, const mpz_t, unsigned long);
+typedef unsigned long div_ui_func (const mpz_t, unsigned long);
int
main (int argc, char **argv)
@@ -40,17 +43,37 @@
{
static const enum hex_random_op ops[3] = { OP_CDIV, OP_FDIV, OP_TDIV };
static const char name[3] = { 'c', 'f', 't'};
- static div_func * const div [3] =
+ static div_qr_func * const div_qr [3] =
{
mpz_cdiv_qr, mpz_fdiv_qr, mpz_tdiv_qr
};
- static div_ui_func *div_ui[3] =
+ static div_qr_ui_func *div_qr_ui[3] =
{
mpz_cdiv_qr_ui, mpz_fdiv_qr_ui, mpz_tdiv_qr_ui
};
+ static div_func * const div_q [3] =
+ {
+ mpz_cdiv_q, mpz_fdiv_q, mpz_tdiv_q
+ };
+ static div_x_ui_func *div_q_ui[3] =
+ {
+ mpz_cdiv_q_ui, mpz_fdiv_q_ui, mpz_tdiv_q_ui
+ };
+ static div_func * const div_r [3] =
+ {
+ mpz_cdiv_r, mpz_fdiv_r, mpz_tdiv_r
+ };
+ static div_x_ui_func *div_r_ui[3] =
+ {
+ mpz_cdiv_r_ui, mpz_fdiv_r_ui, mpz_tdiv_r_ui
+ };
+ static div_ui_func *div_ui[3] =
+ {
+ mpz_cdiv_ui, mpz_fdiv_ui, mpz_tdiv_ui
+ };
mini_random_op4 (ops[j], MAXBITS, a, b, rq, rr);
- div[j] (q, r, a, b);
+ div_qr[j] (q, r, a, b);
if (mpz_cmp (r, rr) || mpz_cmp (q, rq))
{
fprintf (stderr, "mpz_%cdiv_qr failed:\n", name[j]);
@@ -62,11 +85,33 @@
dump ("qref", rq);
abort ();
}
+ mpz_set_si (q, -5);
+ div_q[j] (q, a, b);
+ if (mpz_cmp (q, rq))
+ {
+ fprintf (stderr, "mpz_%cdiv_q failed:\n", name[j]);
+ dump ("a", a);
+ dump ("b", b);
+ dump ("q ", q);
+ dump ("qref", rq);
+ abort ();
+ }
+ mpz_set_ui (r, ~5);
+ div_r[j] (r, a, b);
+ if (mpz_cmp (r, rr))
+ {
+ fprintf (stderr, "mpz_%cdiv_r failed:\n", name[j]);
+ dump ("a", a);
+ dump ("b", b);
+ dump ("r ", r);
+ dump ("rref", rr);
+ abort ();
+ }
if (mpz_fits_ulong_p (b))
{
mp_limb_t rl;
- rl = div_ui[j] (q, r, a, mpz_get_ui (b));
+ rl = div_qr_ui[j] (q, r, a, mpz_get_ui (b));
if (rl != mpz_get_ui (rr)
|| mpz_cmp (r, rr) || mpz_cmp (q, rq))
{
@@ -80,6 +125,44 @@
dump ("qref", rq);
abort ();
}
+
+ mpz_set_si (q, 3);
+ rl = div_q_ui[j] (q, a, mpz_get_ui (b));
+ if (rl != mpz_get_ui (rr) || mpz_cmp (q, rq))
+ {
+ fprintf (stderr, "mpz_%cdiv_q_ui failed:\n", name[j]);
+ dump ("a", a);
+ dump ("b", b);
+ fprintf(stderr, "rl = %lx\n", rl);
+ dump ("rref", rr);
+ dump ("q ", q);
+ dump ("qref", rq);
+ abort ();
+ }
+
+ mpz_set_ui (r, 7);
+ rl = div_r_ui[j] (r, a, mpz_get_ui (b));
+ if (rl != mpz_get_ui (rr) || mpz_cmp (r, rr))
+ {
+ fprintf (stderr, "mpz_%cdiv_qr_ui failed:\n", name[j]);
+ dump ("a", a);
+ dump ("b", b);
+ fprintf(stderr, "rl = %lx\n", rl);
+ dump ("r ", r);
+ dump ("rref", rr);
+ abort ();
+ }
+
+ rl = div_ui[j] (a, mpz_get_ui (b));
+ if (rl != mpz_get_ui (rr))
+ {
+ fprintf (stderr, "mpz_%cdiv_qr_ui failed:\n", name[j]);
+ dump ("a", a);
+ dump ("b", b);
+ fprintf(stderr, "rl = %lx\n", rl);
+ dump ("rref", rr);
+ abort ();
+ }
}
}
}
diff -r d94adfcddabb -r 7bf8ca53869b mini-gmp/tests/t-lcm.c
--- a/mini-gmp/tests/t-lcm.c Thu May 24 15:28:25 2012 +0200
+++ b/mini-gmp/tests/t-lcm.c Fri May 25 10:40:47 2012 +0200
@@ -41,6 +41,20 @@
dump ("ref", s);
abort ();
}
+ if (mpz_fits_ulong_p (b))
+ {
+ mpz_set_si (g, 0);
+ mpz_lcm_ui (g, a, mpz_get_ui (b));
+ if (mpz_cmp (g, s))
+ {
+ fprintf (stderr, "mpz_lcm_ui failed:\n");
+ dump ("a", a);
+ dump ("b", b);
+ dump ("r", g);
+ dump ("ref", s);
+ abort ();
+ }
+ }
}
mpz_clear (a);
diff -r d94adfcddabb -r 7bf8ca53869b mpz/scan1.c
--- a/mpz/scan1.c Thu May 24 15:28:25 2012 +0200
+++ b/mpz/scan1.c Fri May 25 10:40:47 2012 +0200
@@ -33,7 +33,7 @@
mp_srcptr u_ptr = PTR(u);
mp_size_t size = SIZ(u);
mp_size_t abs_size = ABS(size);
- mp_srcptr u_end = u_ptr + abs_size;
+ mp_srcptr u_end = u_ptr + abs_size - 1;
mp_size_t starting_limb = starting_bit / GMP_NUMB_BITS;
mp_srcptr p = u_ptr + starting_limb;
mp_limb_t limb;
@@ -44,6 +44,10 @@
if (starting_limb >= abs_size)
return (size >= 0 ? ~(mp_bitcnt_t) 0 : starting_bit);
+ /* This is an important case, where sign is not relevant! */
+ if (starting_bit == 0)
+ goto short_cut;
+
limb = *p;
if (size >= 0)
@@ -55,62 +59,35 @@
{
/* If it's the high limb which is zero after masking, then there's
no 1 bits after starting_bit. */
- p++;
if (p == u_end)
return ~(mp_bitcnt_t) 0;
/* Otherwise search further for a non-zero limb. The high limb is
non-zero, if nothing else. */
- for (;;)
+ search_nonzero:
+ do
{
+ ASSERT (p != u_end);
+ p++;
+ short_cut:
limb = *p;
- if (limb != 0)
- break;
- p++;
- ASSERT (p < u_end);
}
+ while (limb == 0);
}
}
else
{
- mp_srcptr q;
+ /* If there's a non-zero limb before ours then we're in the ones
+ complement region. */
+ if (mpn_zero_p (u_ptr, starting_limb)) {
+ if (limb == 0)
+ /* Seeking for the first non-zero bit, it is the same for u and -u. */
+ goto search_nonzero;
- /* If there's a non-zero limb before ours then we're in the ones
- complement region. Search from *(p-1) downwards since that might
- give better cache locality, and since a non-zero in the middle of a
- number is perhaps a touch more likely than at the end. */
- q = p;
- while (q != u_ptr)
- {
- q--;
- if (*q != 0)
More information about the gmp-commit
mailing list