[Gmp-commit] /var/hg/gmp: 5 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon Jan 15 20:09:02 UTC 2018
details: /var/hg/gmp/rev/3b86269b0dc7
changeset: 17532:3b86269b0dc7
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Jan 15 07:51:17 2018 +0100
description:
mini-gmp/tests/t-comb.c (checkWilson): check also mpz_2fac_ui
details: /var/hg/gmp/rev/bc082d82f941
changeset: 17533:bc082d82f941
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Jan 15 07:57:58 2018 +0100
description:
mini-gmp/mini-gmp.c (gmp_popcount_limb): micro-opt.
details: /var/hg/gmp/rev/33d84a07bbf3
changeset: 17534:33d84a07bbf3
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Jan 15 20:29:25 2018 +0100
description:
tests/mpz/t-bin.c: Test with large ints and bin_ui with values larger than an unsigned int.
details: /var/hg/gmp/rev/5b6155a340fa
changeset: 17535:5b6155a340fa
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Jan 15 20:31:13 2018 +0100
description:
mpz/bin_ui.c (posmpz_dec_ui): Relax ASSERT (spotted by TG)
details: /var/hg/gmp/rev/274ed86df599
changeset: 17536:274ed86df599
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Jan 15 20:42:23 2018 +0100
description:
Changelog
diffstat:
ChangeLog | 4 ++
mini-gmp/ChangeLog | 5 ++
mini-gmp/mini-gmp.c | 6 +-
mini-gmp/tests/t-comb.c | 15 +++++++-
mpz/bin_ui.c | 2 +-
tests/mpz/t-bin.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++--
6 files changed, 104 insertions(+), 11 deletions(-)
diffs (207 lines):
diff -r 3a9e770cd001 -r 274ed86df599 ChangeLog
--- a/ChangeLog Fri Jan 12 12:51:19 2018 +0100
+++ b/ChangeLog Mon Jan 15 20:42:23 2018 +0100
@@ -1,3 +1,7 @@
+2018-01-15 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * tests/mpz/t-bin.c: Extended tests for bin_ui and uint border cases.
+
2018-01-07 Torbjörn Granlund <tg at gmplib.org>
* mpn/arm: Revert last change, it hides a symbol needed for testing.
diff -r 3a9e770cd001 -r 274ed86df599 mini-gmp/ChangeLog
--- a/mini-gmp/ChangeLog Fri Jan 12 12:51:19 2018 +0100
+++ b/mini-gmp/ChangeLog Mon Jan 15 20:42:23 2018 +0100
@@ -1,3 +1,8 @@
+2018-01-15 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp/mini-gmp.c (gmp_popcount_limb): Micro-optimisations.
+ * mini-gmp/tests/t-comb.c (checkWilson): Check also mpz_2fac_ui.
+
2017-12-30 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mini-gmp.c (mpz_mfac_ui, mpz_2fac_ui): New functions.
diff -r 3a9e770cd001 -r 274ed86df599 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Fri Jan 12 12:51:19 2018 +0100
+++ b/mini-gmp/mini-gmp.c Mon Jan 15 20:42:23 2018 +0100
@@ -3870,10 +3870,10 @@
/* Do 16 bits at a time, to avoid limb-sized constants. */
for (c = 0; x > 0; x >>= 16)
{
- unsigned w = ((x >> 1) & 0x5555) + (x & 0x5555);
+ unsigned w = x - ((x >> 1) & 0x5555);
w = ((w >> 2) & 0x3333) + (w & 0x3333);
- w = ((w >> 4) & 0x0f0f) + (w & 0x0f0f);
- w = (w >> 8) + (w & 0x00ff);
+ w = (w >> 4) + w;
+ w = ((w >> 8) & 0x000f) + (w & 0x000f);
c += w;
}
return c;
diff -r 3a9e770cd001 -r 274ed86df599 mini-gmp/tests/t-comb.c
--- a/mini-gmp/tests/t-comb.c Fri Jan 12 12:51:19 2018 +0100
+++ b/mini-gmp/tests/t-comb.c Mon Jan 15 20:42:23 2018 +0100
@@ -1,6 +1,6 @@
/* Exercise mpz_fac_ui and mpz_bin_uiui.
-Copyright 2000-2002, 2012, 2013 Free Software Foundation, Inc.
+Copyright 2000-2002, 2012, 2013, 2017 Free Software Foundation, Inc.
This file is part of the GNU MP Library test suite.
@@ -102,7 +102,18 @@
void checkWilson (mpz_t f, unsigned long n)
{
- unsigned long m;
+ unsigned long m, a;
+
+ mpz_2fac_ui (f, 2 * n - 1);
+
+ a = mpz_fdiv_q_ui (f, f, n);
+ m = mpz_fdiv_ui (f, n);
+ if ((m != n - 1) || (a != 0))
+ {
+ printf ("mpz_2fac_ui(%lu) wrong\n", 2 * n - 1);
+ printf (" Wilson's theorem not verified: got (%lu, %lu), expected (0, %lu).\n", a, m, n - 1);
+ abort ();
+ }
mpz_fac_ui (f, n - 1);
m = mpz_fdiv_ui (f, n);
diff -r 3a9e770cd001 -r 274ed86df599 mpz/bin_ui.c
--- a/mpz/bin_ui.c Fri Jan 12 12:51:19 2018 +0100
+++ b/mpz/bin_ui.c Mon Jan 15 20:42:23 2018 +0100
@@ -81,7 +81,7 @@
#if BITS_PER_ULONG > GMP_NUMB_BITS
mpz_sub_ui (r, r, in);
#else
- ASSERT (mpz_cmp_ui (r, in) > 0);
+ ASSERT (mpz_cmp_ui (r, in) >= 0);
MPN_DECR_U (PTR (r), SIZ (r), in);
SIZ (r) -= (PTR (r)[SIZ (r)-1] == 0);
#endif
diff -r 3a9e770cd001 -r 274ed86df599 tests/mpz/t-bin.c
--- a/tests/mpz/t-bin.c Fri Jan 12 12:51:19 2018 +0100
+++ b/tests/mpz/t-bin.c Mon Jan 15 20:42:23 2018 +0100
@@ -143,9 +143,8 @@
unsigned long k;
mpz_init (n);
- mpz_init (want);
- mpz_set_ui (want, (unsigned long) 2);
+ mpz_init_set_ui (want, (unsigned long) 2);
for (k = 1; k < count; k++)
{
mpz_set_ui (n, 2*k);
@@ -166,18 +165,17 @@
void
randomwalk (int count)
{
- mpz_t n_z, want;
+ mpz_t n_z, want, tmp;
unsigned long n, k, i, r;
int tests;
gmp_randstate_ptr rands;
rands = RANDS;
mpz_init (n_z);
- mpz_init (want);
k = 3;
n = 12;
- mpz_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */
+ mpz_init_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */
for (tests = 1; tests < count; tests++)
{
@@ -201,6 +199,80 @@
try_mpz_bin_uiui (want, n, k);
}
+ k = 2;
+ mpz_urandomb (n_z, rands, 200);
+ mpz_mul (want, n_z, n_z); /* want = n_z ^ 2 */
+ mpz_sub (want, want, n_z); /* want = n_z ^ 2 - n_z = n_z (n_z- 1) */
+ mpz_tdiv_q_2exp (want, want, 1); /* want = n_z (n_z- 1) / 2 = binomial (n_z, 2) */
+ mpz_init (tmp);
+ for (tests = 1; tests < count; tests++)
+ {
+ r = gmp_urandomm_ui (rands, 62) + 1;
+ for (i = r & 7; i > 0; i--)
+ {
+ k++;
+ mpz_add_ui (n_z, n_z, 1);
+ mpz_mul (want, want, n_z);
+ mpz_tdiv_q_ui (want, want, k);
+ }
+ for (i = r >> 3; i > 0; i--)
+ {
+ mpz_add_ui (n_z, n_z, 1);
+ mpz_mul (want, want, n_z);
+ mpz_sub_ui (tmp, n_z, k);
+ mpz_tdiv_q (want, want, tmp);
+ }
+
+ try_mpz_bin_ui (want, n_z, k);
+ }
+
+ mpz_clear (tmp);
+ mpz_clear (n_z);
+ mpz_clear (want);
+}
+
+/* Test some random bin(n,k) cases. This produces some biggish
+ numbers to exercise the limb accumulating code. */
+void
+randomwalk_down (int count)
+{
+ mpz_t n_z, want, tmp;
+ unsigned long n, k, i, r;
+ int tests;
+ gmp_randstate_ptr rands;
+
+ rands = RANDS;
+ mpz_init (n_z);
+ mpz_init (tmp);
+
+ k = 2;
+ n = ULONG_MAX;
+ mpz_init_set_ui (want, n);
+ mpz_mul_ui (want, want, n >> 1);
+
+ for (tests = 1; tests < count; tests++)
+ {
+ r = gmp_urandomm_ui (rands, 62) + 1;
+ for (i = r & 7; i > 0; i--)
+ {
+ mpz_mul_ui (want, want, n - k);
+ ++k;
+ mpz_tdiv_q_ui (want, want, k);
+ }
+ for (i = r >> 3; i > 0; i--)
+ {
+ mpz_mul_ui (want, want, n - k);
+ mpz_tdiv_q_ui (want, want, n);
+ --n;
+ }
+
+ mpz_set_ui (n_z, n);
+ try_mpz_bin_ui (want, n_z, n - k);
+
+ try_mpz_bin_uiui (want, n, n - k);
+ }
+
+ mpz_clear (tmp);
mpz_clear (n_z);
mpz_clear (want);
}
@@ -259,6 +331,7 @@
smallexaustive (count >> 4);
twos (count >> 1);
randomwalk (count - (count >> 1));
+ randomwalk_down (count >> 1);
tests_end ();
exit (0);
More information about the gmp-commit
mailing list