[Gmp-commit] /var/hg/gmp: Rewrite t-gcd.c.
mercurial at gmplib.org
mercurial at gmplib.org
Sun May 20 20:43:42 CEST 2012
details: /var/hg/gmp/rev/8957fc7608ad
changeset: 14989:8957fc7608ad
user: Torbjorn Granlund <tege at gmplib.org>
date: Sun May 20 20:43:40 2012 +0200
description:
Rewrite t-gcd.c.
diffstat:
ChangeLog | 4 +
tests/mpz/t-gcd.c | 237 ++++++++++++++++++++++++++++++++++-------------------
2 files changed, 154 insertions(+), 87 deletions(-)
diffs (truncated from 315 to 300 lines):
diff -r 73e19f007580 -r 8957fc7608ad ChangeLog
--- a/ChangeLog Sun May 20 14:45:15 2012 +0200
+++ b/ChangeLog Sun May 20 20:43:40 2012 +0200
@@ -1,3 +1,7 @@
+2012-05-20 Torbjorn Granlund <tege at gmplib.org>
+
+ * tests/mpz/t-gcd.c: Rewrite.
+
2012-05-19 Torbjorn Granlund <tege at gmplib.org>
* tests/mpz/t-gcd.c: Generate larger operands for better gcd code
diff -r 73e19f007580 -r 8957fc7608ad tests/mpz/t-gcd.c
--- a/tests/mpz/t-gcd.c Sun May 20 14:45:15 2012 +0200
+++ b/tests/mpz/t-gcd.c Sun May 20 20:43:40 2012 +0200
@@ -30,6 +30,25 @@
static int gcdext_valid_p (const mpz_t, const mpz_t, const mpz_t, const mpz_t);
+/* Keep one_test's variables global, so that we don't need
+ to reinitialize them for each test. */
+mpz_t gcd1, gcd2, s, temp1, temp2, temp3;
+
+#define MAX_SCHOENHAGE_THRESHOLD HGCD_REDUCE_THRESHOLD
+
+/* Define this to make all operands be large enough for Schoenhage gcd
+ to be used. */
+#ifndef WHACK_SCHOENHAGE
+#define WHACK_SCHOENHAGE 0
+#endif
+
+#if WHACK_SCHOENHAGE
+#define MIN_OPERAND_BITSIZE (MAX_SCHOENHAGE_THRESHOLD * GMP_NUMB_BITS)
+#else
+#define MIN_OPERAND_BITSIZE 1
+#endif
+
+
void
check_data (void)
{
@@ -47,10 +66,7 @@
mpz_t a, b, got, want;
int i;
- mpz_init (a);
- mpz_init (b);
- mpz_init (got);
- mpz_init (want);
+ mpz_inits (a, b, got, want, NULL);
for (i = 0; i < numberof (data); i++)
{
@@ -72,58 +88,154 @@
}
}
- mpz_clear (a);
- mpz_clear (b);
- mpz_clear (got);
- mpz_clear (want);
+ mpz_clears (a, b, got, want, NULL);
}
-/* Keep one_test's variables global, so that we don't need
- to reinitialize them for each test. */
-mpz_t gcd1, gcd2, s, t, temp1, temp2, temp3;
+void
+make_chain_operands (mpz_t ref, mpz_t a, mpz_t b, gmp_randstate_t rs, int nb1, int nb2, int chain_len)
+{
+ mpz_t bs, temp1, temp2;
+ int j;
-#define MAX_SCHOENHAGE_THRESHOLD HGCD_REDUCE_THRESHOLD
+ mpz_inits (bs, temp1, temp2, NULL);
-/* Define this to make all operands be large enough for Schoenhage gcd
- to be used. */
-#ifndef WHACK_SCHOENHAGE
-#define WHACK_SCHOENHAGE 0
-#endif
+ /* Generate a division chain backwards, allowing otherwise unlikely huge
+ quotients. */
-#if WHACK_SCHOENHAGE
-#define MIN_OPERAND_BITSIZE (MAX_SCHOENHAGE_THRESHOLD * GMP_NUMB_BITS)
-#else
-#define MIN_OPERAND_BITSIZE 1
-#endif
+ mpz_set_ui (a, 0);
+ mpz_urandomb (bs, rs, 32);
+ mpz_urandomb (bs, rs, mpz_get_ui (bs) % nb1 + 1);
+ mpz_rrandomb (b, rs, mpz_get_ui (bs));
+ mpz_add_ui (b, b, 1);
+ mpz_set (ref, b);
+
+ for (j = 0; j < chain_len; j++)
+ {
+ mpz_urandomb (bs, rs, 32);
+ mpz_urandomb (bs, rs, mpz_get_ui (bs) % nb2 + 1);
+ mpz_rrandomb (temp2, rs, mpz_get_ui (bs) + 1);
+ mpz_add_ui (temp2, temp2, 1);
+ mpz_mul (temp1, b, temp2);
+ mpz_add (a, a, temp1);
+
+ mpz_urandomb (bs, rs, 32);
+ mpz_urandomb (bs, rs, mpz_get_ui (bs) % nb2 + 1);
+ mpz_rrandomb (temp2, rs, mpz_get_ui (bs) + 1);
+ mpz_add_ui (temp2, temp2, 1);
+ mpz_mul (temp1, a, temp2);
+ mpz_add (b, b, temp1);
+ }
+
+ mpz_clears (bs, temp1, temp2, NULL);
+}
+
+/* Test operands from a table of seed data. This variant creates the operands
+ using plain ol' mpz_rrandomb. This is a hack for better coverage of the gcd
+ code, which depends on that the random number generators give the exact
+ numbers we expect. */
+void
+check_kolmo1 (void)
+{
+ static const struct {
+ unsigned int seed;
+ int nb;
+ const char *want;
+ } data[] = {
+ { 59618, 38208, "5"},
+ { 76521, 49024, "3"},
+ { 85869, 54976, "1"},
+ { 99449, 63680, "1"},
+ {112453, 72000, "1"}
+ };
+
+ gmp_randstate_t rs;
+ mpz_t bs, a, b, want;
+ int i, unb, vnb, nb;
+
+ gmp_randinit_default (rs);
+
+ mpz_inits (bs, a, b, want, NULL);
+
+ for (i = 0; i < numberof (data); i++)
+ {
+ nb = data[i].nb;
+
+ gmp_randseed_ui (rs, data[i].seed);
+
+ mpz_urandomb (bs, rs, 32);
+ unb = mpz_get_ui (bs) % nb;
+ mpz_urandomb (bs, rs, 32);
+ vnb = mpz_get_ui (bs) % nb;
+
+ mpz_rrandomb (a, rs, unb);
+ mpz_rrandomb (b, rs, vnb);
+
+ mpz_set_str_or_abort (want, data[i].want, 0);
+
+ one_test (a, b, want, -1);
+ }
+
+ mpz_clears (bs, a, b, want, NULL);
+ gmp_randclear (rs);
+}
+
+/* Test operands from a table of seed data. This variant creates the operands
+ using a division chain. This is a hack for better coverage of the gcd
+ code, which depends on that the random number generators give the exact
+ numbers we expect. */
+void
+check_kolmo2 (void)
+{
+ static const struct {
+ unsigned int seed;
+ int nb, chain_len;
+ } data[] = {
+ { 917, 15, 5 },
+ { 1032, 18, 6 },
+ { 1167, 18, 6 },
+ { 1174, 18, 6 },
+ { 1192, 18, 6 },
+ };
+
+ gmp_randstate_t rs;
+ mpz_t bs, a, b, want;
+ int i;
+
+ gmp_randinit_default (rs);
+
+ mpz_inits (bs, a, b, want, NULL);
+
+ for (i = 0; i < numberof (data); i++)
+ {
+ gmp_randseed_ui (rs, data[i].seed);
+ make_chain_operands (want, a, b, rs, data[i].nb, data[i].nb, data[i].chain_len);
+ one_test (a, b, want, -1);
+ }
+
+ mpz_clears (bs, a, b, want, NULL);
+ gmp_randclear (rs);
+}
int
main (int argc, char **argv)
{
mpz_t op1, op2, ref;
- int i, j, chain_len;
+ int i, chain_len;
gmp_randstate_ptr rands;
mpz_t bs;
unsigned long bsi, size_range;
- int reps = 200;
+ long int reps = 200;
tests_start ();
TESTS_REPS (reps, argv, argc);
rands = RANDS;
+ mpz_inits (bs, op1, op2, ref, gcd1, gcd2, temp1, temp2, temp3, s, NULL);
+
check_data ();
-
- mpz_init (bs);
- mpz_init (op1);
- mpz_init (op2);
- mpz_init (ref);
- mpz_init (gcd1);
- mpz_init (gcd2);
- mpz_init (temp1);
- mpz_init (temp2);
- mpz_init (temp3);
- mpz_init (s);
- mpz_init (t);
+ check_kolmo1 ();
+ check_kolmo2 ();
/* Testcase to exercise the u0 == u1 case in mpn_gcdext_lehmer_n. */
mpz_set_ui (op2, GMP_NUMB_MAX); /* FIXME: Huge limb doesn't always fit */
@@ -132,12 +244,6 @@
mpz_mul_ui (op2, op2, 2);
one_test (op1, op2, NULL, -1);
-#if 0
- mpz_set_str (op1, "4da8e405e0d2f70d6d679d3de08a5100a81ec2cff40f97b313ae75e1183f1df2b244e194ebb02a4ece50d943640a301f0f6cc7f539117b783c3f3a3f91649f8a00d2e1444d52722810562bce02fccdbbc8fe3276646e306e723dd3b", 16);
- mpz_set_str (op2, "76429e12e4fdd8929d89c21657097fbac09d1dc08cf7f1323a34e78ca34226e1a7a29b86fee0fa7fe2cc2a183d46d50df1fe7029590974ad7da77605f35f902cb8b9b8d22dd881eaae5919675d49a337145a029c3b33fc2b0", 16);
- one_test (op1, op2, NULL, -1);
-#endif
-
for (i = 0; i < reps; i++)
{
/* Generate plain operands with unknown gcd. These types of operands
@@ -172,60 +278,17 @@
/* Generate a division chain backwards, allowing otherwise unlikely huge
quotients. */
- mpz_set_ui (op1, 0);
- mpz_urandomb (bs, rands, 32);
- mpz_urandomb (bs, rands, mpz_get_ui (bs) % 16 + 1);
- mpz_rrandomb (op2, rands, mpz_get_ui (bs));
- mpz_add_ui (op2, op2, 1);
- mpz_set (ref, op2);
-
-#if WHACK_SCHOENHAGE
- chain_len = 1000000;
-#else
mpz_urandomb (bs, rands, 32);
chain_len = mpz_get_ui (bs) % LOG2C (GMP_NUMB_BITS * MAX_SCHOENHAGE_THRESHOLD);
mpz_urandomb (bs, rands, 32);
chain_len = mpz_get_ui (bs) % (1 << chain_len) / 32;
-#endif
- for (j = 0; j < chain_len; j++)
- {
- mpz_urandomb (bs, rands, 32);
- mpz_urandomb (bs, rands, mpz_get_ui (bs) % 12 + 1);
- mpz_rrandomb (temp2, rands, mpz_get_ui (bs) + 1);
- mpz_add_ui (temp2, temp2, 1);
- mpz_mul (temp1, op2, temp2);
- mpz_add (op1, op1, temp1);
+ make_chain_operands (ref, op1, op2, rands, 16, 12, chain_len);
- /* Don't generate overly huge operands. */
-/* if (SIZ (op1) > 2 * MAX_SCHOENHAGE_THRESHOLD)
- break; */
-
- mpz_urandomb (bs, rands, 32);
- mpz_urandomb (bs, rands, mpz_get_ui (bs) % 12 + 1);
- mpz_rrandomb (temp2, rands, mpz_get_ui (bs) + 1);
- mpz_add_ui (temp2, temp2, 1);
- mpz_mul (temp1, op1, temp2);
- mpz_add (op2, op2, temp1);
-
- /* Don't generate overly huge operands. */
-/* if (SIZ (op2) > 2 * MAX_SCHOENHAGE_THRESHOLD)
- break; */
- }
one_test (op1, op2, ref, i);
}
More information about the gmp-commit
mailing list