[Gmp-commit] /home/hgfiles/gmp: 10 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Jan 1 21:34:07 CET 2010
details: /home/hgfiles/gmp/rev/26f5eb9e6b01
changeset: 13288:26f5eb9e6b01
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 14:42:33 2010 +0100
description:
Avoid generating too small test operands.
details: /home/hgfiles/gmp/rev/4c33ff9a73ba
changeset: 13289:4c33ff9a73ba
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 14:42:56 2010 +0100
description:
Add a copyright year.
details: /home/hgfiles/gmp/rev/6521ddf76bb1
changeset: 13290:6521ddf76bb1
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 16:50:48 2010 +0100
description:
Move SB suppression limit downwards. Increase COUNT to 200.
details: /home/hgfiles/gmp/rev/86ba3dd5d7b2
changeset: 13291:86ba3dd5d7b2
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 16:51:56 2010 +0100
description:
Replace with unit testing code, based on t-div.c.
details: /home/hgfiles/gmp/rev/c78cb9aa12b1
changeset: 13292:c78cb9aa12b1
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 21:17:52 2010 +0100
description:
Increase COUNT to 500.
details: /home/hgfiles/gmp/rev/1f97f22302f1
changeset: 13293:1f97f22302f1
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 21:19:37 2010 +0100
description:
Add parameter ASSERTs.
details: /home/hgfiles/gmp/rev/164f674caf22
changeset: 13294:164f674caf22
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 21:30:00 2010 +0100
description:
Rewrite to use mpn_mulmod_bnm1.
details: /home/hgfiles/gmp/rev/4bd791b7af10
changeset: 13295:4bd791b7af10
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 21:31:27 2010 +0100
description:
Default MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD.
details: /home/hgfiles/gmp/rev/fa4bf30a8c16
changeset: 13296:fa4bf30a8c16
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 21:33:05 2010 +0100
description:
(check_PROGRAMS): Put t-div and t-bdiv together.
details: /home/hgfiles/gmp/rev/3af60c550de5
changeset: 13297:3af60c550de5
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Jan 01 21:34:03 2010 +0100
description:
Trivial merge.
diffstat:
ChangeLog | 19 +
gmp-impl.h | 4 +
mpn/generic/dcpi1_bdiv_q.c | 5 +-
mpn/generic/dcpi1_bdiv_qr.c | 6 +-
mpn/generic/dcpi1_divappr_q.c | 2 +-
mpn/generic/mu_bdiv_q.c | 187 ++++++++----------
mpn/generic/mu_bdiv_qr.c | 187 ++++++++----------
mpn/generic/mu_div_qr.c | 84 ++------
mpn/generic/mu_divappr_q.c | 98 ++-------
mpn/generic/mul_fft.c | 4 +-
mpn/generic/toom22_mul.c | 2 +-
mpn/generic/toom2_sqr.c | 2 +-
mpn/generic/toom3_sqr.c | 2 +-
mpn/generic/toom4_sqr.c | 2 +-
tests/mpn/Makefile.am | 4 +-
tests/mpn/t-bdiv.c | 416 +++++++++++++++++++++++++++--------------
tests/mpn/t-div.c | 27 +-
17 files changed, 545 insertions(+), 506 deletions(-)
diffs (truncated from 1658 to 300 lines):
diff -r f456a2d8cb66 -r 3af60c550de5 ChangeLog
--- a/ChangeLog Thu Dec 31 20:52:46 2009 +0100
+++ b/ChangeLog Fri Jan 01 21:34:03 2010 +0100
@@ -1,3 +1,22 @@
+2010-01-01 Torbjorn Granlund <tege at gmplib.org>
+
+ * gmp-impl.h (MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD): Default to 0.
+
+ * mpn/generic/mu_div_qr.c: Rewrite to use mpn_mulmod_bnm1. Clean up
+ scratch usage. Improve itch functions.
+ * mpn/generic/mu_divappr_q.c: Likewise.
+ * mpn/generic/mu_bdiv_qr.c: Likewise.
+ * mpn/generic/mu_div_q.c: Likewise.
+
+ * mpn/generic/dcpi1_bdiv_qr.c: Add parameter ASSERTs.
+ * mpn/generic/dcpi1_bdiv_q.c: Likewise.
+
+ * tests/mpn/t-bdiv.c: Replace with unit testing code, based on t-div.c.
+ Increase COUNT to 500.
+
+ * tests/mpn/t-div.c: Avoid generating too small test operands.
+ Move SB suppression limit downwards. Increase COUNT to 200.
+
2009-12-31 Torbjorn Granlund <tege at gmplib.org>
* mpn/generic/tdiv_qr.c: Handle numerator/remainder overlap in MU case.
diff -r f456a2d8cb66 -r 3af60c550de5 gmp-impl.h
--- a/gmp-impl.h Thu Dec 31 20:52:46 2009 +0100
+++ b/gmp-impl.h Fri Jan 01 21:34:03 2010 +0100
@@ -1818,6 +1818,10 @@
#define SQRMOD_BNM1_THRESHOLD 16
#endif
+#ifndef MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD
+#define MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD 0
+#endif
+
#if HAVE_NATIVE_mpn_addmul_2 || HAVE_NATIVE_mpn_redc_2
#ifndef REDC_1_TO_REDC_2_THRESHOLD
diff -r f456a2d8cb66 -r 3af60c550de5 mpn/generic/dcpi1_bdiv_q.c
--- a/mpn/generic/dcpi1_bdiv_q.c Thu Dec 31 20:52:46 2009 +0100
+++ b/mpn/generic/dcpi1_bdiv_q.c Fri Jan 01 21:34:03 2010 +0100
@@ -91,8 +91,9 @@
TMP_MARK;
- ASSERT (nn >= dn);
- ASSERT (dn > 0);
+ ASSERT (dn >= 2);
+ ASSERT (nn - dn >= 0);
+ ASSERT (dp[0] & 1);
tp = TMP_SALLOC_LIMBS (dn);
diff -r f456a2d8cb66 -r 3af60c550de5 mpn/generic/dcpi1_bdiv_qr.c
--- a/mpn/generic/dcpi1_bdiv_qr.c Thu Dec 31 20:52:46 2009 +0100
+++ b/mpn/generic/dcpi1_bdiv_qr.c Fri Jan 01 21:34:03 2010 +0100
@@ -7,7 +7,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.
@@ -92,6 +92,10 @@
TMP_MARK;
+ ASSERT (dn >= 2); /* to adhere to mpn_sbpi1_div_qr's limits */
+ ASSERT (nn - dn >= 1); /* to adhere to mpn_sbpi1_div_qr's limits */
+ ASSERT (dp[0] & 1);
+
tp = TMP_SALLOC_LIMBS (dn);
qn = nn - dn;
diff -r f456a2d8cb66 -r 3af60c550de5 mpn/generic/dcpi1_divappr_q.c
--- a/mpn/generic/dcpi1_divappr_q.c Thu Dec 31 20:52:46 2009 +0100
+++ b/mpn/generic/dcpi1_divappr_q.c Fri Jan 01 21:34:03 2010 +0100
@@ -7,7 +7,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.
diff -r f456a2d8cb66 -r 3af60c550de5 mpn/generic/mu_bdiv_q.c
--- a/mpn/generic/mu_bdiv_q.c Thu Dec 31 20:52:46 2009 +0100
+++ b/mpn/generic/mu_bdiv_q.c Fri Jan 01 21:34:03 2010 +0100
@@ -61,10 +61,10 @@
mp_srcptr dp, mp_size_t dn,
mp_ptr scratch)
{
- mp_ptr ip;
- mp_ptr rp;
mp_size_t qn;
mp_size_t in;
+ int cy, c0;
+ mp_size_t tn, wn;
qn = nn;
@@ -74,15 +74,15 @@
if (qn > dn)
{
mp_size_t b;
- mp_ptr tp;
- mp_limb_t cy;
- int k;
- mp_size_t m, wn;
- mp_size_t i;
/* |_______________________| dividend
|________| divisor */
+#define ip scratch /* in */
+#define rp (scratch + in) /* dn or rest >= binvert_itch(in) */
+#define tp (scratch + in + dn) /* dn+in or next_size(dn) */
+#define scratch_out (scratch + in + dn + tn) /* mulmod_bnm1_itch(next_size(dn)) */
+
/* Compute an inverse size that is a nice partition of the quotient. */
b = (qn - 1) / dn + 1; /* ceil(qn/dn), number of blocks */
in = (qn - 1) / b + 1; /* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
@@ -95,10 +95,6 @@
should reduce itch to perhaps 3dn.
*/
- ip = scratch; /* in limbs */
- rp = scratch + in; /* MAX(binvert_itch(in),dn) limbs */
- tp = scratch + in + dn; /* MAX(next_size(dn,k),dn+in) limbs */
-
mpn_binvert (ip, dp, in, rp);
cy = 0;
@@ -108,42 +104,22 @@
mpn_mullo_n (qp, rp, ip, in);
qn -= in;
-#if WANT_FFT
- if (ABOVE_THRESHOLD (dn, MUL_FFT_MODF_THRESHOLD))
- {
- k = mpn_fft_best_k (dn, 0);
- m = mpn_fft_next_size (dn, k);
- wn = dn + in - m; /* number of wrapped limbs */
- ASSERT_ALWAYS (wn >= 0); /* could handle this below */
- }
-#endif
-
while (qn > in)
{
-#if WANT_FFT
- if (ABOVE_THRESHOLD (dn, MUL_FFT_MODF_THRESHOLD))
+ if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
+ mpn_mul (tp, dp, dn, qp, in); /* mulhi, need tp[dn+in-1...in] */
+ else
{
- /* The two multiplicands are dn and 'in' limbs, with dn >= in.
- The relevant part of the result will typically partially wrap,
- and that part will come out as subtracted to the right. The
- unwrapped part, m-in limbs at the high end of tp, is the lower
- part of the sought product. The wrapped part, at the low end
- of tp, will be subtracted from the low part of the partial
- remainder; we undo that operation with another subtraction. */
- int c0;
+ tn = mpn_mulmod_bnm1_next_size (dn);
+ mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
+ wn = dn + in - tn; /* number of wrapped limbs */
+ if (wn > 0)
+ {
+ c0 = mpn_sub_n (tp + tn, tp, rp, wn);
+ mpn_decr_u (tp + wn, c0);
+ }
+ }
- c0 = mpn_mul_fft (tp, m, dp, dn, qp, in, k);
- ASSERT_ALWAYS (c0 == 0);
-
- c0 = mpn_sub_n (tp + m, rp, tp, wn);
-
- for (i = wn; c0 != 0 && i < in; i++)
- c0 = tp[i] == GMP_NUMB_MASK;
- mpn_incr_u (tp + in, c0);
- }
- else
-#endif
- mpn_mul (tp, dp, dn, qp, in); /* mulhi, need tp[dn+in-1...in] */
qp += in;
if (dn != in)
{
@@ -165,23 +141,21 @@
/* Generate last qn limbs.
FIXME: It should be possible to limit precision here, since qn is
typically somewhat smaller than dn. No big gains expected. */
-#if WANT_FFT
- if (ABOVE_THRESHOLD (dn, MUL_FFT_MODF_THRESHOLD))
+
+ if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
+ mpn_mul (tp, dp, dn, qp, in); /* mulhi, need tp[qn+in-1...in] */
+ else
{
- int c0;
+ tn = mpn_mulmod_bnm1_next_size (dn);
+ mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
+ wn = dn + in - tn; /* number of wrapped limbs */
+ if (wn > 0)
+ {
+ c0 = mpn_sub_n (tp + tn, tp, rp, wn);
+ mpn_decr_u (tp + wn, c0);
+ }
+ }
- c0 = mpn_mul_fft (tp, m, dp, dn, qp, in, k);
- ASSERT_ALWAYS (c0 == 0);
-
- c0 = mpn_sub_n (tp + m, rp, tp, wn);
-
- for (i = wn; c0 != 0 && i < in; i++)
- c0 = tp[i] == GMP_NUMB_MASK;
- mpn_incr_u (tp + in, c0);
- }
- else
-#endif
- mpn_mul (tp, dp, dn, qp, in); /* mulhi, need tp[qn+in-1...in] */
qp += in;
if (dn != in)
{
@@ -195,48 +169,55 @@
mpn_sub_nc (rp + dn - in, np, tp + dn, qn - (dn - in), cy);
mpn_mullo_n (qp, rp, ip, qn);
- }
+
+#undef ip
+#undef rp
+#undef tp
+#undef scratch_out
+ }
else
{
/* |_______________________| dividend
|________________| divisor */
+#define ip scratch /* in */
+#define tp (scratch + in) /* qn+in or next_size(qn) or rest >= binvert_itch(in) */
+#define scratch_out (scratch + in + tn)/* mulmod_bnm1_itch(next_size(qn)) */
+
/* Compute half-sized inverse. */
in = qn - (qn >> 1);
- ip = scratch; /* in limbs */
- rp = scratch + in; /* MAX(binvert_itch(in),next_size(qn,k),qn+in) limbs */
-
- mpn_binvert (ip, dp, in, rp);
+ mpn_binvert (ip, dp, in, tp);
mpn_mullo_n (qp, np, ip, in); /* low `in' quotient limbs */
-#if WANT_FFT
- if (ABOVE_THRESHOLD (qn, MUL_FFT_MODF_THRESHOLD))
+
+ if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
+ mpn_mul (tp, dp, qn, qp, in); /* mulhigh */
+ else
{
- int k;
- mp_size_t m;
- int c0;
+ tn = mpn_mulmod_bnm1_next_size (qn);
+ mpn_mulmod_bnm1 (tp, tn, dp, qn, qp, in, scratch_out);
+ wn = qn + in - tn; /* number of wrapped limbs */
+ if (wn > 0)
+ {
+ c0 = mpn_cmp (tp, np, wn) < 0;
+ mpn_decr_u (tp + wn, c0);
+ }
+ }
- k = mpn_fft_best_k (qn, 0);
- m = mpn_fft_next_size (qn, k);
- c0 = mpn_mul_fft (rp, m, dp, qn, qp, in, k);
- ASSERT_ALWAYS (c0 == 0);
- if (mpn_cmp (np, rp, in) < 0)
- mpn_incr_u (rp + in, 1);
- }
- else
-#endif
- mpn_mul (rp, dp, qn, qp, in); /* mulhigh */
+ mpn_sub_n (tp, np + in, tp + in, qn - in);
+ mpn_mullo_n (qp + in, tp, ip, qn - in); /* high qn-in quotient limbs */
- mpn_sub_n (rp, np + in, rp + in, qn - in);
- mpn_mullo_n (qp + in, rp, ip, qn - in); /* high qn-in quotient limbs */
+#undef ip
+#undef tp
+#undef scratch_out
}
}
More information about the gmp-commit
mailing list