[Gmp-commit] /var/hg/gmp: 7 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon Apr 30 16:25:26 CEST 2012
details: /var/hg/gmp/rev/7a339a8e86c0
changeset: 14909:7a339a8e86c0
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 15:56:55 2012 +0200
description:
Share some tables among combinatoric functions.
details: /var/hg/gmp/rev/9915d8c08024
changeset: 14910:9915d8c08024
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 15:58:05 2012 +0200
description:
mpz/oddfac_1.c: Reordered
details: /var/hg/gmp/rev/673803278b44
changeset: 14911:673803278b44
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 16:02:11 2012 +0200
description:
Share precomputed (n-popcount(n)).
details: /var/hg/gmp/rev/e7cf99f57dc3
changeset: 14912:e7cf99f57dc3
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 16:11:33 2012 +0200
description:
Share log_n_max and its table.
details: /var/hg/gmp/rev/549e2e61f98a
changeset: 14913:549e2e61f98a
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 16:13:04 2012 +0200
description:
Changelog
details: /var/hg/gmp/rev/f82804d517c3
changeset: 14914:f82804d517c3
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 16:22:34 2012 +0200
description:
mpz/mfac_uiui.c: New file.
details: /var/hg/gmp/rev/8703c179e3b3
changeset: 14915:8703c179e3b3
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Apr 30 16:25:05 2012 +0200
description:
tests/mpz/t-mfac_uiui.c: New file.
diffstat:
ChangeLog | 20 ++++++++++++
Makefile.am | 2 +-
configure.in | 1 +
gen-fac.c | 25 +++++++++++++--
gmp-h.in | 3 +
gmp-impl.h | 14 ++++++++
mpz/2fac_ui.c | 19 ++++++----
mpz/Makefile.am | 2 +-
mpz/bin_uiui.c | 49 +++++++++++------------------
mpz/fac_ui.c | 10 ++++-
mpz/oddfac_1.c | 82 +++++++++++++++++++-------------------------------
mpz/primorial_ui.c | 12 -------
tests/mpz/Makefile.am | 2 +-
13 files changed, 132 insertions(+), 109 deletions(-)
diffs (truncated from 539 to 300 lines):
diff -r 200b0707b624 -r 8703c179e3b3 ChangeLog
--- a/ChangeLog Sun Apr 29 17:56:41 2012 +0200
+++ b/ChangeLog Mon Apr 30 16:25:05 2012 +0200
@@ -1,3 +1,15 @@
+2012-04-30 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpn/generic/comb_tables.c: New file.
+ * configure.in: Add it.
+ * gen-fac.c: Define table limits.
+ * gmp-impl.h: Declare tables.
+ (log_n_max): New static function.
+ * mpz/2fac_ui.c: Use shared tables.
+ * mpz/bin_uiui.c: Likewise.
+ * mpz/oddfac_1.c: Likewise.
+ * mpz/primorial_ui.c: Likewise.
+
2012-04-29 Torbjorn Granlund <tege at gmplib.org>
* mpn/arm/aors_n.asm: Tune for more stable performance.
@@ -18,6 +30,14 @@
* mpn/arm/v6/addmul_1.asm: Rewrite for stable speed, smaller size.
* mpn/arm/v6/mul_1.asm: Likewise.
+ * mpz/mfac_uiui.c: New file.
+ * Makefile.am: Compile it.
+ * mpz/Makefile.am (libmpz_la_SOURCES): Add mpz_mfac_uiui.c
+ * gmp-h.in (mpz_mfac_uiui): Declare.
+
+ * tests/mpz/t-mfac_uiui.c: New file.
+ * tests/mpz/Makefile.am: Run it.
+
2012-04-27 Torbjorn Granlund <tege at gmplib.org>
* configure.in: Search arm/v6t2 for arm7.
diff -r 200b0707b624 -r 8703c179e3b3 Makefile.am
--- a/Makefile.am Sun Apr 29 17:56:41 2012 +0200
+++ b/Makefile.am Mon Apr 30 16:25:05 2012 +0200
@@ -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/export$U.lo mpz/mfac_uiui$U.lo \
mpz/2fac_ui$U.lo mpz/fac_ui$U.lo mpz/oddfac_1$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_q$U.lo \
diff -r 200b0707b624 -r 8703c179e3b3 configure.in
--- a/configure.in Sun Apr 29 17:56:41 2012 +0200
+++ b/configure.in Mon Apr 30 16:25:05 2012 +0200
@@ -2680,6 +2680,7 @@
trialdiv remove \
and_n andn_n nand_n ior_n iorn_n nior_n xor_n xnor_n \
copyi copyd zero tabselect \
+ comb_tables \
$gmp_mpn_functions_optional"
define(GMP_MULFUNC_CHOICES,
diff -r 200b0707b624 -r 8703c179e3b3 gen-fac.c
--- a/gen-fac.c Sun Apr 29 17:56:41 2012 +0200
+++ b/gen-fac.c Mon Apr 30 16:25:05 2012 +0200
@@ -35,7 +35,7 @@
int
gen_consts (int numb, int nail, int limb)
{
- mpz_t x, mask, y;
+ mpz_t x, mask, y, last;
unsigned long a, b;
unsigned long ofl, ofe;
@@ -54,6 +54,7 @@
printf
("#define ONE_LIMB_FACTORIAL_TABLE CNST_LIMB(0x1),CNST_LIMB(0x1");
mpz_init_set_ui (x, 1);
+ mpz_init (last);
for (b = 2;; b++)
{
mpz_mul_ui (x, x, b); /* so b!=a */
@@ -74,6 +75,7 @@
for (b = 3;; b++)
{
for (a = b; (a & 1) == 0; a >>= 1);
+ mpz_set (last, x);
mpz_mul_ui (x, x, a);
if (mpz_sizeinbase (x, 2) > numb)
break;
@@ -81,6 +83,10 @@
mpz_out_str (stdout, 16, x);
}
printf (")\n");
+ printf
+ ("#define ODD_FACTORIAL_TABLE_MAX CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, last);
+ printf (")\n");
ofl = b - 1;
printf
@@ -124,6 +130,7 @@
mpz_set_ui (x, 1);
for (b = 3;; b+=2)
{
+ mpz_set (last, x);
mpz_mul_ui (x, x, b);
if (mpz_sizeinbase (x, 2) > numb)
break;
@@ -131,6 +138,13 @@
mpz_out_str (stdout, 16, x);
}
printf (")\n");
+ printf
+ ("#define ODD_DOUBLEFACTORIAL_TABLE_MAX CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, last);
+ printf (")\n");
+
+ printf
+ ("#define ODD_DOUBLEFACTORIAL_TABLE_LIMIT (%lu)\n", b - 2);
printf
("\n/* This table x_1, x_2,... contains values s.t. x_n^n has <= GMP_NUMB_BITS bits */\n");
@@ -139,8 +153,6 @@
for (b = 2;b <= 8; b++)
{
mpz_root (x, mask, b);
- if (mpz_sizeinbase (x, 2) < 4)
- break;
printf ("),CNST_LIMB(0x");
mpz_out_str (stdout, 16, x);
}
@@ -164,18 +176,23 @@
}
printf (")\n");
+ ofe = (ofe / 16 + 1) * 16;
+
printf
("\n/* This table contains 1i-popc(2i) for small i */\n");
printf
("\n/* It begins with 2-1=1 (N=1) */\n");
printf
("#define TABLE_2N_MINUS_POPC_2N 1");
- for (b = 4;b <= ofe + 1; b+=2)
+ for (b = 4; b <= ofe; b += 2)
{
mpz_set_ui (x, b);
printf (",%lu",b - mpz_popcount (x));
}
printf ("\n");
+ printf
+ ("#define TABLE_LIMIT_2N_MINUS_POPC_2N %i\n", ofe + 1);
+
ofl = (ofl + 1) / 2;
printf
diff -r 200b0707b624 -r 8703c179e3b3 gmp-h.in
--- a/gmp-h.in Sun Apr 29 17:56:41 2012 +0200
+++ b/gmp-h.in Mon Apr 30 16:25:05 2012 +0200
@@ -752,6 +752,9 @@
#define mpz_2fac_ui __gmpz_2fac_ui
__GMP_DECLSPEC void mpz_2fac_ui (mpz_ptr, unsigned long int);
+#define mpz_mfac_uiui __gmpz_mfac_uiui
+__GMP_DECLSPEC void mpz_mfac_uiui (mpz_ptr, unsigned long int, unsigned long int);
+
#define mpz_primorial_ui __gmpz_primorial_ui
__GMP_DECLSPEC void mpz_primorial_ui (mpz_ptr, unsigned long int);
diff -r 200b0707b624 -r 8703c179e3b3 gmp-impl.h
--- a/gmp-impl.h Sun Apr 29 17:56:41 2012 +0200
+++ b/gmp-impl.h Mon Apr 30 16:25:05 2012 +0200
@@ -1915,6 +1915,20 @@
__GMP_DECLSPEC extern const mp_limb_t __gmp_fib_table[];
#define FIB_TABLE(n) (__gmp_fib_table[(n)+1])
+extern const mp_limb_t __gmp_oddfac_table[];
+extern const mp_limb_t __gmp_odd2fac_table[];
+extern const unsigned char __gmp_fac2cnt_table[];
+extern const mp_limb_t __gmp_limbroots_table[];
+
+/* n^log <= GMP_NUMB_MAX, a limb can store log factors less than n */
+static unsigned
+log_n_max (mp_limb_t n)
+{
+ unsigned log;
+ for (log = 8; n > __gmp_limbroots_table[log - 1]; log--);
+ return log;
+}
+
#define SIEVESIZE 512 /* FIXME: Allow gmp_init_primesieve to choose */
typedef struct
{
diff -r 200b0707b624 -r 8703c179e3b3 mpz/2fac_ui.c
--- a/mpz/2fac_ui.c Sun Apr 29 17:56:41 2012 +0200
+++ b/mpz/2fac_ui.c Mon Apr 30 16:25:05 2012 +0200
@@ -45,15 +45,18 @@
if ((n & 1) == 0) { /* n is even, n = 2k, (2k)!! = k! 2^k */
mp_limb_t count;
- popc_limb (count, n); /* popc(n) == popc(k) */
- count = n - count; /* n - popc(n) == k + k - popc(k) */
+ if (n <= TABLE_LIMIT_2N_MINUS_POPC_2N)
+ count = __gmp_fac2cnt_table[n / 2 - 1];
+ else
+ {
+ popc_limb (count, n); /* popc(n) == popc(k) */
+ count = n - count; /* n - popc(n) == k + k - popc(k) */
+ }
mpz_oddfac_1 (x, n >> 1, 0);
mpz_mul_2exp (x, x, count);
} else { /* n is odd */
- static const mp_limb_t tabled[] = { ONE_LIMB_ODD_DOUBLEFACTORIAL_TABLE };
-
- if (n < 2 * numberof (tabled)) {
- PTR (x)[0] = tabled[n >> 1];
+ if (n <= ODD_DOUBLEFACTORIAL_TABLE_LIMIT) {
+ PTR (x)[0] = __gmp_odd2fac_table[n >> 1];
SIZ (x) = 1;
} else if (BELOW_THRESHOLD (n, FAC_2DSC_THRESHOLD)) { /* odd basecase, */
mp_limb_t *factors, prod, max_prod, j;
@@ -63,12 +66,12 @@
TMP_SMARK;
factors = TMP_SALLOC_LIMBS (1 + n / (2 * FACTORS_PER_LIMB));
- factors[0] = tabled[numberof (tabled) - 1];
+ factors[0] = ODD_DOUBLEFACTORIAL_TABLE_MAX;
j = 1;
prod = n;
max_prod = GMP_NUMB_MAX / FAC_2DSC_THRESHOLD;
- while ((n -= 2) >= numberof (tabled) * 2 + 1)
+ while ((n -= 2) > ODD_DOUBLEFACTORIAL_TABLE_LIMIT)
FACTOR_LIST_STORE (n, prod, max_prod, factors, j);
factors[j++] = prod;
diff -r 200b0707b624 -r 8703c179e3b3 mpz/Makefile.am
--- a/mpz/Makefile.am Sun Apr 29 17:56:41 2012 +0200
+++ b/mpz/Makefile.am Mon Apr 30 16:25:05 2012 +0200
@@ -43,7 +43,7 @@
import.c init.c init2.c inits.c inp_raw.c inp_str.c \
invert.c ior.c iset.c iset_d.c iset_si.c iset_str.c iset_ui.c \
jacobi.c kronsz.c kronuz.c kronzs.c kronzu.c \
- lcm.c lcm_ui.c lucnum_ui.c lucnum2_ui.c millerrabin.c \
+ lcm.c lcm_ui.c lucnum_ui.c lucnum2_ui.c mfac_uiui.c millerrabin.c \
mod.c mul.c mul_2exp.c mul_si.c mul_ui.c n_pow_ui.c neg.c nextprime.c \
oddfac_1.c \
out_raw.c out_str.c perfpow.c perfsqr.c popcount.c pow_ui.c powm.c \
diff -r 200b0707b624 -r 8703c179e3b3 mpz/bin_uiui.c
--- a/mpz/bin_uiui.c Sun Apr 29 17:56:41 2012 +0200
+++ b/mpz/bin_uiui.c Mon Apr 30 16:25:05 2012 +0200
@@ -58,7 +58,10 @@
would make it both reasonably accurate and fast. (We could use a table
stored into a limb, perhaps.) The table should take the removed factors of
2 into account (those done on-the-fly in mulN).
-*/
+
+ (3) The first time in the loop we compute the odd part of a
+ factorial in kp, we might use oddfac_1 for this task.
+ */
/* This threshold determines how large divisor to accumulate before we call
bdiv. Perhaps we should never call bdiv, and accumulate all we are told,
@@ -182,17 +185,10 @@
} while (0)
#endif
-/* Entry i contains (i!/2^t) where t is chosen such that the parenthesis
- is an odd integer. */
-static const mp_limb_t fac[] = { ONE_LIMB_ODD_FACTORIAL_TABLE, ONE_LIMB_ODD_FACTORIAL_EXTTABLE };
-
/* Entry i contains (i!/2^t)^(-1) where t is chosen such that the parenthesis
is an odd integer. */
static const mp_limb_t facinv[] = { ONE_LIMB_ODD_FACTORIAL_INVERSES_TABLE };
-/* Entry i contains 2i-popc(2i). */
-static const unsigned char fac2cnt[] = { TABLE_2N_MINUS_POPC_2N };
-
static void
mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k)
{
@@ -228,12 +224,13 @@
np[0] = 1; nn = 1;
i2cnt = 0; /* total low zeros in dividend */
- j2cnt = fac2cnt[ODD_FACTORIAL_TABLE_LIMIT / 2 - 1];
+ j2cnt = __gmp_fac2cnt_table[ODD_FACTORIAL_TABLE_LIMIT / 2 - 1];
/* total low zeros in divisor */
numfac = 1;
j = ODD_FACTORIAL_TABLE_LIMIT + 1;
- jjj = fac[ODD_FACTORIAL_TABLE_LIMIT];
+ jjj = ODD_FACTORIAL_TABLE_MAX;
+ ASSERT (__gmp_oddfac_table[ODD_FACTORIAL_TABLE_LIMIT] == ODD_FACTORIAL_TABLE_MAX);
while (1)
{
@@ -346,8 +343,8 @@
ASSERT (rn < alloc);
- mpn_pi1_bdiv_q_1 (rp, rp, rn, fac[k], facinv[k - 2],
- fac2cnt[k / 2 - 1] - i2cnt);
+ mpn_pi1_bdiv_q_1 (rp, rp, rn, __gmp_oddfac_table[k], facinv[k - 2],
More information about the gmp-commit
mailing list