[Gmp-commit] /home/hgfiles/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Dec 29 01:44:07 CET 2009
details: /home/hgfiles/gmp/rev/b9955c51e8b4
changeset: 13250:b9955c51e8b4
user: Torbjorn Granlund <tege at gmplib.org>
date: Tue Dec 29 01:35:08 2009 +0100
description:
Update header comments.
details: /home/hgfiles/gmp/rev/cad43ee503e4
changeset: 13251:cad43ee503e4
user: Torbjorn Granlund <tege at gmplib.org>
date: Tue Dec 29 01:35:56 2009 +0100
description:
Allocate scratch space when caller passed NULL.
details: /home/hgfiles/gmp/rev/531e6859684e
changeset: 13252:531e6859684e
user: Torbjorn Granlund <tege at gmplib.org>
date: Tue Dec 29 01:41:58 2009 +0100
description:
Rewrite mu_div functions.
details: /home/hgfiles/gmp/rev/415926f3d24f
changeset: 13253:415926f3d24f
user: Torbjorn Granlund <tege at gmplib.org>
date: Tue Dec 29 01:43:59 2009 +0100
description:
Call mu_div functions with operands that generate a high quotient limb.
diffstat:
ChangeLog | 26 +++-
gmp-impl.h | 10 +-
mpn/generic/invertappr.c | 15 ++-
mpn/generic/mu_bdiv_q.c | 16 +-
mpn/generic/mu_bdiv_qr.c | 18 +--
mpn/generic/mu_div_q.c | 33 +++--
mpn/generic/mu_div_qr.c | 267 +++++++++++++++++++++-----------------------
mpn/generic/mu_divappr_q.c | 185 +++++++++++++-----------------
tests/mpn/t-div.c | 2 +-
9 files changed, 280 insertions(+), 292 deletions(-)
diffs (truncated from 1020 to 300 lines):
diff -r 92ee2d0d1857 -r 415926f3d24f ChangeLog
--- a/ChangeLog Mon Dec 28 16:53:17 2009 +0100
+++ b/ChangeLog Tue Dec 29 01:43:59 2009 +0100
@@ -1,3 +1,17 @@
+2009-12-29 Torbjorn Granlund <tege at gmplib.org>
+
+ * tests/mpn/t-div.c: Call mu_div functions with operands that generate
+ a high quotient limb.
+
+ * mpn/generic/mu_div_qr.c: Rewrite to return a high quotient limb,
+ to let dividend argument be constant, and as a general cleanup.
+ * mpn/generic/mu_divappr_q.c: Likewise.
+ * mpn/generic/mu_div_q.c: Likewise.
+ * gmp-impl.h: Update declarations of changed functions.
+
+ * mpn/generic/invertappr.c (mpn_invertappr): Allocate scratch space
+ when caller passed NULL.
+
2009-12-28 Torbjorn Granlund <tege at gmplib.org>
* mpn/generic/toom_couple_handling.c: Prefix name with mpn_.
@@ -3314,12 +3328,12 @@
* mpz/get_str.c: Cast a char index to int to shut up compilers.
- * dc_div_qr.c: Pass dummy scratch argument to mpn_invert.
- * dc_divappr_q.c: Likewise.
- * mu_div_qr.c: Likewise.
- * mu_divappr_q.c: Likewise.
- * mu_div_q.c: Likewise.
- * divexact.c: Likewise.
+ * mpn/generic/dc_div_qr.c: Pass dummy scratch argument to mpn_invert.
+ * mpn/generic/dc_divappr_q.c: Likewise.
+ * mpn/generic/mu_div_qr.c: Likewise.
+ * mpn/generic/mu_divappr_q.c: Likewise.
+ * mpn/generic/mu_div_q.c: Likewise.
+ * mpn/generic/divexact.c: Likewise.
* mpn/generic/invert.c: New file, placeholder for now.
diff -r 92ee2d0d1857 -r 415926f3d24f gmp-impl.h
--- a/gmp-impl.h Mon Dec 28 16:53:17 2009 +0100
+++ b/gmp-impl.h Tue Dec 29 01:43:59 2009 +0100
@@ -1186,14 +1186,14 @@
__GMP_DECLSPEC mp_limb_t mpn_dcpi1_divappr_q_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, gmp_pi1_t *, mp_ptr));
#define mpn_mu_div_qr __MPN(mu_div_qr)
-__GMP_DECLSPEC mp_limb_t mpn_mu_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
+__GMP_DECLSPEC mp_limb_t mpn_mu_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
#define mpn_mu_div_qr_itch __MPN(mu_div_qr_itch)
__GMP_DECLSPEC mp_size_t mpn_mu_div_qr_itch __GMP_PROTO ((mp_size_t, mp_size_t, int));
#define mpn_mu_div_qr_choose_in __MPN(mu_div_qr_choose_in)
__GMP_DECLSPEC mp_size_t mpn_mu_div_qr_choose_in __GMP_PROTO ((mp_size_t, mp_size_t, int));
#define mpn_preinv_mu_div_qr __MPN(preinv_mu_div_qr)
-__GMP_DECLSPEC void mpn_preinv_mu_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
+__GMP_DECLSPEC mp_limb_t mpn_preinv_mu_div_qr __GMP_PROTO ((mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
#define mpn_mu_divappr_q __MPN(mu_divappr_q)
__GMP_DECLSPEC mp_limb_t mpn_mu_divappr_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
@@ -1203,7 +1203,7 @@
__GMP_DECLSPEC mp_size_t mpn_mu_divappr_q_choose_in __GMP_PROTO ((mp_size_t, mp_size_t, int));
#define mpn_preinv_mu_divappr_q __MPN(preinv_mu_divappr_q)
-__GMP_DECLSPEC void mpn_preinv_mu_divappr_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
+__GMP_DECLSPEC mp_limb_t mpn_preinv_mu_divappr_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
#define mpn_mu_div_q __MPN(mu_div_q)
__GMP_DECLSPEC mp_limb_t mpn_mu_div_q __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr));
@@ -1794,8 +1794,8 @@
#define MU_DIVAPPR_Q_THRESHOLD 2000
#endif
-#ifndef MU_DIV_Q_THRESHOLD
-#define MU_DIV_Q_THRESHOLD 2000
+#ifndef MU_DIV_QR_THRESHOLD
+#define MU_DIV_QR_THRESHOLD 2000
#endif
#ifndef MU_BDIV_Q_THRESHOLD
diff -r 92ee2d0d1857 -r 415926f3d24f mpn/generic/invertappr.c
--- a/mpn/generic/invertappr.c Mon Dec 28 16:53:17 2009 +0100
+++ b/mpn/generic/invertappr.c Tue Dec 29 01:43:59 2009 +0100
@@ -285,6 +285,14 @@
mp_limb_t
mpn_invertappr (mp_ptr ip, mp_srcptr dp, mp_size_t n, mp_ptr scratch)
{
+ mp_limb_t res;
+ TMP_DECL;
+
+ TMP_MARK;
+
+ if (scratch == NULL)
+ scratch = TMP_ALLOC_LIMBS (mpn_invertappr_itch (n));
+
ASSERT (n > 0);
ASSERT (dp[n-1] & GMP_NUMB_HIGHBIT);
ASSERT (! MPN_OVERLAP_P (ip, n, dp, n));
@@ -292,7 +300,10 @@
ASSERT (! MPN_OVERLAP_P (dp, n, scratch, mpn_invertappr_itch(n)));
if (BELOW_THRESHOLD (n, INV_NEWTON_THRESHOLD))
- return mpn_bc_invertappr (ip, dp, n, scratch);
+ res = mpn_bc_invertappr (ip, dp, n, scratch);
else
- return mpn_ni_invertappr (ip, dp, n, scratch);
+ res = mpn_ni_invertappr (ip, dp, n, scratch);
+
+ TMP_FREE;
+ return res;
}
diff -r 92ee2d0d1857 -r 415926f3d24f mpn/generic/mu_bdiv_q.c
--- a/mpn/generic/mu_bdiv_q.c Mon Dec 28 16:53:17 2009 +0100
+++ b/mpn/generic/mu_bdiv_q.c Tue Dec 29 01:43:59 2009 +0100
@@ -26,17 +26,11 @@
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
-/* We use the "misunderstanding algorithm" (MU), discovered by Paul Zimmermann
- and Torbjorn Granlund when Torbjorn misunderstood Paul's explanation of
- Jebelean's bidirectional exact division algorithm.
-
- The idea of this algorithm is to compute a smaller inverted value than used
- in the standard Barrett algorithm, and thus save time in the Newton
- iterations, and pay just a small price when using the inverted value for
- developing quotient bits.
-
- Written by Torbjorn Granlund. Paul Zimmermann suggested the use of the
- "wrap around" trick.
+/*
+ The idea of the algorithm used herein is to compute a smaller inverted value
+ than used in the standard Barrett algorithm, and thus save time in the
+ Newton iterations, and pay just a small price when using the inverted value
+ for developing quotient bits. This algorithm was presented at ICMS 2006.
*/
#include "gmp.h"
diff -r 92ee2d0d1857 -r 415926f3d24f mpn/generic/mu_bdiv_qr.c
--- a/mpn/generic/mu_bdiv_qr.c Mon Dec 28 16:53:17 2009 +0100
+++ b/mpn/generic/mu_bdiv_qr.c Tue Dec 29 01:43:59 2009 +0100
@@ -26,17 +26,11 @@
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
-/* We use the "misunderstanding algorithm" (MU), discovered by Paul Zimmermann
- and Torbjorn Granlund when Torbjorn misunderstood Paul's explanation of
- Jebelean's bidirectional exact division algorithm.
-
- The idea of this algorithm is to compute a smaller inverted value than used
- in the standard Barrett algorithm, and thus save time in the Newton
- iterations, and pay just a small price when using the inverted value for
- developing quotient bits.
-
- Written by Torbjorn Granlund. Paul Zimmermann suggested the use of the
- "wrap around" trick.
+/*
+ The idea of the algorithm used herein is to compute a smaller inverted value
+ than used in the standard Barrett algorithm, and thus save time in the
+ Newton iterations, and pay just a small price when using the inverted value
+ for developing quotient bits. This algorithm was presented at ICMS 2006.
*/
#include "gmp.h"
@@ -53,7 +47,7 @@
nn >= 2
scratch space as determined by mpn_mu_bdiv_qr_itch(nn,dn).
- Write quotient to Q = {qp,nn}.
+ Write quotient to Q = {qp,nn-dn}.
FIXME: When iterating, perhaps do the small step before loop, not after.
FIXME: Try to avoid the scalar divisions when computing inverse size.
diff -r 92ee2d0d1857 -r 415926f3d24f mpn/generic/mu_div_q.c
--- a/mpn/generic/mu_div_q.c Mon Dec 28 16:53:17 2009 +0100
+++ b/mpn/generic/mu_div_q.c Tue Dec 29 01:43:59 2009 +0100
@@ -1,4 +1,4 @@
-/* mpn_mu_div_q, mpn_preinv_mu_div_q.
+/* mpn_mu_div_q.
Contributed to the GNU project by Torbjorn Granlund.
@@ -6,7 +6,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 2005, 2006, 2007 Free Software Foundation, Inc.
+Copyright 2005, 2006, 2007, 2009 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -25,6 +25,13 @@
/*
+ The idea of the algorithm used herein is to compute a smaller inverted value
+ than used in the standard Barrett algorithm, and thus save time in the
+ Newton iterations, and pay just a small price when using the inverted value
+ for developing quotient bits. This algorithm was presented at ICMS 2006.
+*/
+
+/*
Things to work on:
1. This is a rudimentary implementation of mpn_mu_div_q. The algorithm is
@@ -57,7 +64,7 @@
{
mp_ptr tp, rp, ip, this_ip;
mp_size_t qn, in, this_in;
- mp_limb_t cy;
+ mp_limb_t cy, qh;
TMP_DECL;
TMP_MARK;
@@ -88,7 +95,7 @@
{
MPN_COPY (scratch + 1, dp, in);
scratch[0] = 1;
- mpn_invert (ip, scratch, in + 1, NULL);
+ mpn_invertappr (ip, scratch, in + 1, NULL);
MPN_COPY_INCR (ip, ip + 1, in);
}
else
@@ -98,7 +105,7 @@
MPN_ZERO (ip, in);
else
{
- mpn_invert (ip, scratch, in + 1, NULL);
+ mpn_invertappr (ip, scratch, in + 1, NULL);
MPN_COPY_INCR (ip, ip + 1, in);
}
}
@@ -106,21 +113,20 @@
/* |_______________________| dividend
|________| divisor */
rp = TMP_BALLOC_LIMBS (2 * dn + 1);
- if (dn != qn) /* FIXME: perhaps mpn_mu_div_qr should DTRT */
+
{
this_in = mpn_mu_div_qr_choose_in (qn - dn, dn, 0);
this_ip = ip + in - this_in;
- mpn_preinv_mu_div_qr (tp + dn + 1, rp + dn + 1, np + dn, qn, dp, dn,
+ qh = mpn_preinv_mu_div_qr (tp + dn + 1, rp + dn + 1, np + dn, qn, dp, dn,
this_ip, this_in, scratch);
}
- else
- MPN_COPY (rp + dn + 1, np + dn, dn);
+
MPN_COPY (rp + 1, np, dn);
rp[0] = 0;
this_in = mpn_mu_divappr_q_choose_in (dn + 1, dn, 0);
this_ip = ip + in - this_in;
- mpn_preinv_mu_divappr_q (tp, rp, 2*dn + 1, dp, dn, this_ip, this_in, scratch);
+ mpn_preinv_mu_divappr_q (tp, rp, 2 * dn + 1, dp, dn, this_ip, this_in, scratch);
/* The max error of mpn_mu_divappr_q is +4. If the low quotient limb is
greater than the max error, we cannot trust the quotient. */
@@ -138,7 +144,8 @@
{
/* |_______________________| dividend
|________________| divisor */
- mpn_mu_divappr_q (tp, np + nn - (2*qn + 2), 2*qn + 2, dp + dn - (qn + 1), qn + 1, scratch);
+ qh = mpn_mu_divappr_q (tp, np + nn - (2 * qn + 2), 2 * qn + 2,
+ dp + dn - (qn + 1), qn + 1, scratch);
if (tp[0] > 4)
{
@@ -147,12 +154,12 @@
else
{
rp = TMP_BALLOC_LIMBS (dn);
- mpn_mu_div_qr (qp, rp, np, nn, dp, dn, scratch);
+ qh = mpn_mu_div_qr (qp, rp, np, nn, dp, dn, scratch);
}
}
TMP_FREE;
- return 0;
+ return qh;
}
mp_size_t
diff -r 92ee2d0d1857 -r 415926f3d24f mpn/generic/mu_div_qr.c
--- a/mpn/generic/mu_div_qr.c Mon Dec 28 16:53:17 2009 +0100
+++ b/mpn/generic/mu_div_qr.c Tue Dec 29 01:43:59 2009 +0100
@@ -11,7 +11,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 2005, 2006, 2007 Free Software Foundation, Inc.
+Copyright 2005, 2006, 2007, 2009 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -29,22 +29,14 @@
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
-/* We use the "misunderstanding algorithm" (MUA), discovered by Paul Zimmermann
- and Torbjorn Granlund when Torbjorn misunderstood Paul's explanation of
More information about the gmp-commit
mailing list