[Gmp-commit] /home/hgfiles/gmp: 5 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Thu Feb 25 22:32:26 CET 2010
details: /home/hgfiles/gmp/rev/2a0a81a7b006
changeset: 13463:2a0a81a7b006
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Feb 25 22:13:20 2010 +0100
description:
Retune.
details: /home/hgfiles/gmp/rev/13e7c3444851
changeset: 13464:13e7c3444851
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Feb 25 22:15:59 2010 +0100
description:
Retune.
details: /home/hgfiles/gmp/rev/c164d4ff8998
changeset: 13465:c164d4ff8998
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Feb 25 22:26:17 2010 +0100
description:
Retune.
details: /home/hgfiles/gmp/rev/8e89484b0fec
changeset: 13466:8e89484b0fec
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Feb 25 22:28:54 2010 +0100
description:
Retune.
details: /home/hgfiles/gmp/rev/0334496da77e
changeset: 13467:0334496da77e
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Feb 25 22:32:24 2010 +0100
description:
Trivial merge.
diffstat:
ChangeLog | 3 +
mpn/pa32/hppa2_0/gmp-mparam.h | 6 +-
mpn/powerpc64/mode64/p5/gmp-mparam.h | 24 ++++----
mpn/x86/p6/sse2/gmp-mparam.h | 16 +++---
mpn/x86_64/atom/gmp-mparam.h | 10 +-
tests/mpz/t-jac.c | 96 ++++++++++++++++++++++++++++++++++++
6 files changed, 127 insertions(+), 28 deletions(-)
diffs (278 lines):
diff -r 7f50d4ccfd05 -r 0334496da77e ChangeLog
--- a/ChangeLog Thu Feb 25 21:26:35 2010 +0100
+++ b/ChangeLog Thu Feb 25 22:32:24 2010 +0100
@@ -1,5 +1,8 @@
2010-02-25 Niels Möller <nisse at lysator.liu.se>
+ * tests/mpz/t-jac.c (ref_jacobi): New reference implementation,
+ using factorization and legendre symbols computed by powm.
+
* tests/devel/try.c (param_init, call): Don't pass negative values
for the second argument to mpz_jacobi and refmpz_jacobi.
diff -r 7f50d4ccfd05 -r 0334496da77e mpn/pa32/hppa2_0/gmp-mparam.h
--- a/mpn/pa32/hppa2_0/gmp-mparam.h Thu Feb 25 21:26:35 2010 +0100
+++ b/mpn/pa32/hppa2_0/gmp-mparam.h Thu Feb 25 22:32:24 2010 +0100
@@ -125,18 +125,18 @@
#define MULLO_BASECASE_THRESHOLD 0 /* always */
#define MULLO_DC_THRESHOLD 90
-#define MULLO_MUL_N_THRESHOLD 4167
+#define MULLO_MUL_N_THRESHOLD 3574
#define DC_DIV_QR_THRESHOLD 100
#define DC_DIVAPPR_Q_THRESHOLD 342
#define DC_BDIV_QR_THRESHOLD 119
#define DC_BDIV_Q_THRESHOLD 246
-#define INV_MULMOD_BNM1_THRESHOLD 12
+#define INV_MULMOD_BNM1_THRESHOLD 34
#define INV_NEWTON_THRESHOLD 274
#define INV_APPR_THRESHOLD 268
-#define BINV_NEWTON_THRESHOLD 327
+#define BINV_NEWTON_THRESHOLD 278
#define REDC_1_TO_REDC_N_THRESHOLD 70
#define MU_DIV_QR_THRESHOLD 979
diff -r 7f50d4ccfd05 -r 0334496da77e mpn/powerpc64/mode64/p5/gmp-mparam.h
--- a/mpn/powerpc64/mode64/p5/gmp-mparam.h Thu Feb 25 21:26:35 2010 +0100
+++ b/mpn/powerpc64/mode64/p5/gmp-mparam.h Thu Feb 25 22:32:24 2010 +0100
@@ -28,15 +28,15 @@
#define MOD_1N_TO_MOD_1_1_THRESHOLD 13
#define MOD_1U_TO_MOD_1_1_THRESHOLD 10
#define MOD_1_1_TO_MOD_1_2_THRESHOLD 0
-#define MOD_1_2_TO_MOD_1_4_THRESHOLD 20
-#define PREINV_MOD_1_TO_MOD_1_THRESHOLD 33
+#define MOD_1_2_TO_MOD_1_4_THRESHOLD 18
+#define PREINV_MOD_1_TO_MOD_1_THRESHOLD 17
#define USE_PREINV_DIVREM_1 0
#define DIVEXACT_1_THRESHOLD 0 /* always (native) */
#define BMOD_1_TO_MOD_1_THRESHOLD MP_SIZE_T_MAX /* never */
#define MUL_TOOM22_THRESHOLD 16
#define MUL_TOOM33_THRESHOLD 56
-#define MUL_TOOM44_THRESHOLD 154
+#define MUL_TOOM44_THRESHOLD 130
#define MUL_TOOM6H_THRESHOLD 206
#define MUL_TOOM8H_THRESHOLD 309
@@ -48,12 +48,12 @@
#define SQR_BASECASE_THRESHOLD 10
#define SQR_TOOM2_THRESHOLD 36
#define SQR_TOOM3_THRESHOLD 59
-#define SQR_TOOM4_THRESHOLD 112
-#define SQR_TOOM6_THRESHOLD 189
-#define SQR_TOOM8_THRESHOLD 309
+#define SQR_TOOM4_THRESHOLD 160
+#define SQR_TOOM6_THRESHOLD 204
+#define SQR_TOOM8_THRESHOLD 321
#define MULMOD_BNM1_THRESHOLD 13
-#define SQRMOD_BNM1_THRESHOLD 9
+#define SQRMOD_BNM1_THRESHOLD 13
#define MUL_FFT_MODF_THRESHOLD 348 /* k = 5 */
#define MUL_FFT_TABLE3 \
@@ -174,12 +174,12 @@
#define DC_BDIV_QR_THRESHOLD 47
#define DC_BDIV_Q_THRESHOLD 112
-#define INV_MULMOD_BNM1_THRESHOLD 107
-#define INV_NEWTON_THRESHOLD 130
-#define INV_APPR_THRESHOLD 117
+#define INV_MULMOD_BNM1_THRESHOLD 82
+#define INV_NEWTON_THRESHOLD 109
+#define INV_APPR_THRESHOLD 99
-#define BINV_NEWTON_THRESHOLD 246
-#define REDC_1_TO_REDC_N_THRESHOLD 54
+#define BINV_NEWTON_THRESHOLD 199
+#define REDC_1_TO_REDC_N_THRESHOLD 51
#define MU_DIV_QR_THRESHOLD 872
#define MU_DIVAPPR_Q_THRESHOLD 855
diff -r 7f50d4ccfd05 -r 0334496da77e mpn/x86/p6/sse2/gmp-mparam.h
--- a/mpn/x86/p6/sse2/gmp-mparam.h Thu Feb 25 21:26:35 2010 +0100
+++ b/mpn/x86/p6/sse2/gmp-mparam.h Thu Feb 25 22:32:24 2010 +0100
@@ -144,25 +144,25 @@
#define MULLO_BASECASE_THRESHOLD 0 /* always */
#define MULLO_DC_THRESHOLD 34
-#define MULLO_MUL_N_THRESHOLD 8907
+#define MULLO_MUL_N_THRESHOLD 13463
-#define DC_DIV_QR_THRESHOLD 19
+#define DC_DIV_QR_THRESHOLD 25
#define DC_DIVAPPR_Q_THRESHOLD 56
#define DC_BDIV_QR_THRESHOLD 60
#define DC_BDIV_Q_THRESHOLD 132
-#define INV_MULMOD_BNM1_THRESHOLD 117
-#define INV_NEWTON_THRESHOLD 81
+#define INV_MULMOD_BNM1_THRESHOLD 39
+#define INV_NEWTON_THRESHOLD 66
#define INV_APPR_THRESHOLD 61
#define BINV_NEWTON_THRESHOLD 276
#define REDC_1_TO_REDC_N_THRESHOLD 63
-#define MU_DIV_QR_THRESHOLD 1308
-#define MU_DIVAPPR_Q_THRESHOLD 998
+#define MU_DIV_QR_THRESHOLD 1142
+#define MU_DIVAPPR_Q_THRESHOLD 872
#define MUPI_DIV_QR_THRESHOLD 62
-#define MU_BDIV_QR_THRESHOLD 1442
-#define MU_BDIV_Q_THRESHOLD 1470
+#define MU_BDIV_QR_THRESHOLD 1308
+#define MU_BDIV_Q_THRESHOLD 1442
#define MATRIX22_STRASSEN_THRESHOLD 17
#define HGCD_THRESHOLD 60
diff -r 7f50d4ccfd05 -r 0334496da77e mpn/x86_64/atom/gmp-mparam.h
--- a/mpn/x86_64/atom/gmp-mparam.h Thu Feb 25 21:26:35 2010 +0100
+++ b/mpn/x86_64/atom/gmp-mparam.h Thu Feb 25 22:32:24 2010 +0100
@@ -34,7 +34,7 @@
#define MUL_TOOM22_THRESHOLD 10
#define MUL_TOOM33_THRESHOLD 66
-#define MUL_TOOM44_THRESHOLD 118
+#define MUL_TOOM44_THRESHOLD 82
#define MUL_TOOM6H_THRESHOLD 157
#define MUL_TOOM8H_THRESHOLD 236
@@ -50,8 +50,8 @@
#define SQR_TOOM6_THRESHOLD 226
#define SQR_TOOM8_THRESHOLD 333
-#define MULMOD_BNM1_THRESHOLD 9
-#define SQRMOD_BNM1_THRESHOLD 9
+#define MULMOD_BNM1_THRESHOLD 10
+#define SQRMOD_BNM1_THRESHOLD 11
#define MUL_FFT_MODF_THRESHOLD 212 /* k = 5 */
#define MUL_FFT_TABLE3 \
@@ -152,8 +152,8 @@
#define DC_BDIV_QR_THRESHOLD 27
#define DC_BDIV_Q_THRESHOLD 62
-#define INV_MULMOD_BNM1_THRESHOLD 100
-#define INV_NEWTON_THRESHOLD 147
+#define INV_MULMOD_BNM1_THRESHOLD 18
+#define INV_NEWTON_THRESHOLD 132
#define INV_APPR_THRESHOLD 108
#define BINV_NEWTON_THRESHOLD 165
diff -r 7f50d4ccfd05 -r 0334496da77e tests/mpz/t-jac.c
--- a/tests/mpz/t-jac.c Thu Feb 25 21:26:35 2010 +0100
+++ b/tests/mpz/t-jac.c Thu Feb 25 22:32:24 2010 +0100
@@ -719,6 +719,101 @@
}
+/* Assumes that b = prod p_k^e_k */
+int
+ref_jacobi (mpz_srcptr a, mpz_srcptr b, unsigned nprime,
+ mpz_t prime[], unsigned *exp)
+{
+ unsigned i;
+ int res;
+
+ for (i = 0, res = 1; i < nprime; i++)
+ if (exp[i])
+ {
+ int legendre = refmpz_legendre (a, prime[i]);
+ if (!legendre)
+ return 0;
+ if (exp[i] & 1)
+ res *= legendre;
+ }
+ return res;
+}
+
+void
+check_jacobi_factored (void)
+{
+#define PRIME_N 10
+#define PRIME_MAX_SIZE 50
+#define PRIME_MAX_EXP 4
+#define PRIME_A_COUNT 10
+#define PRIME_B_COUNT 5
+#define PRIME_MAX_B_SIZE 2000
+
+ gmp_randstate_ptr rands = RANDS;
+ mpz_t prime[PRIME_N];
+ unsigned exp[PRIME_N];
+ mpz_t a, b, t, bs;
+ unsigned i;
+
+ mpz_init (a);
+ mpz_init (b);
+ mpz_init (t);
+ mpz_init (bs);
+
+ /* Generate primes */
+ for (i = 0; i < PRIME_N; i++)
+ {
+ mp_size_t size;
+ mpz_init (prime[i]);
+ mpz_urandomb (bs, rands, 32);
+ size = mpz_get_ui (bs) % PRIME_MAX_SIZE + 2;
+ mpz_rrandomb (prime[i], rands, size);
+ if (mpz_cmp_ui (prime[i], 3) <= 0)
+ mpz_set_ui (prime[i], 3);
+ else
+ mpz_nextprime (prime[i], prime[i]);
+ }
+
+ for (i = 0; i < PRIME_B_COUNT; i++)
+ {
+ unsigned j, k;
+ mp_bitcnt_t bsize;
+
+ mpz_set_ui (b, 1);
+ bsize = 1;
+
+ for (j = 0; j < PRIME_N && bsize < PRIME_MAX_B_SIZE; j++)
+ {
+ mpz_urandomb (bs, rands, 32);
+ exp[j] = mpz_get_ui (bs) % PRIME_MAX_EXP;
+ mpz_pow_ui (t, prime[j], exp[j]);
+ mpz_mul (b, b, t);
+ bsize = mpz_sizeinbase (b, 2);
+ }
+ for (k = 0; k < PRIME_A_COUNT; k++)
+ {
+ int answer;
+ mpz_rrandomb (a, rands, bsize + 2);
+ answer = ref_jacobi (a, b, j, prime, exp);
+ try_all (a, b, answer);
+ }
+ }
+ for (i = 0; i < PRIME_N; i++)
+ mpz_clear (prime[i]);
+
+ mpz_clear (a);
+ mpz_clear (b);
+ mpz_clear (t);
+ mpz_clear (bs);
+
+#undef PRIME_N
+#undef PRIME_MAX_SIZE
+#undef PRIME_MAX_EXP
+#undef PRIME_A_COUNT
+#undef PRIME_B_COUNT
+#undef PRIME_MAX_B_SIZE
+}
+
int
main (int argc, char *argv[])
{
@@ -741,6 +836,7 @@
check_data ();
check_squares_zi ();
check_a_zero ();
+ check_jacobi_factored ();
tests_end ();
exit (0);
More information about the gmp-commit
mailing list