[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Mar 15 21:34:06 UTC 2014
details: /var/hg/gmp/rev/8933187ab2a6
changeset: 16340:8933187ab2a6
user: Torbjorn Granlund <tege at gmplib.org>
date: Sat Mar 15 22:32:34 2014 +0100
description:
Retune.
details: /var/hg/gmp/rev/430bef4bae3e
changeset: 16341:430bef4bae3e
user: Torbjorn Granlund <tege at gmplib.org>
date: Sat Mar 15 22:34:03 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/ev6/gmp-mparam.h | 229 ++++++++++++++++++++++---------------------
5 files changed, 134 insertions(+), 123 deletions(-)
diffs (truncated from 392 to 300 lines):
diff -r 03c0799f3dc0 -r 430bef4bae3e ChangeLog
--- a/ChangeLog Sat Mar 15 21:26:50 2014 +0100
+++ b/ChangeLog Sat Mar 15 22:34:03 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 03c0799f3dc0 -r 430bef4bae3e mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Sat Mar 15 21:26:50 2014 +0100
+++ b/mini-gmp/mini-gmp.c Sat Mar 15 22:34:03 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 03c0799f3dc0 -r 430bef4bae3e mini-gmp/mini-gmp.h
--- a/mini-gmp/mini-gmp.h Sat Mar 15 21:26:50 2014 +0100
+++ b/mini-gmp/mini-gmp.h Sat Mar 15 22:34:03 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 03c0799f3dc0 -r 430bef4bae3e mini-gmp/tests/t-pprime_p.c
--- a/mini-gmp/tests/t-pprime_p.c Sat Mar 15 21:26:50 2014 +0100
+++ b/mini-gmp/tests/t-pprime_p.c Sat Mar 15 22:34:03 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 03c0799f3dc0 -r 430bef4bae3e mpn/alpha/ev6/gmp-mparam.h
--- a/mpn/alpha/ev6/gmp-mparam.h Sat Mar 15 21:26:50 2014 +0100
+++ b/mpn/alpha/ev6/gmp-mparam.h Sat Mar 15 22:34:03 2014 +0100
@@ -1,7 +1,7 @@
/* 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.
@@ -35,86 +35,89 @@
#define DIVEXACT_BY3_METHOD 0 /* override ../diveby3.asm */
/* 500 MHz 21164 (agnesi.math.su.se) */
-
-/* Generated by tuneup.c, 2009-11-29, gcc 3.3 */
+/* FFT tuning limit = 20000000 */
+/* Generated by tuneup.c, 2014-03-14, gcc 3.3 */
#define DIVREM_1_NORM_THRESHOLD 0 /* preinv always */
#define DIVREM_1_UNNORM_THRESHOLD 0 /* always */
#define MOD_1_1P_METHOD 2
#define MOD_1_NORM_THRESHOLD 0 /* always */
#define MOD_1_UNNORM_THRESHOLD 0 /* always */
-#define MOD_1N_TO_MOD_1_1_THRESHOLD 3
+#define MOD_1N_TO_MOD_1_1_THRESHOLD 4
#define MOD_1U_TO_MOD_1_1_THRESHOLD 2
#define MOD_1_1_TO_MOD_1_2_THRESHOLD 10
-#define MOD_1_2_TO_MOD_1_4_THRESHOLD 17
+#define MOD_1_2_TO_MOD_1_4_THRESHOLD 21
#define PREINV_MOD_1_TO_MOD_1_THRESHOLD 7
#define USE_PREINV_DIVREM_1 1 /* preinv always */
+#define DIV_QR_1N_PI1_METHOD 2
+#define DIV_QR_1_NORM_THRESHOLD 5
+#define DIV_QR_1_UNNORM_THRESHOLD 1
#define DIV_QR_2_PI2_THRESHOLD 8
#define DIVEXACT_1_THRESHOLD 0 /* always */
-#define BMOD_1_TO_MOD_1_THRESHOLD 19
+#define BMOD_1_TO_MOD_1_THRESHOLD 20
#define MUL_TOOM22_THRESHOLD 32
-#define MUL_TOOM33_THRESHOLD 105
-#define MUL_TOOM44_THRESHOLD 166
-#define MUL_TOOM6H_THRESHOLD 232
+#define MUL_TOOM33_THRESHOLD 117
+#define MUL_TOOM44_THRESHOLD 124
+#define MUL_TOOM6H_THRESHOLD 230
#define MUL_TOOM8H_THRESHOLD 357
-#define MUL_TOOM32_TO_TOOM43_THRESHOLD 96
-#define MUL_TOOM32_TO_TOOM53_THRESHOLD 110
-#define MUL_TOOM42_TO_TOOM53_THRESHOLD 93
-#define MUL_TOOM42_TO_TOOM63_THRESHOLD 113
-#define MUL_TOOM43_TO_TOOM54_THRESHOLD 133
+#define MUL_TOOM32_TO_TOOM43_THRESHOLD 97
+#define MUL_TOOM32_TO_TOOM53_THRESHOLD 107
+#define MUL_TOOM42_TO_TOOM53_THRESHOLD 88
+#define MUL_TOOM42_TO_TOOM63_THRESHOLD 105
+#define MUL_TOOM43_TO_TOOM54_THRESHOLD 136
-#define SQR_BASECASE_THRESHOLD 4
-#define SQR_TOOM2_THRESHOLD 60
-#define SQR_TOOM3_THRESHOLD 102
-#define SQR_TOOM4_THRESHOLD 155
-#define SQR_TOOM6_THRESHOLD 306
-#define SQR_TOOM8_THRESHOLD 333
+#define SQR_BASECASE_THRESHOLD 0 /* always */
+#define SQR_TOOM2_THRESHOLD 59
+#define SQR_TOOM3_THRESHOLD 123
+#define SQR_TOOM4_THRESHOLD 163
+#define SQR_TOOM6_THRESHOLD 333
+#define SQR_TOOM8_THRESHOLD 0 /* always */
#define MULMID_TOOM42_THRESHOLD 52
-#define MULMOD_BNM1_THRESHOLD 15
-#define SQRMOD_BNM1_THRESHOLD 23
+#define MULMOD_BNM1_THRESHOLD 19
+#define SQRMOD_BNM1_THRESHOLD 5
-#define MUL_FFT_MODF_THRESHOLD 412 /* k = 5 */
+#define MUL_FFT_MODF_THRESHOLD 468 /* k = 5 */
#define MUL_FFT_TABLE3 \
- { { 480, 5}, { 18, 6}, { 10, 5}, { 21, 6}, \
- { 11, 5}, { 23, 6}, { 12, 5}, { 25, 6}, \
- { 19, 7}, { 10, 6}, { 25, 7}, { 13, 6}, \
- { 27, 7}, { 14, 6}, { 29, 7}, { 25, 8}, \
- { 13, 7}, { 29, 8}, { 15, 7}, { 32, 8}, \
- { 17, 7}, { 35, 8}, { 19, 7}, { 39, 8}, \
- { 29, 9}, { 15, 8}, { 37, 9}, { 19, 8}, \
- { 41, 9}, { 23, 8}, { 51, 9}, { 27, 8}, \
- { 55, 9}, { 31, 8}, { 63, 9}, { 35, 8}, \
+ { { 468, 5}, { 19, 6}, { 10, 5}, { 21, 6}, \
+ { 11, 5}, { 23, 6}, { 19, 7}, { 10, 6}, \
+ { 24, 7}, { 13, 6}, { 27, 7}, { 14, 6}, \
+ { 29, 7}, { 17, 6}, { 35, 7}, { 29, 8}, \
+ { 15, 7}, { 32, 8}, { 17, 7}, { 35, 8}, \
+ { 19, 7}, { 39, 8}, { 29, 9}, { 15, 8}, \
+ { 35, 9}, { 19, 8}, { 41, 9}, { 23, 8}, \
+ { 51, 9}, { 27, 8}, { 55, 9}, { 35, 8}, \
{ 71, 9}, { 39,10}, { 23, 9}, { 55,10}, \
- { 31, 9}, { 67,10}, { 39, 9}, { 83,10}, \
- { 47, 9}, { 99,10}, { 55,11}, { 31,10}, \
+ { 31, 9}, { 67,10}, { 39, 9}, { 79,10}, \
+ { 47, 9}, { 95,10}, { 55,11}, { 31,10}, \
{ 79,11}, { 47,10}, { 103,12}, { 31,11}, \
{ 63,10}, { 135,11}, { 79,10}, { 167,11}, \
- { 95,10}, { 191,11}, { 111,12}, { 63,11}, \
- { 127,10}, { 255,11}, { 143,10}, { 287, 9}, \
- { 575,11}, { 159,10}, { 319,12}, { 95,11}, \
- { 191,10}, { 383,11}, { 207,13}, { 63,12}, \
- { 127,11}, { 255,10}, { 511,11}, { 271,10}, \
- { 543,11}, { 287,10}, { 575,12}, { 159,11}, \
- { 319,10}, { 639,11}, { 351,10}, { 703,12}, \
- { 191,11}, { 383,10}, { 767,11}, { 415,10}, \
- { 831,11}, { 447,13}, { 127,12}, { 255,11}, \
- { 543,12}, { 287,11}, { 575,10}, { 1151,12}, \
- { 319,11}, { 639,12}, { 351,11}, { 703,13}, \
- { 191,12}, { 383,11}, { 767,12}, { 415,11}, \
- { 831,12}, { 447,11}, { 895,14}, { 127,13}, \
- { 255,12}, { 543,11}, { 1087,12}, { 575,11}, \
- { 1151,12}, { 607,13}, { 319,12}, { 671,11}, \
- { 1343,12}, { 703,13}, { 383,12}, { 831,13}, \
- { 447,12}, { 927,14}, { 255,13}, { 511,12}, \
- { 1087,13}, { 575,12}, { 1151,13}, { 639,12}, \
- { 1279,13}, { 703,12}, { 1407,14}, { 383,13}, \
- { 767,15}, { 255,14}, { 511,13}, { 1215,14}, \
- { 639,13}, { 1407,14}, { 767,13}, { 1663,14}, \
- { 895,13}, { 1791,15}, { 32768,16}, { 65536,17}, \
+ { 95,10}, { 199,11}, { 111,12}, { 63,11}, \
+ { 143,10}, { 287, 9}, { 575,11}, { 159,10}, \
+ { 319,12}, { 95,11}, { 191,10}, { 383,11}, \
+ { 207,13}, { 63,12}, { 127,11}, { 255,10}, \
+ { 511,11}, { 271,10}, { 543,11}, { 287,10}, \
+ { 575,12}, { 159,11}, { 319,10}, { 639,11}, \
+ { 335,10}, { 671,11}, { 351,10}, { 703,12}, \
+ { 191,11}, { 383,10}, { 767,11}, { 415,12}, \
+ { 223,11}, { 447,13}, { 127,12}, { 255,11}, \
+ { 543,12}, { 287,11}, { 575,10}, { 1151,11}, \
+ { 607,12}, { 319,11}, { 671,12}, { 351,11}, \
+ { 703,13}, { 191,12}, { 383,11}, { 767,12}, \
+ { 415,11}, { 831,12}, { 447,14}, { 127,13}, \
+ { 255,12}, { 575,11}, { 1151,12}, { 607,13}, \
+ { 319,12}, { 735,13}, { 383,12}, { 767,11}, \
+ { 1535,12}, { 831,13}, { 447,12}, { 959,14}, \
+ { 255,13}, { 511,12}, { 1087,13}, { 575,12}, \
+ { 1215,13}, { 639,12}, { 1343,13}, { 703,12}, \
+ { 1407,14}, { 383,13}, { 767,12}, { 1535,13}, \
+ { 831,12}, { 1663,13}, { 959,15}, { 255,14}, \
+ { 511,13}, { 1215,14}, { 639,13}, { 1407,14}, \
+ { 767,13}, { 1663,14}, { 895,13}, { 1855,15}, \
+ { 511,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 151
@@ -122,83 +125,85 @@
#define SQR_FFT_MODF_THRESHOLD 412 /* k = 5 */
#define SQR_FFT_TABLE3 \
- { { 476, 5}, { 19, 6}, { 10, 5}, { 23, 6}, \
- { 12, 5}, { 25, 6}, { 27, 7}, { 14, 6}, \
- { 29, 7}, { 28, 8}, { 15, 7}, { 31, 8}, \
- { 29, 9}, { 15, 8}, { 35, 9}, { 19, 8}, \
- { 41, 9}, { 23, 8}, { 49, 9}, { 27,10}, \
- { 15, 9}, { 35, 8}, { 71, 9}, { 39,10}, \
+ { { 412, 5}, { 19, 6}, { 10, 5}, { 21, 6}, \
+ { 11, 5}, { 23, 6}, { 12, 5}, { 25, 6}, \
+ { 27, 7}, { 14, 6}, { 29, 7}, { 28, 8}, \
+ { 15, 7}, { 31, 8}, { 17, 7}, { 36, 8}, \
+ { 19, 7}, { 39, 8}, { 29, 9}, { 15, 8}, \
+ { 35, 9}, { 19, 8}, { 41, 9}, { 23, 8}, \
+ { 49, 9}, { 27,10}, { 15, 9}, { 39,10}, \
{ 23, 9}, { 51,11}, { 15,10}, { 31, 9}, \
{ 67,10}, { 39, 9}, { 79,10}, { 47, 9}, \
{ 95,10}, { 55,11}, { 31,10}, { 79,11}, \
- { 47,10}, { 103,12}, { 31,11}, { 63,10}, \
- { 135,11}, { 79,10}, { 159, 9}, { 319,11}, \
- { 95,10}, { 191, 9}, { 383,11}, { 111,12}, \
- { 63,11}, { 127,10}, { 255, 9}, { 511,10}, \
+ { 47,10}, { 95,12}, { 31,11}, { 63,10}, \
+ { 127, 9}, { 255,11}, { 79,10}, { 159, 9}, \
+ { 319,10}, { 167,11}, { 95,10}, { 191, 9}, \
+ { 383,11}, { 111,12}, { 63,11}, { 127,10}, \
{ 271,11}, { 143,10}, { 287, 9}, { 575,10}, \
{ 303,11}, { 159,10}, { 319,12}, { 95,11}, \
- { 191,10}, { 383, 9}, { 767,13}, { 63,12}, \
+ { 191,10}, { 383,11}, { 207,13}, { 63,12}, \
{ 127,11}, { 255,10}, { 511,11}, { 271,10}, \
{ 543,11}, { 287,10}, { 575,11}, { 303,12}, \
{ 159,11}, { 319,10}, { 639,11}, { 335,10}, \
- { 671,11}, { 351,10}, { 703,11}, { 367,10}, \
- { 735,12}, { 191,11}, { 383,10}, { 767,11}, \
- { 415,10}, { 831,11}, { 447,10}, { 895,13}, \
- { 127,12}, { 255,11}, { 543,12}, { 287,11}, \
- { 575,10}, { 1151,11}, { 607,12}, { 319,11}, \
- { 671,12}, { 351,11}, { 735,13}, { 191,12}, \
+ { 671,11}, { 351,10}, { 703,11}, { 367,12}, \
+ { 191,11}, { 383,10}, { 767,11}, { 415,12}, \
+ { 223,11}, { 447,13}, { 127,12}, { 255,11}, \
+ { 543,12}, { 287,11}, { 575,10}, { 1151,11}, \
+ { 607,12}, { 319,11}, { 639,10}, { 1279,11}, \
+ { 671,12}, { 351,11}, { 703,13}, { 191,12}, \
{ 383,11}, { 767,12}, { 415,11}, { 831,12}, \
{ 447,11}, { 895,12}, { 479,14}, { 127,13}, \
More information about the gmp-commit
mailing list