[Gmp-commit] /home/hgfiles/gmp: 5 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Dec 12 00:05:26 CET 2009
details: /home/hgfiles/gmp/rev/f7bd22df81d4
changeset: 13035:f7bd22df81d4
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Dec 11 19:33:27 2009 +0100
description:
(COUNT): Decrease to keep run time reasonable.
details: /home/hgfiles/gmp/rev/298984c47f61
changeset: 13036:298984c47f61
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Dec 11 23:33:47 2009 +0100
description:
Use mpn_mulmod_bnm1 instead of FFT wrapping.
details: /home/hgfiles/gmp/rev/49f002b840b8
changeset: 13037:49f002b840b8
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Dec 11 23:34:39 2009 +0100
description:
Tune BINV_MULMOD_BNM1_THRESHOLD.
details: /home/hgfiles/gmp/rev/c4d9e0463d69
changeset: 13038:c4d9e0463d69
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Dec 11 23:35:18 2009 +0100
description:
*** empty log message ***
details: /home/hgfiles/gmp/rev/8155c651b234
changeset: 13039:8155c651b234
user: Torbjorn Granlund <tege at gmplib.org>
date: Sat Dec 12 00:05:18 2009 +0100
description:
Rework BINV_MULMOD_BNM1_THRESHOLD code.
diffstat:
ChangeLog | 7 +++++++
gmp-impl.h | 6 +++++-
mpn/generic/binvert.c | 36 ++++++++++++++++--------------------
tests/mpn/t-bdiv.c | 2 +-
tune/tuneup.c | 15 +++++++++++++--
5 files changed, 42 insertions(+), 24 deletions(-)
diffs (155 lines):
diff -r 75e6a9ad2a72 -r 8155c651b234 ChangeLog
--- a/ChangeLog Fri Dec 11 18:53:04 2009 +0100
+++ b/ChangeLog Sat Dec 12 00:05:18 2009 +0100
@@ -1,5 +1,12 @@
2009-12-11 Torbjorn Granlund <tege at gmplib.org>
+ * mpn/generic/binvert.c: Use mpn_mulmod_bnm1 instead of FFT wrapping.
+ Old, evidently broken wrapping code removed.
+ * tune/tuneup.c (tune_binvert): Tune BINV_MULMOD_BNM1_THRESHOLD.
+ * gmp-impl.h: Provide declarations for corresponding threshold var.
+
+ * tests/mpn/t-bdiv.c (COUNT): Decrease to keep run time reasonable.
+
* tune/tuneup.c (tune_invert): Tune INV_MULMOD_BNM1_THRESHOLD.
* gmp-impl.h: Provide declarations for corresponding threshold var.
diff -r 75e6a9ad2a72 -r 8155c651b234 gmp-impl.h
--- a/gmp-impl.h Fri Dec 11 18:53:04 2009 +0100
+++ b/gmp-impl.h Sat Dec 12 00:05:18 2009 +0100
@@ -952,7 +952,7 @@
#define mpn_mulmod_bnm1 __MPN(mulmod_bnm1)
__GMP_DECLSPEC void mpn_mulmod_bnm1 __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
#define mpn_mulmod_bnm1_next_size __MPN(mulmod_bnm1_next_size)
-__GMP_DECLSPEC mp_size_t mpn_mulmod_bnm1_next_size __GMP_PROTO ((mp_size_t));
+__GMP_DECLSPEC mp_size_t mpn_mulmod_bnm1_next_size __GMP_PROTO ((mp_size_t)) ATTRIBUTE_CONST;
#define mpn_mulmod_bnm1_itch(n) (2*(n) + 2*GMP_LIMB_BITS +2)
@@ -4174,6 +4174,10 @@
#define INV_NEWTON_THRESHOLD inv_newton_threshold
extern mp_size_t inv_newton_threshold;
+#undef BINV_MULMOD_BNM1_THRESHOLD
+#define BINV_MULMOD_BNM1_THRESHOLD binv_mulmod_bnm1_threshold
+extern mp_size_t binv_mulmod_bnm1_threshold;
+
#undef BINV_NEWTON_THRESHOLD
#define BINV_NEWTON_THRESHOLD binv_newton_threshold
extern mp_size_t binv_newton_threshold;
diff -r 75e6a9ad2a72 -r 8155c651b234 mpn/generic/binvert.c
--- a/mpn/generic/binvert.c Fri Dec 11 18:53:04 2009 +0100
+++ b/mpn/generic/binvert.c Sat Dec 12 00:05:18 2009 +0100
@@ -44,6 +44,9 @@
#define NPOWS \
((sizeof(mp_size_t) > 6 ? 48 : 8*sizeof(mp_size_t)))
#else
+#ifndef BINV_MULMOD_BNM1_THRESHOLD
+#define BINV_MULMOD_BNM1_THRESHOLD 0 /* presumably always 0 */
+#endif
#define NPOWS \
((sizeof(mp_size_t) > 6 ? 48 : 8*sizeof(mp_size_t)) - LOG2C (BINV_NEWTON_THRESHOLD))
#endif
@@ -51,18 +54,15 @@
mp_size_t
mpn_binvert_itch (mp_size_t n)
{
-#if WANT_FFT
- if (ABOVE_THRESHOLD (n, 2 * MUL_FFT_MODF_THRESHOLD))
- return mpn_fft_next_size (n, mpn_fft_best_k (n, 0));
- else
-#endif
- return 3 * (n - (n >> 1));
+ mp_size_t itch_local = mpn_mulmod_bnm1_next_size (n);
+ mp_size_t itch_out = mpn_mulmod_bnm1_itch (itch_local);
+ return itch_local + itch_out;
}
void
mpn_binvert (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_ptr scratch)
{
- mp_ptr xp;
+ mp_ptr xp, tp;
mp_size_t rn, newrn;
mp_size_t sizes[NPOWS], *sizp;
mp_limb_t di;
@@ -89,23 +89,19 @@
{
newrn = *--sizp;
- /* X <- UR. We actually want a mulmid */
-#if WANT_FFT
- if (ABOVE_THRESHOLD (newrn, 2 * MUL_FFT_MODF_THRESHOLD))
+ /* X <- UR. */
+ if (ABOVE_THRESHOLD (newrn, BINV_MULMOD_BNM1_THRESHOLD))
{
- int k;
mp_size_t m;
-
- k = mpn_fft_best_k (newrn, 0);
- m = mpn_fft_next_size (newrn, k);
- mpn_mul_fft (xp, m, up, newrn, rp, rn, k);
-
- if (xp[0] != 1 || !mpn_zero_p (xp + 1, rn - 1))
- MPN_INCR_U (xp + rn, newrn - rn, 1);
+ m = mpn_mulmod_bnm1_next_size (newrn);
+ mpn_mulmod_bnm1 (xp, m, up, newrn, rp, rn, xp + m);
+ mpn_sub_1 (xp + m, xp, rn - (m - newrn), 1);
}
else
-#endif
- mpn_mul (xp, up, newrn, rp, rn);
+ {
+ mpn_mul (xp, up, newrn, rp, rn);
+ }
+ /* R = R(X/B^rn) */
mpn_mullo_n (rp + rn, rp, xp + rn, newrn - rn);
mpn_neg_n (rp + rn, rp + rn, newrn - rn);
}
diff -r 75e6a9ad2a72 -r 8155c651b234 tests/mpn/t-bdiv.c
--- a/tests/mpn/t-bdiv.c Fri Dec 11 18:53:04 2009 +0100
+++ b/tests/mpn/t-bdiv.c Sat Dec 12 00:05:18 2009 +0100
@@ -78,7 +78,7 @@
#define MAX_DN (1L << SIZE_LOG)
#define MAX_NN (1L << (SIZE_LOG + 1))
-#define COUNT 1000
+#define COUNT 100
int
main (int argc, char **argv)
{
diff -r 75e6a9ad2a72 -r 8155c651b234 tune/tuneup.c
--- a/tune/tuneup.c Fri Dec 11 18:53:04 2009 +0100
+++ b/tune/tuneup.c Sat Dec 12 00:05:18 2009 +0100
@@ -170,6 +170,7 @@
mp_size_t dc_bdiv_q_threshold = MP_SIZE_T_MAX;
mp_size_t inv_mulmod_bnm1_threshold = MP_SIZE_T_MAX;
mp_size_t inv_newton_threshold = MP_SIZE_T_MAX;
+mp_size_t binv_mulmod_bnm1_threshold = MP_SIZE_T_MAX;
mp_size_t binv_newton_threshold = MP_SIZE_T_MAX;
mp_size_t redc_1_to_redc_2_threshold = MP_SIZE_T_MAX;
mp_size_t redc_1_to_redc_n_threshold = MP_SIZE_T_MAX;
@@ -1056,11 +1057,21 @@
tune_binvert (void)
{
static struct param_t param;
+ param.function = speed_mpn_binvert;
+
param.name = "BINV_NEWTON_THRESHOLD";
- param.function = speed_mpn_binvert;
- param.step_factor = 0.02;
param.max_size = 5000;
one (&binv_newton_threshold, ¶m);
+
+ param.name = "BINV_MULMOD_BNM1_THRESHOLD";
+ param.noprint = 1;
+ param.min_size = binv_newton_threshold;
+ param.max_size = 500;
+ one (&binv_mulmod_bnm1_threshold, ¶m);
+ if (binv_mulmod_bnm1_threshold <= binv_newton_threshold)
+ print_define_remark (param.name, 0, "always when newton");
+ else
+ print_define (param.name, binv_mulmod_bnm1_threshold);
}
void
More information about the gmp-commit
mailing list