[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Mar 14 12:16:07 UTC 2014
details: /var/hg/gmp/rev/013f1cd73c4d
changeset: 16336:013f1cd73c4d
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Mar 14 13:15:24 2014 +0100
description:
Retune.
details: /var/hg/gmp/rev/e3af5e27e3e1
changeset: 16337:e3af5e27e3e1
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Mar 14 13:16:04 2014 +0100
description:
Trivial merge.
diffstat:
ChangeLog | 4 +
mini-gmp/mini-gmp.c | 19 +-
mini-gmp/mini-gmp.h | 3 +-
mini-gmp/tests/t-pprime_p.c | 2 +-
mpn/alpha/ev5/gmp-mparam.h | 143 +++++++++---------
mpn/arm/v7a/cora15/gmp-mparam.h | 102 +++++++------
mpn/arm/v7a/cora9/gmp-mparam.h | 116 ++++++++------
mpn/ia64/gmp-mparam.h | 95 +++++++-----
mpn/powerpc32/gmp-mparam.h | 80 ++++++----
mpn/powerpc32/p4/gmp-mparam.h | 210 +++++++++++++++++----------
mpn/powerpc64/mode64/p4/gmp-mparam.h | 4 +-
mpn/powerpc64/mode64/p7/gmp-mparam.h | 161 +++++++++++++--------
mpn/s390_32/esame/gmp-mparam.h | 137 +++++++++--------
mpn/s390_64/z10/gmp-mparam.h | 3 +-
mpn/sparc64/ultrasparc34/gmp-mparam.h | Bin
mpn/x86/bd2/gmp-mparam.h | 155 +++++++++++---------
mpn/x86/bobcat/gmp-mparam.h | 40 +++--
mpn/x86/core2/gmp-mparam.h | 215 ++++++++++++++++++-----------
mpn/x86/coreisbr/gmp-mparam.h | 195 ++++++++++++++++---------
mpn/x86/k10/gmp-mparam.h | 219 ++++++++++++++++++-----------
mpn/x86/k7/gmp-mparam.h | 240 +++++++++++++++++---------------
mpn/x86/k8/gmp-mparam.h | 4 +-
mpn/x86/pentium4/sse2/gmp-mparam.h | 166 +++++++++++----------
mpn/x86_64/atom/gmp-mparam.h | 203 ++++++++++++++++-----------
mpn/x86_64/bd1/gmp-mparam.h | 249 +++++++++++++++++++++------------
mpn/x86_64/bd2/gmp-mparam.h | 189 ++++++++++++++-----------
mpn/x86_64/bobcat/gmp-mparam.h | 155 +++++++++++---------
mpn/x86_64/core2/gmp-mparam.h | 192 +++++++++++++++----------
mpn/x86_64/coreihwl/gmp-mparam.h | 150 +++++++++++---------
mpn/x86_64/coreinhm/gmp-mparam.h | 3 +-
mpn/x86_64/coreisbr/gmp-mparam.h | 156 ++++++++++++---------
mpn/x86_64/k10/gmp-mparam.h | 127 +++++++++--------
mpn/x86_64/k8/gmp-mparam.h | 143 ++++++++++--------
mpn/x86_64/nano/gmp-mparam.h | 180 +++++++++++++-----------
mpn/x86_64/pentium4/gmp-mparam.h | 173 ++++++++++++----------
35 files changed, 2435 insertions(+), 1798 deletions(-)
diffs (truncated from 5608 to 300 lines):
diff -r 3f9086cd12d3 -r e3af5e27e3e1 ChangeLog
--- a/ChangeLog Wed Mar 12 20:57:10 2014 +0100
+++ b/ChangeLog Fri Mar 14 13:16:04 2014 +0100
@@ -1,3 +1,7 @@
+2014-02-21 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp/mini-gmp.c (mpz_probab_prime_p): Micro-optimisation.
+
2014-03-12 Torbjorn Granlund <tege at gmplib.org>
* mpn/x86/bd2/gmp-mparam.h: New file.
diff -r 3f9086cd12d3 -r e3af5e27e3e1 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Wed Mar 12 20:57:10 2014 +0100
+++ b/mini-gmp/mini-gmp.c Fri Mar 14 13:16:04 2014 +0100
@@ -3363,7 +3363,7 @@
gmp_millerrabin (const mpz_t n, const mpz_t nm1, mpz_t y,
const mpz_t q, mp_bitcnt_t k)
{
- mp_bitcnt_t i;
+ assert (k > 0);
/* Caller must initialize y to the base. */
mpz_powm (y, y, q, n);
@@ -3371,12 +3371,15 @@
if (mpz_cmp_ui (y, 1) == 0 || mpz_cmp (y, nm1) == 0)
return 1;
- for (i = 1; i < k; i++)
+ while (--k > 0)
{
mpz_powm_ui (y, y, 2, n);
if (mpz_cmp (y, nm1) == 0)
return 1;
- if (mpz_cmp_ui (y, 1) == 0)
+ /* y == 1 means that the previous y was a non-trivial square root
+ of 1 (mod n). y == 0 means that n is a power of the base.
+ In either case, n is not prime. */
+ if (mpz_cmp_ui (y, 1) <= 0)
return 0;
}
return 0;
@@ -3427,21 +3430,21 @@
mpz_init (y);
/* Find q and k, where q is odd and n = 1 + 2**k * q. */
- mpz_abs (nm1, n);
- mpz_sub_ui (nm1, nm1, 1);
+ nm1->_mp_size = mpz_abs_sub_ui (nm1, n, 1);
k = mpz_scan1 (nm1, 0);
mpz_tdiv_q_2exp (q, nm1, k);
- for (j = 0, is_prime = 1; is_prime && j < reps; j++)
+ for (j = 0, is_prime = 1; is_prime & (j < reps); j++)
{
mpz_set_ui (y, (unsigned long) j*j+j+41);
if (mpz_cmp (y, nm1) >= 0)
{
- /* Don't try any further bases. */
+ /* Don't try any further bases. This "early" break does not affect
+ the result for any reasonable reps value (<=5000 was tested) */
assert (j >= 30);
break;
}
- is_prime &= gmp_millerrabin (n, nm1, y, q, k);
+ is_prime = gmp_millerrabin (n, nm1, y, q, k);
}
mpz_clear (nm1);
mpz_clear (q);
diff -r 3f9086cd12d3 -r e3af5e27e3e1 mini-gmp/mini-gmp.h
--- a/mini-gmp/mini-gmp.h Wed Mar 12 20:57:10 2014 +0100
+++ b/mini-gmp/mini-gmp.h Fri Mar 14 13:16:04 2014 +0100
@@ -215,8 +215,7 @@
void mpz_fac_ui (mpz_t, unsigned long);
void mpz_bin_uiui (mpz_t, unsigned long, unsigned long);
-int
-mpz_probab_prime_p (const mpz_t, int);
+int mpz_probab_prime_p (const mpz_t, int);
int mpz_tstbit (const mpz_t, mp_bitcnt_t);
void mpz_setbit (mpz_t, mp_bitcnt_t);
diff -r 3f9086cd12d3 -r e3af5e27e3e1 mini-gmp/tests/t-pprime_p.c
--- a/mini-gmp/tests/t-pprime_p.c Wed Mar 12 20:57:10 2014 +0100
+++ b/mini-gmp/tests/t-pprime_p.c Fri Mar 14 13:16:04 2014 +0100
@@ -93,7 +93,7 @@
mpz_init (n);
- for (i = 0; i < 300; i++)
+ for (i = 0; i < 1700; i++)
{
mpz_set_si (n, i);
check_pn (n, isprime (i));
diff -r 3f9086cd12d3 -r e3af5e27e3e1 mpn/alpha/ev5/gmp-mparam.h
--- a/mpn/alpha/ev5/gmp-mparam.h Wed Mar 12 20:57:10 2014 +0100
+++ b/mpn/alpha/ev5/gmp-mparam.h Fri Mar 14 13:16:04 2014 +0100
@@ -1,7 +1,7 @@
/* Alpha EV5 gmp-mparam.h -- Compiler/machine parameter header file.
-Copyright 1991, 1993, 1994, 1999-2002, 2004, 2005, 2008-2010 Free Software
-Foundation, Inc.
+Copyright 1991, 1993, 1994, 1999-2002, 2004, 2005, 2008-2010, 2014 Free
+Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -33,6 +33,7 @@
#define GMP_LIMB_BYTES 8
/* 600 MHz 21164A */
+/* FFT tuning limit = 5000000 */
/* Generated by tuneup.c, 2014-03-12, gcc 4.5 */
#define DIVREM_1_NORM_THRESHOLD 0 /* preinv always */
@@ -51,35 +52,35 @@
#define DIV_QR_1_UNNORM_THRESHOLD MP_SIZE_T_MAX /* never */
#define DIV_QR_2_PI2_THRESHOLD MP_SIZE_T_MAX /* never */
#define DIVEXACT_1_THRESHOLD 0 /* always */
-#define BMOD_1_TO_MOD_1_THRESHOLD 80
+#define BMOD_1_TO_MOD_1_THRESHOLD 76
#define MUL_TOOM22_THRESHOLD 14
-#define MUL_TOOM33_THRESHOLD 57
+#define MUL_TOOM33_THRESHOLD 50
#define MUL_TOOM44_THRESHOLD 118
#define MUL_TOOM6H_THRESHOLD 157
-#define MUL_TOOM8H_THRESHOLD 212
+#define MUL_TOOM8H_THRESHOLD 236
#define MUL_TOOM32_TO_TOOM43_THRESHOLD 73
#define MUL_TOOM32_TO_TOOM53_THRESHOLD 77
#define MUL_TOOM42_TO_TOOM53_THRESHOLD 81
#define MUL_TOOM42_TO_TOOM63_THRESHOLD 56
-#define MUL_TOOM43_TO_TOOM54_THRESHOLD 66
+#define MUL_TOOM43_TO_TOOM54_THRESHOLD 70
#define SQR_BASECASE_THRESHOLD 0 /* always */
-#define SQR_TOOM2_THRESHOLD 24
-#define SQR_TOOM3_THRESHOLD 74
-#define SQR_TOOM4_THRESHOLD 120
-#define SQR_TOOM6_THRESHOLD 166
-#define SQR_TOOM8_THRESHOLD 236
+#define SQR_TOOM2_THRESHOLD 22
+#define SQR_TOOM3_THRESHOLD 73
+#define SQR_TOOM4_THRESHOLD 178
+#define SQR_TOOM6_THRESHOLD 0 /* always */
+#define SQR_TOOM8_THRESHOLD 260
#define MULMID_TOOM42_THRESHOLD 18
-#define MULMOD_BNM1_THRESHOLD 10
-#define SQRMOD_BNM1_THRESHOLD 11
+#define MULMOD_BNM1_THRESHOLD 9
+#define SQRMOD_BNM1_THRESHOLD 12
-#define MUL_FFT_MODF_THRESHOLD 276 /* k = 5 */
+#define MUL_FFT_MODF_THRESHOLD 284 /* k = 5 */
#define MUL_FFT_TABLE3 \
- { { 276, 5}, { 11, 6}, { 6, 5}, { 13, 6}, \
+ { { 284, 5}, { 11, 6}, { 6, 5}, { 13, 6}, \
{ 7, 5}, { 15, 6}, { 13, 7}, { 7, 6}, \
{ 15, 7}, { 8, 6}, { 17, 7}, { 13, 8}, \
{ 7, 7}, { 17, 8}, { 9, 7}, { 20, 8}, \
@@ -102,85 +103,85 @@
{ 383,11}, { 207,10}, { 415,11}, { 223,13}, \
{ 63,11}, { 287,10}, { 575,12}, { 159,11}, \
{ 319,10}, { 639,11}, { 351,12}, { 191,11}, \
- { 415,12}, { 223,11}, { 479,12}, { 287,11}, \
- { 575,12}, { 351,13}, { 191,12}, { 479,13}, \
- { 255,12}, { 575,13}, { 8192,14}, { 16384,15}, \
+ { 415,12}, { 223,11}, { 447,10}, { 895,11}, \
+ { 479,12}, { 287,11}, { 575,12}, { 351,13}, \
+ { 191,12}, { 479,13}, { 255,12}, { 575,13}, \
+ { 319,12}, { 703,13}, { 383,12}, { 831,13}, \
+ { 447,14}, { 255,13}, { 8192,14}, { 16384,15}, \
{ 32768,16}, { 65536,17}, { 131072,18}, { 262144,19}, \
{ 524288,20}, {1048576,21}, {2097152,22}, {4194304,23}, \
{8388608,24} }
-#define MUL_FFT_TABLE3_SIZE 113
-#define MUL_FFT_THRESHOLD 3200
+#define MUL_FFT_TABLE3_SIZE 121
+#define MUL_FFT_THRESHOLD 4224
-#define SQR_FFT_MODF_THRESHOLD 236 /* k = 5 */
+#define SQR_FFT_MODF_THRESHOLD 240 /* k = 5 */
#define SQR_FFT_TABLE3 \
- { { 236, 5}, { 11, 6}, { 6, 5}, { 13, 6}, \
- { 7, 5}, { 15, 6}, { 17, 7}, { 9, 6}, \
- { 19, 7}, { 17, 8}, { 9, 7}, { 20, 8}, \
- { 11, 7}, { 23, 8}, { 13, 9}, { 7, 8}, \
- { 19, 9}, { 11, 8}, { 25,10}, { 7, 9}, \
- { 15, 8}, { 33, 9}, { 19, 8}, { 39, 9}, \
- { 23, 8}, { 47, 9}, { 27,10}, { 15, 9}, \
- { 39,10}, { 23, 9}, { 47,11}, { 15,10}, \
- { 31, 9}, { 67,10}, { 39, 9}, { 79,10}, \
- { 47,11}, { 31,10}, { 63, 9}, { 127, 8}, \
- { 255,10}, { 71, 9}, { 143, 8}, { 287,10}, \
- { 79,11}, { 47,12}, { 31,11}, { 63,10}, \
- { 127, 9}, { 255, 8}, { 511,10}, { 143, 9}, \
- { 287,11}, { 79,10}, { 159, 9}, { 319, 8}, \
- { 639,10}, { 175, 9}, { 351,11}, { 95,10}, \
- { 191, 9}, { 383,10}, { 207, 9}, { 415,11}, \
- { 111,10}, { 223,12}, { 63,11}, { 127,10}, \
- { 255,11}, { 143,10}, { 287, 9}, { 575,11}, \
- { 159,10}, { 319,11}, { 175,10}, { 351,12}, \
- { 95,11}, { 191,10}, { 383,11}, { 207,10}, \
- { 415,11}, { 223,13}, { 63,12}, { 127,11}, \
- { 287,10}, { 575,12}, { 159,11}, { 319,10}, \
- { 639,11}, { 351,12}, { 191,11}, { 415,12}, \
- { 223,11}, { 447,13}, { 127,12}, { 287,11}, \
- { 575,12}, { 319,11}, { 639,12}, { 351,13}, \
- { 191,12}, { 479,14}, { 127,13}, { 255,12}, \
- { 575,13}, { 8192,14}, { 16384,15}, { 32768,16}, \
- { 65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, \
- {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
-#define SQR_FFT_TABLE3_SIZE 116
-#define SQR_FFT_THRESHOLD 2240
+ { { 240, 5}, { 13, 6}, { 7, 5}, { 15, 6}, \
+ { 14, 5}, { 29, 7}, { 9, 6}, { 19, 7}, \
+ { 13, 6}, { 27, 8}, { 7, 7}, { 21, 8}, \
+ { 11, 7}, { 29, 8}, { 19, 9}, { 11, 8}, \
+ { 27,10}, { 7, 9}, { 15, 8}, { 33, 9}, \
+ { 19, 8}, { 39, 9}, { 23, 8}, { 47,10}, \
+ { 15, 9}, { 39,10}, { 23, 9}, { 47,11}, \
+ { 15,10}, { 31, 9}, { 67,10}, { 39, 9}, \
+ { 79,10}, { 47,11}, { 31,10}, { 63, 9}, \
+ { 127, 8}, { 255,10}, { 71, 9}, { 143, 8}, \
+ { 287,10}, { 79,11}, { 47,12}, { 31,11}, \
+ { 63,10}, { 127, 9}, { 255,10}, { 143, 9}, \
+ { 287,11}, { 79,10}, { 159, 9}, { 319,10}, \
+ { 175,11}, { 95,10}, { 191, 9}, { 383,10}, \
+ { 207, 9}, { 415,11}, { 111,10}, { 223,12}, \
+ { 63,11}, { 175,12}, { 95,11}, { 207,13}, \
+ { 63,12}, { 127,11}, { 287,12}, { 159,11}, \
+ { 351,12}, { 191,11}, { 415,12}, { 223,11}, \
+ { 447,13}, { 127,12}, { 351,13}, { 191,12}, \
+ { 383,11}, { 767,12}, { 415,11}, { 831,12}, \
+ { 447,14}, { 127,13}, { 255,12}, { 511,11}, \
+ { 1087,12}, { 575,13}, { 319,12}, { 703,13}, \
+ { 383,12}, { 831,13}, { 447,14}, { 255,13}, \
+ { 511,12}, { 1023,13}, { 8192,14}, { 16384,15}, \
+ { 32768,16}, { 65536,17}, { 131072,18}, { 262144,19}, \
+ { 524288,20}, {1048576,21}, {2097152,22}, {4194304,23}, \
+ {8388608,24} }
+#define SQR_FFT_TABLE3_SIZE 105
+#define SQR_FFT_THRESHOLD 3968
#define MULLO_BASECASE_THRESHOLD 0 /* always */
#define MULLO_DC_THRESHOLD 45
-#define MULLO_MUL_N_THRESHOLD 6253
+#define MULLO_MUL_N_THRESHOLD 8397
-#define DC_DIV_QR_THRESHOLD 48
-#define DC_DIVAPPR_Q_THRESHOLD 167
+#define DC_DIV_QR_THRESHOLD 47
+#define DC_DIVAPPR_Q_THRESHOLD 168
#define DC_BDIV_QR_THRESHOLD 47
-#define DC_BDIV_Q_THRESHOLD 108
+#define DC_BDIV_Q_THRESHOLD 110
#define INV_MULMOD_BNM1_THRESHOLD 26
-#define INV_NEWTON_THRESHOLD 187
-#define INV_APPR_THRESHOLD 173
+#define INV_NEWTON_THRESHOLD 189
+#define INV_APPR_THRESHOLD 181
-#define BINV_NEWTON_THRESHOLD 190
+#define BINV_NEWTON_THRESHOLD 196
#define REDC_1_TO_REDC_N_THRESHOLD 51
-#define MU_DIV_QR_THRESHOLD 998
-#define MU_DIVAPPR_Q_THRESHOLD 1078
+#define MU_DIV_QR_THRESHOLD 1558
+#define MU_DIVAPPR_Q_THRESHOLD 1558
#define MUPI_DIV_QR_THRESHOLD 90
-#define MU_BDIV_QR_THRESHOLD 872
-#define MU_BDIV_Q_THRESHOLD 942
+#define MU_BDIV_QR_THRESHOLD 855
+#define MU_BDIV_Q_THRESHOLD 1078
-#define POWM_SEC_TABLE 3,16,90,473,1167
+#define POWM_SEC_TABLE 1,16,90,452,1221
#define MATRIX22_STRASSEN_THRESHOLD 11
-#define HGCD_THRESHOLD 98
-#define HGCD_APPR_THRESHOLD 104
-#define HGCD_REDUCE_THRESHOLD 1494
-#define GCD_DC_THRESHOLD 268
-#define GCDEXT_DC_THRESHOLD 189
+#define HGCD_THRESHOLD 99
+#define HGCD_APPR_THRESHOLD 103
+#define HGCD_REDUCE_THRESHOLD 2899
+#define GCD_DC_THRESHOLD 283
+#define GCDEXT_DC_THRESHOLD 201
#define JACOBI_BASE_METHOD 3
-#define GET_STR_DC_THRESHOLD 15
+#define GET_STR_DC_THRESHOLD 13
#define GET_STR_PRECOMPUTE_THRESHOLD 28
#define SET_STR_DC_THRESHOLD 426
More information about the gmp-commit
mailing list