[Gmp-commit] /home/hgfiles/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Dec 20 18:17:20 CET 2009
details: /home/hgfiles/gmp/rev/1aff179cbe9b
changeset: 13142:1aff179cbe9b
user: Torbjorn Granlund <tege at gmplib.org>
date: Sun Dec 20 18:16:48 2009 +0100
description:
Loop also over mpn_nussbaumer_mul. Misc improvements.
details: /home/hgfiles/gmp/rev/c7195073a1f1
changeset: 13143:c7195073a1f1
user: Torbjorn Granlund <tege at gmplib.org>
date: Sun Dec 20 18:17:16 2009 +0100
description:
Trivial merge.
diffstat:
ChangeLog | 15 ++++++----
gmp-impl.h | 4 +-
mpn/generic/mul.c | 78 ++++++++++++++++++++++++++++++++++++++++++------------
3 files changed, 71 insertions(+), 26 deletions(-)
diffs (223 lines):
diff -r aa534ff027a4 -r c7195073a1f1 ChangeLog
--- a/ChangeLog Sun Dec 20 05:03:00 2009 +0100
+++ b/ChangeLog Sun Dec 20 18:17:16 2009 +0100
@@ -1,5 +1,14 @@
2009-12-20 Torbjorn Granlund <tege at gmplib.org>
+ * mpn/generic/mul.c: Loop also over mpn_nussbaumer_mul.
+ Use TMP_SALLOC_LIMBS in more places. Clean up ws allocation.
+
+2009-12-19 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpn/generic/toom_interpolate_8pts.c: Nailify.
+
+2009-12-19 Torbjorn Granlund <tege at gmplib.org>
+
* mpn/generic/mul.c: Major rewrite. Use toom43, toom53, toom63.
Call mpn_nussbaumer_mul for largest operands.
@@ -21,12 +30,6 @@
(tune_mul): New function, for unbalanced multiplication.
* gmp-impl.h: Provide declarations for corresponding threshold vars.
-2009-12-19 Marco Bodrato <bodrato at mail.dm.unipi.it>
-
- * mpn/generic/toom_interpolate_8pts.c: Nailify.
-
-2009-12-19 Torbjorn Granlund <tege at gmplib.org>
-
* gmp-impl.h (mpn_rsh1add_nc, mpn_rsh1sub_nc): Declare.
* mpn/asm-defs.m4: Likewise.
* configure.in: Add corresponding HAVE_NATIVEs.
diff -r aa534ff027a4 -r c7195073a1f1 gmp-impl.h
--- a/gmp-impl.h Sun Dec 20 05:03:00 2009 +0100
+++ b/gmp-impl.h Sun Dec 20 18:17:16 2009 +0100
@@ -846,7 +846,7 @@
#define mpn_rsh1add_n __MPN(rsh1add_n)
__GMP_DECLSPEC mp_limb_t mpn_rsh1add_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
#define mpn_rsh1add_nc __MPN(rsh1add_nc)
-__GMP_DECLSPEC mp_limb_t mpn_rsh1add_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
+__GMP_DECLSPEC mp_limb_t mpn_rsh1add_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
/* mpn_rsh1sub_n(c,a,b,n), when it exists, sets {c,n} to ({a,n} - {b,n}) >> 1,
and returns the bit rshifted out (0 or 1). If there's a borrow from the
@@ -855,7 +855,7 @@
#define mpn_rsh1sub_n __MPN(rsh1sub_n)
__GMP_DECLSPEC mp_limb_t mpn_rsh1sub_n __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
#define mpn_rsh1sub_nc __MPN(rsh1sub_nc)
-__GMP_DECLSPEC mp_limb_t mpn_rsh1sub_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t));
+__GMP_DECLSPEC mp_limb_t mpn_rsh1sub_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
#define mpn_lshiftc __MPN(lshiftc)
__GMP_DECLSPEC mp_limb_t mpn_lshiftc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, unsigned int));
diff -r aa534ff027a4 -r c7195073a1f1 mpn/generic/mul.c
--- a/mpn/generic/mul.c Sun Dec 20 05:03:00 2009 +0100
+++ b/mpn/generic/mul.c Sun Dec 20 18:17:16 2009 +0100
@@ -64,15 +64,12 @@
even larger for toom42.
* That problem is even more prevalent for toomX3. We therefore have a
- special fix for avoiding toom63; we call toom42 sometimes in the X3 code.
- We have an uglier fix for toom53, but here we need to choose toom32 or
- toom42...
+ special THRESHOLD variables there.
* Is our ITCH allocation correct?
*/
#define ITCH (16*vn + 100)
-#define WSALLOC (4 * vn)
mp_limb_t
mpn_mul (mp_ptr prodp,
@@ -163,9 +160,9 @@
{
/* Use ToomX2 variants */
mp_ptr scratch;
- TMP_DECL; TMP_MARK;
+ TMP_SDECL; TMP_SMARK;
- scratch = TMP_ALLOC_LIMBS (ITCH);
+ scratch = TMP_SALLOC_LIMBS (ITCH);
/* FIXME: This condition (repeated in the loop below) leaves from a vn*vn
square to a (3vn-1)*vn rectangle. Leaving such a rectangle is hardly
@@ -176,7 +173,8 @@
mp_limb_t cy;
mp_ptr ws;
- ws = TMP_SALLOC_LIMBS (WSALLOC + 1);
+ /* The maximum ws usage is for the mpn_mul result. */
+ ws = TMP_SALLOC_LIMBS (4 * vn);
mpn_toom42_mul (prodp, up, 2 * vn, vp, vn, scratch);
un -= 2 * vn;
@@ -194,6 +192,8 @@
prodp += 2 * vn;
}
+ /* vn <= un < 3vn */
+
if (4 * un < 5 * vn)
mpn_toom22_mul (ws, up, un, vp, vn, scratch);
else if (4 * un < 7 * vn)
@@ -214,29 +214,30 @@
else
mpn_toom42_mul (prodp, up, un, vp, vn, scratch);
}
- TMP_FREE;
+ TMP_SFREE;
}
- else if (BELOW_THRESHOLD ((un + vn) >> 1, MUL_FFT_THRESHOLD) || un > 8 * vn)
+ else if (BELOW_THRESHOLD ((un + vn) >> 1, MUL_FFT_THRESHOLD) ||
+ BELOW_THRESHOLD (3 * vn, MUL_FFT_THRESHOLD))
{
/* Handle the largest operands that are not in the FFT range. The 2nd
condition makes very unbalanced operands avoid the FFT code (except
perhaps as coefficient products of the Toom code. */
- TMP_DECL; TMP_MARK;
-
if (BELOW_THRESHOLD (vn, MUL_TOOM44_THRESHOLD) || !TOOM44_OK (un, vn))
{
/* Use ToomX3 variants */
mp_ptr scratch;
+ TMP_SDECL; TMP_SMARK;
- scratch = TMP_ALLOC_LIMBS (ITCH);
+ scratch = TMP_SALLOC_LIMBS (ITCH);
if (2 * un >= 5 * vn)
{
mp_limb_t cy;
mp_ptr ws;
- ws = TMP_SALLOC_LIMBS (WSALLOC + 1);
+ /* The maximum ws usage is for the mpn_mul result. */
+ ws = TMP_SALLOC_LIMBS (7 * vn >> 1);
if (BELOW_THRESHOLD (vn, MUL_TOOM42_TO_TOOM63_THRESHOLD))
mpn_toom42_mul (prodp, up, 2 * vn, vp, vn, scratch);
@@ -246,7 +247,7 @@
up += 2 * vn;
prodp += 2 * vn;
- while (2 * un >= 5 * vn)
+ while (2 * un >= 5 * vn) /* un >= 2.5vn */
{
if (BELOW_THRESHOLD (vn, MUL_TOOM42_TO_TOOM63_THRESHOLD))
mpn_toom42_mul (ws, up, 2 * vn, vp, vn, scratch);
@@ -260,6 +261,8 @@
prodp += 2 * vn;
}
+ /* vn / 2 <= un < 2.5vn */
+
if (un < vn)
mpn_mul (ws, vp, vn, up, un);
else
@@ -305,21 +308,60 @@
mpn_toom63_mul (prodp, up, un, vp, vn, scratch);
}
}
+ TMP_SFREE;
}
else
{
mp_ptr scratch;
-
- ASSERT (TOOM44_OK (un, vn));
+ TMP_DECL; TMP_MARK;
scratch = TMP_ALLOC_LIMBS (mpn_toom44_mul_itch (un, vn));
mpn_toom44_mul (prodp, up, un, vp, vn, scratch);
+ TMP_FREE;
}
- TMP_FREE;
}
else
{
- mpn_nussbaumer_mul (prodp, up, un, vp, vn);
+ if (un >= 8 * vn)
+ {
+ mp_limb_t cy;
+ mp_ptr ws;
+ TMP_DECL; TMP_MARK;
+
+ /* The maximum ws usage is for the mpn_mul result. */
+ ws = TMP_BALLOC_LIMBS (9 * vn >> 1);
+
+ mpn_nussbaumer_mul (prodp, up, 3 * vn, vp, vn);
+ un -= 3 * vn;
+ up += 3 * vn;
+ prodp += 3 * vn;
+
+ while (2 * un >= 7 * vn) /* un >= 3.5vn */
+ {
+ mpn_nussbaumer_mul (ws, up, 3 * vn, vp, vn);
+ un -= 3 * vn;
+ up += 3 * vn;
+ cy = mpn_add_n (prodp, prodp, ws, vn);
+ MPN_COPY (prodp + vn, ws + vn, 3 * vn);
+ mpn_incr_u (prodp + vn, cy);
+ prodp += 3 * vn;
+ }
+
+ /* vn / 2 <= un < 3.5vn */
+
+ if (un < vn)
+ mpn_mul (ws, vp, vn, up, un);
+ else
+ mpn_mul (ws, up, un, vp, vn);
+
+ cy = mpn_add_n (prodp, prodp, ws, vn);
+ MPN_COPY (prodp + vn, ws + vn, un);
+ mpn_incr_u (prodp + vn, cy);
+
+ TMP_FREE;
+ }
+ else
+ mpn_nussbaumer_mul (prodp, up, un, vp, vn);
}
return prodp[un + vn - 1]; /* historic */
More information about the gmp-commit
mailing list