[Gmp-commit] /home/hgfiles/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Jan 27 19:11:32 CET 2010
details: /home/hgfiles/gmp/rev/6fb4748cbd07
changeset: 13402:6fb4748cbd07
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 27 19:10:16 2010 +0100
description:
Remove an incorrect comment about an incorrect function.
details: /home/hgfiles/gmp/rev/c9c6eeb3fcb3
changeset: 13403:c9c6eeb3fcb3
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 27 19:11:28 2010 +0100
description:
(mpn_mu_div_q_itch): Rewrite. Then undo Marco's last change.
diffstat:
ChangeLog | 11 ++++++++++-
mpn/generic/mu_bdiv_q.c | 2 +-
mpn/generic/mu_bdiv_qr.c | 2 +-
mpn/generic/mu_div_q.c | 37 +++++++++++++++++++++++++++----------
mpn/generic/mu_div_qr.c | 3 ++-
mpn/generic/mu_divappr_q.c | 12 ++++++++++--
tests/mpn/t-div.c | 2 +-
7 files changed, 52 insertions(+), 17 deletions(-)
diffs (170 lines):
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 ChangeLog
--- a/ChangeLog Wed Jan 27 07:45:18 2010 +0100
+++ b/ChangeLog Wed Jan 27 19:11:28 2010 +0100
@@ -1,3 +1,12 @@
+2010-01-27 Torbjorn Granlund <tege at gmplib.org>
+
+ * mpn/generic/mu_div_q.c (mpn_mu_div_q_itch): Rewrite.
+ * mpn/generic/mu_div_qr.c (mpn_mu_div_qr_itch): Re-enable
+ better mulmod itch estimate.
+ * mpn/generic/mu_divappr_q.c (mpn_mu_divappr_q_itch): Likewise.
+ * mpn/generic/mu_bdiv_qr.c (mpn_mu_bdiv_qr_itch): Likewise.
+ * mpn/generic/mu_bdiv_q.c (mpn_mu_bdiv_q_itch): Likewise.
+
2010-01-27 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mpn/generic/mu_div_qr.c (mpn_mu_div_qr_itch): Disabled guessed
@@ -19,7 +28,7 @@
* mpn/generic/nussbaumer_mul.c: Use the new functions.
* mpn/generic/invertappr.c (mpn_ni_invertappr): Use new syntax for
- mpn_mulmod_bnm1_itch.
+ mpn_mulmod_bnm1_itch.
* mpn/generic/mu_divappr_q.c (mpn_mu_divappr_q_itch): Likewise.
* mpn/generic/mu_bdiv_qr.c (mpn_mu_bdiv_qr_itch): Likewise.
* mpn/generic/mu_bdiv_q.c (mpn_mu_bdiv_q_itch): Likewise.
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 mpn/generic/mu_bdiv_q.c
--- a/mpn/generic/mu_bdiv_q.c Wed Jan 27 07:45:18 2010 +0100
+++ b/mpn/generic/mu_bdiv_q.c Wed Jan 27 19:11:28 2010 +0100
@@ -257,7 +257,7 @@
{
tn = mpn_mulmod_bnm1_next_size (qn);
/* FIXME: check for the correct estimate and remove #if */
-#if 0
+#if 1
itch_out = mpn_mulmod_bnm1_itch (tn, qn, in);
#else
itch_out = mpn_mulmod_bnm1_itch (tn, tn, tn);
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 mpn/generic/mu_bdiv_qr.c
--- a/mpn/generic/mu_bdiv_qr.c Wed Jan 27 07:45:18 2010 +0100
+++ b/mpn/generic/mu_bdiv_qr.c Wed Jan 27 19:11:28 2010 +0100
@@ -277,7 +277,7 @@
{
tn = mpn_mulmod_bnm1_next_size (dn);
/* FIXME: check for the correct estimate and remove #if */
-#if 0
+#if 1
itch_out = mpn_mulmod_bnm1_itch (tn, dn, in);
#else
itch_out = mpn_mulmod_bnm1_itch (tn, tn, tn);
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 mpn/generic/mu_div_q.c
--- a/mpn/generic/mu_div_q.c Wed Jan 27 07:45:18 2010 +0100
+++ b/mpn/generic/mu_div_q.c Wed Jan 27 19:11:28 2010 +0100
@@ -42,13 +42,14 @@
simply call mpn_mu_divappr_q. Such a temporary allocation is
unfortunately very large.
- 2. Instead of falling back to mpn_mu_div_qr when we detect a possible
- mpn_mu_divappr_q rounding problem, we could multiply and compare.
+ 2. We used to fall back to mpn_mu_div_qr when we detect a possible
+ mpn_mu_divappr_q rounding problem, now we multiply and compare.
Unfortunately, since mpn_mu_divappr_q does not return the partial
- remainder, this also doesn't become optimal. A mpn_mu_divappr_qr
- could solve that.
+ remainder, this also doesn't become optimal. A mpn_mu_divappr_qr could
+ solve that.
- 3. The allocations done here should be made from the scratch area.
+ 3. The allocations done here should be made from the scratch area, which
+ then would need to be amended.
*/
#include <stdlib.h> /* for NULL */
@@ -75,7 +76,8 @@
if (qn >= dn) /* nn >= 2*dn + 1 */
{
- /* Find max inverse size needed by the two preinv calls. */
+ /* Find max inverse size needed by the two preinv calls. FIXME: This is
+ not optimal, it underestimates the invariance. */
if (dn != qn)
{
mp_size_t in1, in2;
@@ -163,6 +165,12 @@
{
/* |_______________________| dividend
|________________| divisor */
+
+ /* FIXME: When nn = 2dn-1, qn becomes dn-1, and the numerator size passed
+ here becomes 2dn, i.e., more than nn. This shouldn't hurt, since only
+ the most significant dn-1 limbs will actually be read, but it is not
+ pretty. */
+
qh = mpn_mu_divappr_q (tp, np + nn - (2 * qn + 2), 2 * qn + 2,
dp + dn - (qn + 1), qn + 1, scratch);
@@ -197,9 +205,18 @@
mp_size_t
mpn_mu_div_q_itch (mp_size_t nn, mp_size_t dn, int mua_k)
{
- mp_size_t itch1, itch2;
+ mp_size_t qn, itch1, itch2;
- itch1 = mpn_mu_divappr_q_itch (nn, dn, mua_k);
- itch2 = mpn_mu_div_qr_itch (nn, dn, mua_k);
- return MAX (itch1, itch2);
+ qn = nn - dn;
+ if (qn >= dn)
+ {
+ itch1 = mpn_mu_div_qr_itch (qn, dn, mua_k);
+ itch2 = mpn_mu_divappr_q_itch (2 * dn + 1, dn, mua_k);
+ return MAX (itch1, itch2);
+ }
+ else
+ {
+ itch1 = mpn_mu_divappr_q_itch (2 * qn + 2, qn + 1, mua_k);
+ return itch1;
+ }
}
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 mpn/generic/mu_div_qr.c
--- a/mpn/generic/mu_div_qr.c Wed Jan 27 07:45:18 2010 +0100
+++ b/mpn/generic/mu_div_qr.c Wed Jan 27 19:11:28 2010 +0100
@@ -405,11 +405,12 @@
mp_size_t itch_local = mpn_mulmod_bnm1_next_size (dn + 1);
mp_size_t in = mpn_mu_div_qr_choose_in (nn - dn, dn, mua_k);
/* FIXME: check for the correct estimate and remove #if */
-#if 0
+#if 1
mp_size_t itch_out = mpn_mulmod_bnm1_itch (itch_local, dn, in);
#else
mp_size_t itch_out = mpn_mulmod_bnm1_itch (itch_local, itch_local, itch_local);
#endif
+ ASSERT_ALWAYS (mpn_mulmod_bnm1_itch (itch_local, dn, in) <= itch_out);
return in + itch_local + itch_out;
}
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 mpn/generic/mu_divappr_q.c
--- a/mpn/generic/mu_divappr_q.c Wed Jan 27 07:45:18 2010 +0100
+++ b/mpn/generic/mu_divappr_q.c Wed Jan 27 19:11:28 2010 +0100
@@ -356,9 +356,17 @@
mpn_mu_divappr_q_itch (mp_size_t nn, mp_size_t dn, int mua_k)
{
mp_size_t itch_local = mpn_mulmod_bnm1_next_size (dn + 1);
- mp_size_t in = mpn_mu_div_qr_choose_in (nn - dn, dn, mua_k);
+ mp_size_t qn, in;
+
+ qn = nn - dn;
+ if (qn + 1 < dn)
+ {
+ dn = qn + 1;
+ }
+ in = mpn_mu_divappr_q_choose_in (qn, dn, mua_k);
+
/* FIXME: check for the correct estimate and remove #if */
-#if 0
+#if 1
mp_size_t itch_out = mpn_mulmod_bnm1_itch (itch_local, dn, in);
#else
mp_size_t itch_out = mpn_mulmod_bnm1_itch (itch_local, itch_local, itch_local);
diff -r 73636b3ec7c2 -r c9c6eeb3fcb3 tests/mpn/t-div.c
--- a/tests/mpn/t-div.c Wed Jan 27 07:45:18 2010 +0100
+++ b/tests/mpn/t-div.c Wed Jan 27 19:11:28 2010 +0100
@@ -380,7 +380,7 @@
/* Test mpn_mu_div_q */
if (nn - dn > 2 && dn >= 2)
{
- itch = mpn_mu_div_q_itch (nn, dn, 0); /* FIXME: wrong itch function */
+ itch = mpn_mu_div_q_itch (nn, dn, 0);
if (itch + 1> alloc)
{
scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1);
More information about the gmp-commit
mailing list