[Gmp-commit] /home/hgfiles/gmp: Nussbaumer multiplication.
mercurial at gmplib.org
mercurial at gmplib.org
Thu Dec 17 13:40:26 CET 2009
details: /home/hgfiles/gmp/rev/40348c556b42
changeset: 13105:40348c556b42
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Dec 17 13:40:21 2009 +0100
description:
Nussbaumer multiplication.
diffstat:
ChangeLog | 13 ++++++++--
configure.in | 3 +-
gmp-impl.h | 3 ++
mpn/generic/nussbaumer_mul.c | 53 ++++++++++++++++++++++++++++++++++++++++++++
tune/Makefile.am | 2 +-
tune/common.c | 7 +++++
tune/speed.c | 1 +
tune/speed.h | 1 +
8 files changed, 78 insertions(+), 5 deletions(-)
diffs (173 lines):
diff -r 2fe512db5302 -r 40348c556b42 ChangeLog
--- a/ChangeLog Thu Dec 17 12:05:16 2009 +0100
+++ b/ChangeLog Thu Dec 17 13:40:21 2009 +0100
@@ -11,9 +11,16 @@
* mpn/generic/invert.c: Added some comment.
* mpn/generic/invertappr.c: Slightly better threshold handling.
-
* gmp-impl.h (INV_NEWTON_THRESHOLD): Default to 200.
+ * mpn/generic/nussbaumer_mul.c: New file.
+ * configure.in (gmp_mpn_functions): Add nussbaumer_mul.
+ * tune/Makefile.am (TUNE_MPN_SRCS_BASIC): Add nussbaumer_mul.
+ * gmp-impl.h (mpn_nussbaumer_mul): Added prototype and name-mangling.
+ * tune/speed.h (speed_mpn_nussbaumer_mul): Declare function.
+ * tune/common.c (speed_mpn_nussbaumer_mul): New function.
+ * tune/speed.c (routine): Add speed_mpn_nussbaumer_mul.
+
2009-12-17 Torbjorn Granlund <tege at gmplib.org>
* mpn/generic/bdiv_q.c (mpn_bdiv_q_itch): Rewrite.
@@ -128,7 +135,7 @@
(tune_invertappr): Min for INV_NEWTON_THRESHOLD.
* tune/speed.h (SPEED_ROUTINE_MPN_NI_INVERTAPPR): New macro.
- (speed_mpn_ni_invertappr): New function.
+ (speed_mpn_ni_invertappr): Declare function.
* tune/common.c (speed_mpn_ni_invertappr): New function.
* tune/speed.c (routine): Add speed_mpn_ni_invertappr.
@@ -149,7 +156,7 @@
(mpn_invertappr_itch): Added prototype and name-mangling.
(INV_APPR_THRESHOLD): Support for a new tunable const.
* tune/speed.h (SPEED_ROUTINE_MPN_INVERTAPPR): New macro.
- (speed_mpn_invertappr): New function.
+ (speed_mpn_invertappr): Declare function.
* tune/common.c (speed_mpn_invertappr): New function.
* tune/speed.c (routine): Add speed_mpn_invertappr.
* tune/tuneup.c (tune_invertappr): New function: was tune_invert.
diff -r 2fe512db5302 -r 40348c556b42 configure.in
--- a/configure.in Thu Dec 17 12:05:16 2009 +0100
+++ b/configure.in Thu Dec 17 13:40:21 2009 +0100
@@ -2481,7 +2481,8 @@
submul_1 lshift rshift dive_1 diveby3 divis divrem divrem_1 divrem_2 \
fib2_ui mod_1 mod_34lsub1 mode1o pre_divrem_1 pre_mod_1 dump \
mod_1_1 mod_1_2 mod_1_3 mod_1_4 \
- mul mul_fft mul_n sqr_n mul_basecase sqr_basecase random random2 pow_1 \
+ mul mul_fft mul_n sqr_n mul_basecase sqr_basecase nussbaumer_mul \
+ random random2 pow_1 \
rootrem sqrtrem get_str set_str scan0 scan1 popcount hamdist cmp \
perfsqr perfpow \
bdivmod gcd_1 gcd gcdext_1 gcdext gcd_lehmer gcd_subdiv_step \
diff -r 2fe512db5302 -r 40348c556b42 gmp-impl.h
--- a/gmp-impl.h Thu Dec 17 12:05:16 2009 +0100
+++ b/gmp-impl.h Thu Dec 17 13:40:21 2009 +0100
@@ -1119,6 +1119,9 @@
#define mpn_mul_fft_full __MPN(mul_fft_full)
__GMP_DECLSPEC void mpn_mul_fft_full __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
+#define mpn_nussbaumer_mul __MPN(nussbaumer_mul)
+__GMP_DECLSPEC void mpn_nussbaumer_mul __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t));
+
#define mpn_fft_next_size __MPN(fft_next_size)
__GMP_DECLSPEC mp_size_t mpn_fft_next_size __GMP_PROTO ((mp_size_t, int)) ATTRIBUTE_CONST;
diff -r 2fe512db5302 -r 40348c556b42 mpn/generic/nussbaumer_mul.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/nussbaumer_mul.c Thu Dec 17 13:40:21 2009 +0100
@@ -0,0 +1,53 @@
+/* mpn_nussbaumer_mul -- Multiply {ap,an} and {bp,bn} using
+ Nussbaumer's negacyclic convolution.
+
+ Contributed to the GNU project by Marco Bodrato.
+
+ THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE. IT IS ONLY
+ SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
+ GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
+
+Copyright 2009 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+/* Multiply {ap,an} by {bp,bn}, and put the result in {pp, an+bn} */
+void
+mpn_nussbaumer_mul (mp_ptr pp,
+ mp_srcptr ap, mp_size_t an,
+ mp_srcptr bp, mp_size_t bn)
+{
+ mp_size_t rn;
+ mp_ptr rp, tp;
+ TMP_DECL;
+
+ ASSERT (an >= bn);
+ ASSERT (bn > 0);
+
+ rn = mpn_mulmod_bnm1_next_size (an + bn);
+
+ TMP_MARK;
+ TMP_ALLOC_LIMBS_2(rp, rn, tp, mpn_mulmod_bnm1_itch (rn));
+
+ mpn_mulmod_bnm1 (rp, rn, ap, an, bp, bn, tp);
+
+ MPN_COPY (pp, rp, an + bn);
+ TMP_FREE;
+}
diff -r 2fe512db5302 -r 40348c556b42 tune/Makefile.am
--- a/tune/Makefile.am Thu Dec 17 12:05:16 2009 +0100
+++ b/tune/Makefile.am Thu Dec 17 13:40:21 2009 +0100
@@ -126,7 +126,7 @@
dcpi1_div_qr.c dcpi1_divappr_q.c dcpi1_bdiv_qr.c dcpi1_bdiv_q.c \
invertappr.c invert.c binvert.c divrem_2.c gcd.c gcdext.c \
get_str.c set_str.c matrix22_mul.c hgcd.c mul_n.c sqr_n.c \
- mullo_n.c mul_fft.c mul.c tdiv_qr.c mulmod_bnm1.c \
+ mullo_n.c mul_fft.c mul.c tdiv_qr.c mulmod_bnm1.c nussbaumer_mul.c \
toom22_mul.c toom2_sqr.c toom33_mul.c toom3_sqr.c toom44_mul.c toom4_sqr.c
$(TUNE_MPN_SRCS_BASIC):
diff -r 2fe512db5302 -r 40348c556b42 tune/common.c
--- a/tune/common.c Thu Dec 17 12:05:16 2009 +0100
+++ b/tune/common.c Thu Dec 17 13:40:21 2009 +0100
@@ -1036,6 +1036,13 @@
}
double
+speed_mpn_nussbaumer_mul (struct speed_params *s)
+{
+ SPEED_ROUTINE_MPN_MUL_N_CALL
+ (mpn_nussbaumer_mul (wp, s->xp, s->size, s->yp, s->size));
+}
+
+double
speed_mpn_mul_fft_full (struct speed_params *s)
{
SPEED_ROUTINE_MPN_MUL_N_CALL
diff -r 2fe512db5302 -r 40348c556b42 tune/speed.c
--- a/tune/speed.c Thu Dec 17 12:05:16 2009 +0100
+++ b/tune/speed.c Thu Dec 17 13:40:21 2009 +0100
@@ -299,6 +299,7 @@
{ "mpn_toom44_mul", speed_mpn_toom44_mul },
{ "mpn_toom32_mul", speed_mpn_toom32_mul },
{ "mpn_toom42_mul", speed_mpn_toom42_mul },
+ { "mpn_nussbaumer_mul", speed_mpn_nussbaumer_mul },
{ "mpn_mul_fft_full", speed_mpn_mul_fft_full },
{ "mpn_mul_fft_full_sqr", speed_mpn_mul_fft_full_sqr },
diff -r 2fe512db5302 -r 40348c556b42 tune/speed.h
--- a/tune/speed.h Thu Dec 17 12:05:16 2009 +0100
+++ b/tune/speed.h Thu Dec 17 13:40:21 2009 +0100
@@ -223,6 +223,7 @@
double speed_mpn_mul_fft_sqr __GMP_PROTO ((struct speed_params *s));
double speed_mpn_mul_fft_full __GMP_PROTO ((struct speed_params *s));
double speed_mpn_mul_fft_full_sqr __GMP_PROTO ((struct speed_params *s));
+double speed_mpn_nussbaumer_mul __GMP_PROTO ((struct speed_params *s));
double speed_mpn_mul_n __GMP_PROTO ((struct speed_params *s));
double speed_mpn_mul_n_sqr __GMP_PROTO ((struct speed_params *s));
double speed_mpn_mullo_n __GMP_PROTO ((struct speed_params *s));
More information about the gmp-commit
mailing list