[Gmp-commit] /home/hgfiles/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Thu Dec 10 17:04:40 CET 2009
details: /home/hgfiles/gmp/rev/a339bbaca1a9
changeset: 13027:a339bbaca1a9
user: Niels M?ller <nisse at lysator.liu.se>
date: Thu Dec 10 16:31:07 2009 +0100
description:
Simpler but more trustworthy mpn_divexact.
details: /home/hgfiles/gmp/rev/6ab3c0c25b30
changeset: 13028:6ab3c0c25b30
user: Niels M?ller <nisse at lysator.liu.se>
date: Thu Dec 10 16:32:34 2009 +0100
description:
Simpler but more trustworthy mpn_divexact.
details: /home/hgfiles/gmp/rev/d48fdb0f5eef
changeset: 13029:d48fdb0f5eef
user: Niels M?ller <nisse at lysator.liu.se>
date: Thu Dec 10 17:04:34 2009 +0100
description:
Trivial merge
diffstat:
ChangeLog | 18 +++++++-
gmp-impl.h | 2 +-
mpn/alpha/ev5/gmp-mparam.h | 35 +++++++++-------
mpn/alpha/ev6/gmp-mparam.h | 16 ++++--
mpn/arm/gmp-mparam.h | 16 ++++--
mpn/generic/divexact.c | 75 ++++++++++++++++++++++++++++++++---
mpn/generic/gcdext.c | 61 +----------------------------
mpn/ia64/gmp-mparam.h | 16 ++++--
mpn/pa64/gmp-mparam.h | 13 +++--
mpn/powerpc32/750/gmp-mparam.h | 14 ++++--
mpn/powerpc32/gmp-mparam.h | 16 ++++--
mpn/powerpc64/mode64/p3/gmp-mparam.h | 14 ++++--
mpn/powerpc64/mode64/p4/gmp-mparam.h | 16 ++++--
mpn/powerpc64/mode64/p5/gmp-mparam.h | 16 ++++--
mpn/sparc64/gmp-mparam.h | 12 +++-
mpn/x86/atom/gmp-mparam.h | 16 ++++--
mpn/x86/k7/gmp-mparam.h | 18 +++++---
mpn/x86/p6/mmx/gmp-mparam.h | 16 ++++--
mpn/x86/p6/sse2/gmp-mparam.h | 16 ++++--
mpn/x86/pentium4/sse2/gmp-mparam.h | 18 +++++---
mpn/x86_64/atom/gmp-mparam.h | 16 ++++--
mpn/x86_64/core2/gmp-mparam.h | 16 ++++--
mpn/x86_64/corei/gmp-mparam.h | 20 +++++---
mpn/x86_64/gmp-mparam.h | 14 ++++--
mpn/x86_64/nano/gmp-mparam.h | 18 +++++---
mpn/x86_64/pentium4/gmp-mparam.h | 20 +++++---
26 files changed, 315 insertions(+), 213 deletions(-)
diffs (truncated from 912 to 300 lines):
diff -r 11b4d88d0e5b -r d48fdb0f5eef ChangeLog
--- a/ChangeLog Thu Dec 10 16:23:55 2009 +0100
+++ b/ChangeLog Thu Dec 10 17:04:34 2009 +0100
@@ -1,5 +1,17 @@
+2009-12-10 Torbjorn Granlund <tege at gmplib.org>
+
+ * mpn/*/gmp-mparam.h: Regenerate many of these files.
+
2009-12-10 Niels Möller <nisse at lysator.liu.se>
+ * gmp-impl.h (mpn_divexact): Removed scratch pointer from
+ prototype.
+ * mpn/generic/gcdext.c (divexact): Deleted, moved to...
+ * mpn/generic/divexact.c (mpn_divexact): New implementation (moved
+ from gcdext.c). The bidirectional divexact is kept but #if:ed out.
+ Interface change, since the new code doesn't take a scratch
+ argument.
+
* tests/mpn/t-mulmod_bnm1.c (main): Ensure thatn an >= bn. Lowered
MIN_N to 1. Various fixes to handle n == 1 properly.
@@ -52,9 +64,9 @@
* tune/speed.h (SPEED_ROUTINE_MPN_MULMOD_BNM1_ROUNDED): New define.
* tune/common.c (speed_mpn_mulmod_bnm1_rounded): New function.
- * tune/speed.c (routine): Add mpn_mulmod_bnm1_rounded for measuring
+ * tune/speed.c (routine): Add mpn_mulmod_bnm1_rounded for measuring
mpn_mulmod_bnm1 at recommended sizes.
-
+
* mpn/generic/mulmod_bnm1.c (mpn_mulmod_bnm1_next_size): Rewrite.
(mpn_bc_mulmod_bnm1): Use mpn_add_n instead of mpn_add.
@@ -165,7 +177,7 @@
Added various masking tricks.
* mpn/generic/gcdext_1.c (mpn_gcdext_1) [GCDEXT_1_USE_BINARY]:
- Reimplemented binary gcdext, with proper canonicalization.
+ Reimplemented binary gcdext, with proper canonicalization.
* mpn/generic/gcdext_lehmer.c (mpn_gcdext_lehmer_n): Handle v == 0
from mpn_gcdext_1.
diff -r 11b4d88d0e5b -r d48fdb0f5eef gmp-impl.h
--- a/gmp-impl.h Thu Dec 10 16:23:55 2009 +0100
+++ b/gmp-impl.h Thu Dec 10 17:04:34 2009 +0100
@@ -1225,7 +1225,7 @@
__GMP_DECLSPEC mp_size_t mpn_bdiv_q_itch __GMP_PROTO ((mp_size_t, mp_size_t));
#define mpn_divexact __MPN(divexact)
-__GMP_DECLSPEC void mpn_divexact __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
+__GMP_DECLSPEC void mpn_divexact __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
#define mpn_divexact_itch __MPN(divexact_itch)
__GMP_DECLSPEC mp_size_t mpn_divexact_itch __GMP_PROTO ((mp_size_t, mp_size_t));
diff -r 11b4d88d0e5b -r d48fdb0f5eef mpn/alpha/ev5/gmp-mparam.h
--- a/mpn/alpha/ev5/gmp-mparam.h Thu Dec 10 16:23:55 2009 +0100
+++ b/mpn/alpha/ev5/gmp-mparam.h Thu Dec 10 17:04:34 2009 +0100
@@ -24,7 +24,7 @@
/* 600 MHz 21164A */
-/* Generated by tuneup.c, 2009-01-15, gcc 3.4 */
+/* Generated by tuneup.c, 2009-12-10, gcc 3.3 */
#define MUL_TOOM22_THRESHOLD 14
#define MUL_TOOM33_THRESHOLD 74
@@ -35,18 +35,31 @@
#define SQR_TOOM3_THRESHOLD 77
#define SQR_TOOM4_THRESHOLD 136
+#define MUL_FFT_TABLE { 240, 480, 1344, 1792, 5120, 20480, 81920, 196608, 0 }
+#define MUL_FFT_MODF_THRESHOLD 240
+#define MUL_FFT_THRESHOLD 1920
+
+#define SQR_FFT_TABLE { 240, 480, 1216, 1792, 5120, 12288, 81920, 196608, 0 }
+#define SQR_FFT_MODF_THRESHOLD 208
+#define SQR_FFT_THRESHOLD 1408
+
#define MULLO_BASECASE_THRESHOLD 0 /* always */
#define MULLO_DC_THRESHOLD 44
#define MULLO_MUL_N_THRESHOLD 246
-#define DIV_SB_PREINV_THRESHOLD 0 /* preinv always */
-#define DIV_DC_THRESHOLD 53
-#define POWM_THRESHOLD 85
+#define MULMOD_BNM1_THRESHOLD 9
-#define MATRIX22_STRASSEN_THRESHOLD 17
-#define HGCD_THRESHOLD 104
+#define DC_DIV_QR_THRESHOLD 54
+#define DC_DIVAPPR_Q_THRESHOLD 180
+#define DC_BDIV_QR_THRESHOLD 47
+#define DC_BDIV_Q_THRESHOLD 181
+#define BINV_NEWTON_THRESHOLD 541
+#define REDC_1_TO_REDC_N_THRESHOLD 77
+
+#define MATRIX22_STRASSEN_THRESHOLD 15
+#define HGCD_THRESHOLD 108
#define GCD_DC_THRESHOLD 321
-#define GCDEXT_DC_THRESHOLD 298
+#define GCDEXT_DC_THRESHOLD 217
#define JACOBI_BASE_METHOD 3
#define DIVREM_1_NORM_THRESHOLD 0 /* preinv always */
@@ -66,14 +79,6 @@
#define SET_STR_DC_THRESHOLD 532
#define SET_STR_PRECOMPUTE_THRESHOLD 1501
-#define MUL_FFT_TABLE { 240, 480, 1344, 1792, 5120, 20480, 81920, 196608, 0 }
-#define MUL_FFT_MODF_THRESHOLD 240
-#define MUL_FFT_THRESHOLD 1920
-
-#define SQR_FFT_TABLE { 240, 480, 1216, 1792, 5120, 12288, 81920, 196608, 0 }
-#define SQR_FFT_MODF_THRESHOLD 208
-#define SQR_FFT_THRESHOLD 1408
-
/* These tables need to be updated. */
#define MUL_FFT_TABLE2 {{1, 4}, {177, 5}, {193, 4}, {209, 5}, {353, 6}, {385, 5}, {417, 6}, {833, 7}, {897, 6}, {961, 7}, {1025, 6}, {1089, 7}, {1665, 8}, {1793, 7}, {2177, 8}, {2305, 7}, {2433, 8}, {2817, 7}, {2945, 8}, {3329, 9}, {3457, 8}, {4865, 9}, {5633, 8}, {6401, 10}, {7169, 9}, {11777, 10}, {12801, 9}, {13825, 10}, {15361, 9}, {19969, 10}, {23553, 9}, {24065, 11}, {30721, 10}, {48129, 11}, {63489, 10}, {72705, 11}, {96257, 12}, {126977, 11}, {194561, 12}, {258049, 11}, {325633, 12}, {389121, 13}, {516097, 12}, {MP_SIZE_T_MAX,0}}
diff -r 11b4d88d0e5b -r d48fdb0f5eef mpn/alpha/ev6/gmp-mparam.h
--- a/mpn/alpha/ev6/gmp-mparam.h Thu Dec 10 16:23:55 2009 +0100
+++ b/mpn/alpha/ev6/gmp-mparam.h Thu Dec 10 17:04:34 2009 +0100
@@ -50,13 +50,17 @@
#define MULMOD_BNM1_THRESHOLD 16
-#define DC_DIV_QR_THRESHOLD 118
-#define REDC_1_TO_REDC_N_THRESHOLD 122
+#define DC_DIV_QR_THRESHOLD 112
+#define DC_DIVAPPR_Q_THRESHOLD 396
+#define DC_BDIV_QR_THRESHOLD 110
+#define DC_BDIV_Q_THRESHOLD 315
+#define BINV_NEWTON_THRESHOLD 889
+#define REDC_1_TO_REDC_N_THRESHOLD 110
-#define MATRIX22_STRASSEN_THRESHOLD 19
-#define HGCD_THRESHOLD 300
-#define GCD_DC_THRESHOLD 1421
-#define GCDEXT_DC_THRESHOLD 1063
+#define MATRIX22_STRASSEN_THRESHOLD 21
+#define HGCD_THRESHOLD 276
+#define GCD_DC_THRESHOLD 1197
+#define GCDEXT_DC_THRESHOLD 799
#define JACOBI_BASE_METHOD 3
#define DIVREM_1_NORM_THRESHOLD 0 /* preinv always */
diff -r 11b4d88d0e5b -r d48fdb0f5eef mpn/arm/gmp-mparam.h
--- a/mpn/arm/gmp-mparam.h Thu Dec 10 16:23:55 2009 +0100
+++ b/mpn/arm/gmp-mparam.h Thu Dec 10 17:04:34 2009 +0100
@@ -46,15 +46,19 @@
#define MULLO_DC_THRESHOLD 120
#define MULLO_MUL_N_THRESHOLD 11138
-#define MULMOD_BNM1_THRESHOLD 20
+#define MULMOD_BNM1_THRESHOLD 19
-#define DC_DIV_QR_THRESHOLD 132
-#define REDC_1_TO_REDC_N_THRESHOLD 123
+#define DC_DIV_QR_THRESHOLD 128
+#define DC_DIVAPPR_Q_THRESHOLD 430
+#define DC_BDIV_QR_THRESHOLD 127
+#define DC_BDIV_Q_THRESHOLD 296
+#define BINV_NEWTON_THRESHOLD 1442
+#define REDC_1_TO_REDC_N_THRESHOLD 115
#define MATRIX22_STRASSEN_THRESHOLD 19
-#define HGCD_THRESHOLD 106
-#define GCD_DC_THRESHOLD 706
-#define GCDEXT_DC_THRESHOLD 630
+#define HGCD_THRESHOLD 110
+#define GCD_DC_THRESHOLD 562
+#define GCDEXT_DC_THRESHOLD 345
#define JACOBI_BASE_METHOD 2
#define DIVREM_1_NORM_THRESHOLD 0 /* preinv always */
diff -r 11b4d88d0e5b -r d48fdb0f5eef mpn/generic/divexact.c
--- a/mpn/generic/divexact.c Thu Dec 10 16:23:55 2009 +0100
+++ b/mpn/generic/divexact.c Thu Dec 10 17:04:34 2009 +0100
@@ -8,7 +8,7 @@
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
-Copyright 2006, 2007 Free Software Foundation, Inc.
+Copyright 2006, 2007, 2009 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -26,6 +26,72 @@
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "longlong.h"
+
+#if 1
+void
+mpn_divexact (mp_ptr qp,
+ mp_srcptr np, mp_size_t nn,
+ mp_srcptr dp, mp_size_t dn)
+{
+ unsigned shift;
+ mp_size_t qn;
+ mp_ptr tp;
+ TMP_DECL;
+
+ ASSERT (dn > 0);
+ ASSERT (nn >= dn);
+ ASSERT (dp[dn-1] > 0);
+ ASSERT (np[nn-1] > 0);
+
+ qn = nn + 1 - dn;
+
+ while (dp[0] == 0)
+ {
+ ASSERT (np[0] == 0);
+ dp++;
+ np++;
+ dn--;
+ nn--;
+ }
+ count_trailing_zeros (shift, dp[0]);
+
+ TMP_MARK;
+ if (shift > 0)
+ {
+ tp = TMP_ALLOC_LIMBS (dn);
+ mpn_rshift (tp, dp, dn, shift);
+ dp = tp;
+
+ /* FIXME: It's sufficient to get the qn least significant
+ limbs. */
+ tp = TMP_ALLOC_LIMBS (nn);
+ mpn_rshift (tp, np, nn, shift);
+ np = tp;
+ }
+ else
+ {
+ mp_ptr tp = TMP_ALLOC_LIMBS (qn);
+ MPN_COPY (tp, np, qn);
+ np = tp;
+ }
+ if (nn > qn)
+ nn = qn;
+ if (dn > qn)
+ dn = qn;
+
+ if (qn > nn)
+ MPN_ZERO (qp + nn, qn - nn);
+
+ tp = TMP_ALLOC_LIMBS (mpn_bdiv_q_itch (nn, dn));
+ mpn_bdiv_q (qp, np, nn, dp, dn, tp);
+ TMP_FREE;
+}
+
+#else
+
/* We use the Jebelean's bidirectional exact division algorithm. This is
somewhat naively implemented, with equal quotient parts done by 2-adic
division and truncating division. Since 2-adic division is faster, it
@@ -45,12 +111,6 @@
we should make the lsb part considerably larger. (How do we tune this?)
*/
-
-#include "gmp.h"
-#include "gmp-impl.h"
-#include "longlong.h"
-
-
mp_size_t
mpn_divexact_itch (mp_size_t nn, mp_size_t dn)
{
@@ -220,3 +280,4 @@
TMP_FREE;
}
+#endif
diff -r 11b4d88d0e5b -r d48fdb0f5eef mpn/generic/gcdext.c
--- a/mpn/generic/gcdext.c Thu Dec 10 16:23:55 2009 +0100
+++ b/mpn/generic/gcdext.c Thu Dec 10 17:04:34 2009 +0100
@@ -85,65 +85,6 @@
return n;
}
-static void
-divexact (mp_ptr qp,
- mp_srcptr np, mp_size_t nn,
- mp_srcptr dp, mp_size_t dn)
-{
- unsigned shift;
- mp_size_t qn;
- mp_ptr tp;
- TMP_DECL;
-
- ASSERT (dn > 0);
- ASSERT (nn >= dn);
- ASSERT (dp[dn-1] > 0);
- ASSERT (np[nn-1] > 0);
-
More information about the gmp-commit
mailing list