[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Apr 22 12:23:14 CEST 2012
details: /var/hg/gmp/rev/8b337290bfb9
changeset: 14877:8b337290bfb9
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Apr 22 12:17:09 2012 +0200
description:
Renamed files with constants for combinatorics.
details: /var/hg/gmp/rev/7f5429959ef8
changeset: 14878:7f5429959ef8
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Apr 22 12:23:10 2012 +0200
description:
tune: Support mpz_bin_ui.
diffstat:
ChangeLog | 8 +
Makefile.am | 14 +-
gen-fac.c | 313 +++++++++++++++++++++++++++++++++++++++++++++++++++++
gen-fac_ui.c | 313 -----------------------------------------------------
gmp-impl.h | 1 +
mpz/2fac_ui.c | 2 -
mpz/bin_ui.c | 11 +-
mpz/bin_uiui.c | 2 -
mpz/fac_ui.c | 2 -
mpz/oddfac_1.c | 6 +-
mpz/primorial_ui.c | 1 -
tune/common.c | 34 +++++
tune/speed.c | 1 +
tune/speed.h | 1 +
14 files changed, 372 insertions(+), 337 deletions(-)
diffs (truncated from 874 to 300 lines):
diff -r 2347fd4901ad -r 7f5429959ef8 ChangeLog
--- a/ChangeLog Sat Apr 21 21:09:01 2012 +0200
+++ b/ChangeLog Sun Apr 22 12:23:10 2012 +0200
@@ -1,3 +1,11 @@
+2012-04-22 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * gen-fac.c: Renamed, was gen-fac_ui.c .
+ * Makefile.am: Renamed gen-fac.c and fac_table.h .
+ * gmp-impl.h: #include "fac_table.h".
+ * mpz/oddfac_1.c: Use generated constant.
+ * mpz/bin_ui.c: Small optimisations.
+
2012-04-21 Torbjorn Granlund <tege at gmplib.org>
* mpn/arm/mul_1.asm: Cleanup.
diff -r 2347fd4901ad -r 7f5429959ef8 Makefile.am
--- a/Makefile.am Sat Apr 21 21:09:01 2012 +0200
+++ b/Makefile.am Sun Apr 22 12:23:10 2012 +0200
@@ -313,14 +313,14 @@
EXTRA_DIST += bootstrap.c
-fac_ui.h: gen-fac_ui$(EXEEXT_FOR_BUILD)
- ./gen-fac_ui $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >fac_ui.h || (rm -f fac_ui.h; exit 1)
-BUILT_SOURCES += fac_ui.h
+fac_table.h: gen-fac$(EXEEXT_FOR_BUILD)
+ ./gen-fac $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >fac_table.h || (rm -f fac_table.h; exit 1)
+BUILT_SOURCES += fac_table.h
-gen-fac_ui$(EXEEXT_FOR_BUILD): gen-fac_ui$(U_FOR_BUILD).c bootstrap.c
- $(CC_FOR_BUILD) `test -f 'gen-fac_ui$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-fac_ui$(U_FOR_BUILD).c -o gen-fac_ui$(EXEEXT_FOR_BUILD)
-DISTCLEANFILES += gen-fac_ui$(EXEEXT_FOR_BUILD)
-EXTRA_DIST += gen-fac_ui.c
+gen-fac$(EXEEXT_FOR_BUILD): gen-fac$(U_FOR_BUILD).c bootstrap.c
+ $(CC_FOR_BUILD) `test -f 'gen-fac$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-fac$(U_FOR_BUILD).c -o gen-fac$(EXEEXT_FOR_BUILD)
+DISTCLEANFILES += gen-fac$(EXEEXT_FOR_BUILD)
+EXTRA_DIST += gen-fac.c
fib_table.h: gen-fib$(EXEEXT_FOR_BUILD)
diff -r 2347fd4901ad -r 7f5429959ef8 gen-fac.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/gen-fac.c Sun Apr 22 12:23:10 2012 +0200
@@ -0,0 +1,313 @@
+/* Generate data for combinatorics: fac_ui, bin_uiui, ...
+
+Copyright 2002, 2011, 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 <stdio.h>
+#include <stdlib.h>
+
+#include "bootstrap.c"
+
+int
+mpz_remove_twos (mpz_t x)
+{
+ int r = 0;
+ for (;mpz_even_p (x);r++)
+ mpz_tdiv_q_2exp (x, x, 1);
+ return r;
+}
+
+/* returns 0 on success */
+int
+gen_consts (int numb, int nail, int limb)
+{
+ mpz_t x, mask, y;
+ unsigned long a, b;
+ unsigned long ofl, ofe;
+
+ printf ("/* This file is automatically generated by gen-fac.c */\n\n");
+ printf ("#if GMP_NUMB_BITS != %d\n", numb);
+ printf ("Error , error this data is for %d GMP_NUMB_BITS only\n", numb);
+ printf ("#endif\n");
+#if 0
+ printf ("#if GMP_LIMB_BITS != %d\n", limb);
+ printf ("Error , error this data is for %d GMP_LIMB_BITS only\n", limb);
+ printf ("#endif\n");
+#endif
+
+ printf
+ ("/* This table is 0!,1!,2!,3!,...,n! where n! has <= GMP_NUMB_BITS bits */\n");
+ printf
+ ("#define ONE_LIMB_FACTORIAL_TABLE CNST_LIMB(0x1),CNST_LIMB(0x1");
+ mpz_init_set_ui (x, 1);
+ for (b = 2;; b++)
+ {
+ mpz_mul_ui (x, x, b); /* so b!=a */
+ if (mpz_sizeinbase (x, 2) > numb)
+ break;
+ printf ("),CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, x);
+ }
+ printf (")\n");
+
+ printf
+ ("\n/* This table is 0!,1!,2!/2,3!/2,...,n!/2^sn where n!/2^sn is an */\n");
+ printf
+ ("/* odd integer for each n, and n!/2^sn has <= GMP_NUMB_BITS bits */\n");
+ printf
+ ("#define ONE_LIMB_ODD_FACTORIAL_TABLE CNST_LIMB(0x1),CNST_LIMB(0x1),CNST_LIMB(0x1");
+ mpz_set_ui (x, 1);
+ for (b = 3;; b++)
+ {
+ for (a = b; (a & 1) == 0; a >>= 1);
+ mpz_mul_ui (x, x, a);
+ if (mpz_sizeinbase (x, 2) > numb)
+ break;
+ printf ("),CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, x);
+ }
+ printf (")\n");
+
+ ofl = b - 1;
+ printf
+ ("#define ODD_FACTORIAL_TABLE_LIMIT (%lu)\n", ofl);
+ mpz_init (mask);
+ mpz_setbit (mask, numb);
+ mpz_sub_ui (mask, mask, 1);
+ printf
+ ("\n/* Previous table, continued, values modulo 2^GMP_NUMB_BITS */\n");
+ printf
+ ("#define ONE_LIMB_ODD_FACTORIAL_EXTTABLE CNST_LIMB(0x");
+ mpz_and (x, x, mask);
+ mpz_out_str (stdout, 16, x);
+ mpz_init (y);
+ mpz_bin_uiui (y, b, b/2);
+ b++;
+ for (;; b++)
+ {
+ for (a = b; (a & 1) == 0; a >>= 1);
+ if (a == b) {
+ mpz_divexact_ui (y, y, a/2+1);
+ mpz_mul_ui (y, y, a);
+ } else
+ mpz_mul_2exp (y, y, 1);
+ if (mpz_sizeinbase (y, 2) > numb)
+ break;
+ mpz_mul_ui (x, x, a);
+ mpz_and (x, x, mask);
+ printf ("),CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, x);
+ }
+ printf (")\n");
+ ofe = b - 1;
+ printf
+ ("#define ODD_FACTORIAL_EXTTABLE_LIMIT (%lu)\n", ofe);
+
+ printf
+ ("\n/* This table is 1!!,3!!,...,(2n+1)!! where (2n+1)!! has <= GMP_NUMB_BITS bits */\n");
+ printf
+ ("#define ONE_LIMB_ODD_DOUBLEFACTORIAL_TABLE CNST_LIMB(0x1");
+ mpz_set_ui (x, 1);
+ for (b = 3;; b+=2)
+ {
+ mpz_mul_ui (x, x, b);
+ if (mpz_sizeinbase (x, 2) > numb)
+ break;
+ printf ("),CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, x);
+ }
+ printf (")\n");
+
+ printf
+ ("\n/* This table x_1, x_2,... contains values s.t. x_n^n has <= GMP_NUMB_BITS bits */\n");
+ printf
+ ("#define NTH_ROOT_NUMB_MASK_TABLE (GMP_NUMB_MASK");
+ 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);
+ }
+ printf (")\n");
+
+ mpz_add_ui (mask, mask, 1);
+ printf
+ ("\n/* This table contains inverses of odd factorials, modulo 2^GMP_NUMB_BITS */\n");
+ printf
+ ("\n/* It begins with (2!/2)^-1=1 */\n");
+ printf
+ ("#define ONE_LIMB_ODD_FACTORIAL_INVERSES_TABLE CNST_LIMB(0x1");
+ mpz_set_ui (x, 1);
+ for (b = 3;b <= ofe - 2; b++)
+ {
+ for (a = b; (a & 1) == 0; a >>= 1);
+ mpz_mul_ui (x, x, a);
+ mpz_invert (y, x, mask);
+ printf ("),CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, y);
+ }
+ printf (")\n");
+
+ 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)
+ {
+ mpz_set_ui (x, b);
+ printf (",%lu",b - mpz_popcount (x));
+ }
+ printf ("\n");
+
+ ofl = (ofl + 1) / 2;
+ printf
+ ("#define ODD_CENTRAL_BINOMIAL_OFFSET (%lu)\n", ofl);
+ printf
+ ("\n/* This table contains binomial(2k,k)/2^t */\n");
+ printf
+ ("\n/* It begins with ODD_CENTRAL_BINOMIAL_TABLE_MIN */\n");
+ printf
+ ("#define ONE_LIMB_ODD_CENTRAL_BINOMIAL_TABLE ");
+ for (b = ofl;; b++)
+ {
+ mpz_bin_uiui (x, 2 * b, b);
+ mpz_remove_twos (x);
+ if (mpz_sizeinbase (x, 2) > numb)
+ break;
+ if (b != ofl)
+ printf ("),");
+ printf("CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, x);
+ }
+ printf (")\n");
+
+ ofe = b - 1;
+ printf
+ ("#define ODD_CENTRAL_BINOMIAL_TABLE_LIMIT (%lu)\n", ofe);
+
+ printf
+ ("\n/* This table contains the inverses of elements in the previous table. */\n");
+ printf
+ ("#define ONE_LIMB_ODD_CENTRAL_BINOMIAL_INVERSE_TABLE CNST_LIMB(0x");
+ for (b = ofl; b <= ofe; b++)
+ {
+ mpz_bin_uiui (x, 2 * b, b);
+ mpz_remove_twos (x);
+ mpz_invert (x, x, mask);
+ mpz_out_str (stdout, 16, x);
+ if (b != ofe)
+ printf ("),CNST_LIMB(0x");
+ }
+ printf (")\n");
+
+ printf
+ ("\n/* This table contains the values t in the formula binomial(2k,k)/2^t */\n");
+ printf
+ ("#define CENTRAL_BINOMIAL_2FAC_TABLE ");
+ for (b = ofl; b <= ofe; b++)
+ {
+ mpz_bin_uiui (x, 2 * b, b);
+ printf ("%lu",mpz_remove_twos (x));
+ if (b != ofe)
+ printf (",");
+ }
+ printf ("\n");
+
+#if 0
+ mpz_set_ui (x, 1);
+ mpz_mul_2exp (x, x, limb + 1); /* x=2^(limb+1) */
+ mpz_init (y);
+ mpz_set_ui (y, 10000);
+ mpz_mul (x, x, y); /* x=2^(limb+1)*10^4 */
+ mpz_set_ui (y, 27182); /* exp(1)*10^4 */
+ mpz_tdiv_q (x, x, y); /* x=2^(limb+1)/exp(1) */
+ printf ("\n/* is 2^(GMP_LIMB_BITS+1)/exp(1) */\n");
+ printf ("#define FAC2OVERE CNST_LIMB(0x");
+ mpz_out_str (stdout, 16, x);
+ printf (")\n");
+
+
+ printf
+ ("\n/* FACMULn is largest odd x such that x*(x+2)*...*(x+2(n-1))<=2^GMP_NUMB_BITS-1 */\n\n");
+ mpz_init (z);
+ mpz_init (t);
+ for (a = 2; a <= 4; a++)
+ {
+ mpz_set_ui (x, 1);
+ mpz_mul_2exp (x, x, numb);
+ mpz_root (x, x, a);
More information about the gmp-commit
mailing list