[Gmp-commit] /var/hg/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Thu Jan 26 22:27:17 CET 2012
details: /var/hg/gmp/rev/6dc0da79f3b9
changeset: 14582:6dc0da79f3b9
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Jan 26 21:56:50 2012 +0100
description:
fac_ui: test above thresholds, and remove typos.
details: /var/hg/gmp/rev/4b84f801006e
changeset: 14583:4b84f801006e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Jan 26 22:19:40 2012 +0100
description:
mpz_prodlimbs: removed from mpz/fac_ui.c, now in a new file.
details: /var/hg/gmp/rev/60e765a525e8
changeset: 14584:60e765a525e8
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Jan 26 22:21:46 2012 +0100
description:
fac_ui: micro-optimisations
diffstat:
ChangeLog | 19 +++++++--
Makefile.am | 4 +-
gmp-impl.h | 3 +
mpz/Makefile.am | 10 +----
mpz/fac_ui.c | 67 -----------------------------------
mpz/prodlimbs.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++
tests/mpz/t-fac_ui.c | 4 +-
tune/Makefile.am | 2 +-
8 files changed, 123 insertions(+), 84 deletions(-)
diffs (truncated from 327 to 300 lines):
diff -r 5cbae1dac316 -r 60e765a525e8 ChangeLog
--- a/ChangeLog Wed Jan 25 10:17:58 2012 +0100
+++ b/ChangeLog Thu Jan 26 22:21:46 2012 +0100
@@ -1,10 +1,21 @@
+2012-01-26 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * tests/mpz/t-fac_ui.c: Increase default test cases.
+
+ * mpz/prodlimbs.c: New file, mpz_prodlimbs implementation.
+ * gmp-impl.h: mpz_prodlimbs declaration.
+ * Makefile.am (MPZ_OBJECTS): add mpz/prodlimbs$U.lo .
+ * mpz/Makefile.am (libmpz_la_SOURCES): add prodlimbs.c .
+ (fac_ui.h): remove target (moved up one directory).
+ * mpz/fac_ui.c: mpz_prodlimbs removed, micro-optimisations.
+
2012-01-25 Torbjorn Granlund <tege at gmplib.org>
* tune/tuneup.c: Remove unused tuneup variables.
2012-01-20 Marco Bodrato <bodrato at mail.dm.unipi.it>
- * mpz/fac_ui.h: Reduce branches in basecases.
+ * mpz/fac_ui.c: Reduce branches in basecases.
2012-01-18 Marc Glisse <marc.glisse at inria.fr>
@@ -18,7 +29,7 @@
2012-01-16 Marco Bodrato <bodrato at mail.dm.unipi.it>
- * mpz/fac_ui.h (SIEVE_SEED): Define value for small limb size.
+ * mpz/fac_ui.c (SIEVE_SEED): Define value for small limb size.
(mpz_oddswing_1): Reduce the number of divisions.
(mpz_oddfac_1): Reduce memory usage.
* mpn/minithres/gmp-mparam.h: Correct minimum for FAC_DSC_.
@@ -54,7 +65,7 @@
* gen-fac_ui.c: Remove currently unused constants; add new odd
double factorial table.
- * mpz/fac_ui.h (RECURSIVE_PROD_THRESHOLD): Increase default.
+ * mpz/fac_ui.c (RECURSIVE_PROD_THRESHOLD): Increase default.
(mpz_oddfac_1): New function: a merge of _bc_odd and _dsc_odd.
(mpz_prodlimbs): More in-place computations.
@@ -79,7 +90,7 @@
* gmp-impl.h (FAC_ODD_THRESHOLD,FAC_DSC_THRESHOLD):
New thresholds: default values, and setup for tuning.
(FAC_DSC_THRESHOLD_LIMIT): Define (when tuning).
- * mpz/fac_ui.h (FAC_ODD_THRESHOLD,FAC_DSC_THRESHOLD):
+ * mpz/fac_ui.c (FAC_ODD_THRESHOLD,FAC_DSC_THRESHOLD):
Default values removed.
2011-12-30 Torbjorn Granlund <tege at gmplib.org>
diff -r 5cbae1dac316 -r 60e765a525e8 Makefile.am
--- a/Makefile.am Wed Jan 25 10:17:58 2012 +0100
+++ b/Makefile.am Thu Jan 26 22:21:46 2012 +0100
@@ -2,7 +2,7 @@
# Copyright 1991, 1993, 1994, 1996, 1997, 1999, 2000, 2001, 2002, 2003, 2004,
-# 2006, 2007, 2008, 2009, 2011 Free Software Foundation, Inc.
+# 2006, 2007, 2008, 2009, 2011, 2012 Free Software Foundation, Inc.
#
# This file is part of the GNU MP Library.
#
@@ -157,7 +157,7 @@
mpz/cong$U.lo mpz/cong_2exp$U.lo mpz/cong_ui$U.lo \
mpz/divexact$U.lo mpz/divegcd$U.lo mpz/dive_ui$U.lo \
mpz/divis$U.lo mpz/divis_ui$U.lo mpz/divis_2exp$U.lo mpz/dump$U.lo \
- mpz/export$U.lo mpz/fac_ui$U.lo mpz/fdiv_q$U.lo \
+ mpz/export$U.lo mpz/fac_ui$U.lo mpz/fdiv_q$U.lo mpz/prodlimbs$U.lo \
mpz/fdiv_q_ui$U.lo mpz/fdiv_qr$U.lo mpz/fdiv_qr_ui$U.lo \
mpz/fdiv_r$U.lo mpz/fdiv_r_ui$U.lo \
mpz/fdiv_ui$U.lo mpz/fib_ui$U.lo mpz/fib2_ui$U.lo mpz/fits_sint$U.lo \
diff -r 5cbae1dac316 -r 60e765a525e8 gmp-impl.h
--- a/gmp-impl.h Wed Jan 25 10:17:58 2012 +0100
+++ b/gmp-impl.h Thu Jan 26 22:21:46 2012 +0100
@@ -1569,6 +1569,9 @@
#define mpz_divexact_gcd __gmpz_divexact_gcd
__GMP_DECLSPEC void mpz_divexact_gcd __GMP_PROTO ((mpz_ptr, mpz_srcptr, mpz_srcptr));
+#define mpz_prodlimbs __gmpz_prodlimbs
+__GMP_DECLSPEC mp_size_t mpz_prodlimbs __GMP_PROTO ((mpz_ptr, mp_ptr, mp_size_t));
+
#define mpz_inp_str_nowhite __gmpz_inp_str_nowhite
#ifdef _GMP_H_HAVE_FILE
__GMP_DECLSPEC size_t mpz_inp_str_nowhite __GMP_PROTO ((mpz_ptr, FILE *, int, int, size_t));
diff -r 5cbae1dac316 -r 60e765a525e8 mpz/Makefile.am
--- a/mpz/Makefile.am Wed Jan 25 10:17:58 2012 +0100
+++ b/mpz/Makefile.am Thu Jan 26 22:21:46 2012 +0100
@@ -1,6 +1,6 @@
## Process this file with automake to generate Makefile.in
-# Copyright 1996, 1998, 1999, 2000, 2001, 2002, 2003 Free Software
+# Copyright 1996, 1998, 1999, 2000, 2001, 2002, 2003, 2012 Free Software
# Foundation, Inc.
#
# This file is part of the GNU MP Library.
@@ -45,16 +45,10 @@
lcm.c lcm_ui.c lucnum_ui.c lucnum2_ui.c millerrabin.c \
mod.c mul.c mul_2exp.c mul_si.c mul_ui.c n_pow_ui.c neg.c nextprime.c \
out_raw.c out_str.c perfpow.c perfsqr.c popcount.c pow_ui.c powm.c \
- powm_sec.c powm_ui.c pprime_p.c random.c random2.c \
+ powm_sec.c powm_ui.c pprime_p.c prodlimbs.c random.c random2.c \
realloc.c realloc2.c remove.c root.c rootrem.c rrandomb.c \
scan0.c scan1.c set.c set_d.c set_f.c set_q.c set_si.c set_str.c \
set_ui.c setbit.c size.c sizeinbase.c sqrt.c sqrtrem.c sub.c sub_ui.c \
swap.c tdiv_ui.c tdiv_q.c tdiv_q_2exp.c tdiv_q_ui.c tdiv_qr.c \
tdiv_qr_ui.c tdiv_r.c tdiv_r_2exp.c tdiv_r_ui.c tstbit.c ui_pow_ui.c \
ui_sub.c urandomb.c urandomm.c xor.c
-
-# These are BUILT_SOURCES at the top-level, so normally they're built before
-# recursing into this directory.
-#
-fac_ui.h:
- cd ..; $(MAKE) $(AM_MAKEFLAGS) mpz/fac_ui.h
diff -r 5cbae1dac316 -r 60e765a525e8 mpz/fac_ui.c
--- a/mpz/fac_ui.c Wed Jan 25 10:17:58 2012 +0100
+++ b/mpz/fac_ui.c Thu Jan 26 22:21:46 2012 +0100
@@ -294,73 +294,6 @@
#undef BLOCK_SIZE
/*********************************************************/
-/* Section list-prod: product of a list -> mpz_t */
-/*********************************************************/
-
-/* FIXME: should be tuned */
-#ifndef RECURSIVE_PROD_THRESHOLD
-#define RECURSIVE_PROD_THRESHOLD (MUL_TOOM22_THRESHOLD|(MUL_TOOM22_THRESHOLD>>1))
-#endif
-
-/* Computes the product of the j>1 limbs pointed by factors, puts the
- result in x.
- The list in {factors, j} is overwritten.
-*/
-
-static void
-mpz_prodlimbs (mpz_ptr x, mp_limb_t *factors, mp_limb_t j)
-{
- mp_limb_t i;
- mp_size_t size;
- mp_ptr prod;
-
- ASSERT (j > 1);
- ASSERT (RECURSIVE_PROD_THRESHOLD > 3);
-
- if (BELOW_THRESHOLD (j, RECURSIVE_PROD_THRESHOLD)) {
- mp_limb_t cy;
-
- j--;
- size = 1;
-
- for (i = 1; i < j; i++)
- {
- cy = mpn_mul_1 (factors, factors, size, factors[i]);
- factors[size] = cy;
- size += cy != 0;
- };
-
- prod = MPZ_REALLOC (x, size + 1);
-
- cy = mpn_mul_1 (prod, factors, size, factors[i]);
- prod[size] = cy;
- SIZ (x) = size + (cy != 0);
- } else {
- mpz_t x1, x2;
- TMP_DECL;
-
- i = j >> 1;
- TMP_MARK;
-
- MPZ_TMP_INIT (x2, j - i);
-
- PTR (x1) = factors + i;
- ALLOC (x1) = j - i;
- mpz_prodlimbs (x2, factors + i, j - i);
- mpz_prodlimbs (x1, factors, i);
- size = SIZ (x1) + SIZ (x2);
- prod = MPZ_REALLOC (x, size);
- if (SIZ (x1) >= SIZ (x2))
- i = mpn_mul (prod, PTR(x1), SIZ(x1), PTR(x2), SIZ(x2));
- else
- i = mpn_mul (prod, PTR(x2), SIZ(x2), PTR(x1), SIZ(x1));
- SIZ (x) = size - (i == 0);
-
- TMP_FREE;
- }
-}
-
-/*********************************************************/
/* Section swing: swing factorial */
/*********************************************************/
diff -r 5cbae1dac316 -r 60e765a525e8 mpz/prodlimbs.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpz/prodlimbs.c Thu Jan 26 22:21:46 2012 +0100
@@ -0,0 +1,98 @@
+/* mpz_prodlimps(RESULT, V, LEN) -- Set RESULT to V[0]*V[1]*...*V[LEN-1].
+
+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 2012 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"
+
+/*********************************************************/
+/* Section list-prod: product of a list -> mpz_t */
+/*********************************************************/
+
+/* FIXME: should be tuned */
+#ifndef RECURSIVE_PROD_THRESHOLD
+#define RECURSIVE_PROD_THRESHOLD (MUL_TOOM22_THRESHOLD|(MUL_TOOM22_THRESHOLD<<1))
+#endif
+
+/* Computes the product of the j>1 limbs pointed by factors, puts the
+ * result in x. It assumes that all limbs are non-zero. Above
+ * Karatsuba's threshold it uses a binary splitting startegy, to gain
+ * speed by the asymptotically fast multiplication algorithms.
+ *
+ * The list in {factors, j} is overwritten.
+ * Returns the size of the result
+ */
+
+mp_size_t
+mpz_prodlimbs (mpz_ptr x, mp_ptr factors, mp_size_t j)
+{
+ mp_limb_t cy;
+ mp_size_t size, i;
+ mp_ptr prod;
+
+ ASSERT (j > 1);
+ ASSERT (RECURSIVE_PROD_THRESHOLD > 3);
+
+ if (BELOW_THRESHOLD (j, RECURSIVE_PROD_THRESHOLD)) {
+ j--;
+ size = 1;
+
+ for (i = 1; i < j; i++)
+ {
+ cy = mpn_mul_1 (factors, factors, size, factors[i]);
+ factors[size] = cy;
+ size += cy != 0;
+ };
+
+ prod = MPZ_REALLOC (x, size + 1);
+
+ cy = mpn_mul_1 (prod, factors, size, factors[i]);
+ prod[size] = cy;
+ return SIZ (x) = size + (cy != 0);
+ } else {
+ mpz_t x1, x2;
+ TMP_DECL;
+
+ i = j >> 1;
+ j -= i;
+ TMP_MARK;
+
+ MPZ_TMP_INIT (x2, j);
+
+ PTR (x1) = factors + i;
+ ALLOC (x1) = j;
+ j = mpz_prodlimbs (x2, factors + i, j);
+ i = mpz_prodlimbs (x1, factors, i);
+ size = i + j;
+ prod = MPZ_REALLOC (x, size);
+ if (i >= j)
+ cy = mpn_mul (prod, PTR(x1), i, PTR(x2), j);
+ else
+ cy = mpn_mul (prod, PTR(x2), j, PTR(x1), i);
+ TMP_FREE;
+
+ return SIZ (x) = size - (cy == 0);
+ }
+}
diff -r 5cbae1dac316 -r 60e765a525e8 tests/mpz/t-fac_ui.c
--- a/tests/mpz/t-fac_ui.c Wed Jan 25 10:17:58 2012 +0100
+++ b/tests/mpz/t-fac_ui.c Thu Jan 26 22:21:46 2012 +0100
@@ -1,6 +1,6 @@
/* Exercise mpz_fac_ui.
More information about the gmp-commit
mailing list