[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Feb 3 13:39:41 CET 2012
details: /var/hg/gmp/rev/647cdf50233a
changeset: 14602:647cdf50233a
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Feb 03 13:26:27 2012 +0100
description:
Add copyright years.
details: /var/hg/gmp/rev/a23759f9e720
changeset: 14603:a23759f9e720
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Feb 03 13:39:33 2012 +0100
description:
mpz_oddfac_1: removed from mpz/fac_ui.c, now in a new file.
diffstat:
ChangeLog | 9 +
Makefile.am | 4 +-
gmp-impl.h | 3 +
mpz/Makefile.am | 1 +
mpz/fac_ui.c | 529 +------------------------------------------------
mpz/oddfac_1.c | 592 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
mpz/prodlimbs.c | 2 +-
tune/Makefile.am | 2 +
8 files changed, 615 insertions(+), 527 deletions(-)
diffs (truncated from 1240 to 300 lines):
diff -r 024bc8908e40 -r a23759f9e720 ChangeLog
--- a/ChangeLog Thu Feb 02 23:01:53 2012 +0100
+++ b/ChangeLog Fri Feb 03 13:39:33 2012 +0100
@@ -1,3 +1,12 @@
+2012-02-03 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpz/fac_ui.c: mpz_oddfac_1 removed, with many related functions.
+ * mpz/oddfac_1.c: New file, mpz_oddfac_1 implementation.
+ * gmp-impl.h: mpz_oddfac_1 declaration.
+ * Makefile.am (MPZ_OBJECTS): add mpz/oddfac_1$U.lo .
+ * mpz/Makefile.am (libmpz_la_SOURCES): add oddfac_1.c .
+ * tune/Makefile.am (fac_ui.c): include mpz/oddfac_1.c .
+
2012-02-02 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mpn/generic/toom_interpolate_16pts.c: Correct an unlikely 32-bit bug.
diff -r 024bc8908e40 -r a23759f9e720 Makefile.am
--- a/Makefile.am Thu Feb 02 23:01:53 2012 +0100
+++ b/Makefile.am Fri Feb 03 13:39:33 2012 +0100
@@ -157,9 +157,9 @@
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/prodlimbs$U.lo \
+ mpz/export$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_r$U.lo mpz/fdiv_r_ui$U.lo mpz/fdiv_q$U.lo \
mpz/fdiv_ui$U.lo mpz/fib_ui$U.lo mpz/fib2_ui$U.lo mpz/fits_sint$U.lo \
mpz/fits_slong$U.lo mpz/fits_sshort$U.lo mpz/fits_uint$U.lo \
mpz/fits_ulong$U.lo mpz/fits_ushort$U.lo mpz/gcd$U.lo \
diff -r 024bc8908e40 -r a23759f9e720 gmp-impl.h
--- a/gmp-impl.h Thu Feb 02 23:01:53 2012 +0100
+++ b/gmp-impl.h Fri Feb 03 13:39:33 2012 +0100
@@ -1572,6 +1572,9 @@
#define mpz_prodlimbs __gmpz_prodlimbs
__GMP_DECLSPEC mp_size_t mpz_prodlimbs __GMP_PROTO ((mpz_ptr, mp_ptr, mp_size_t));
+#define mpz_oddfac_1 __gmpz_oddfac_1
+__GMP_DECLSPEC void mpz_oddfac_1 __GMP_PROTO ((mpz_ptr, mp_limb_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 024bc8908e40 -r a23759f9e720 mpz/Makefile.am
--- a/mpz/Makefile.am Thu Feb 02 23:01:53 2012 +0100
+++ b/mpz/Makefile.am Fri Feb 03 13:39:33 2012 +0100
@@ -44,6 +44,7 @@
jacobi.c kronsz.c kronuz.c kronzs.c kronzu.c \
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 \
+ oddfac_1.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 prodlimbs.c random.c random2.c \
realloc.c realloc2.c remove.c root.c rootrem.c rrandomb.c \
diff -r 024bc8908e40 -r a23759f9e720 mpz/fac_ui.c
--- a/mpz/fac_ui.c Thu Feb 02 23:01:53 2012 +0100
+++ b/mpz/fac_ui.c Fri Feb 03 13:39:33 2012 +0100
@@ -22,19 +22,9 @@
#include "gmp.h"
#include "gmp-impl.h"
-#include "longlong.h"
#include "fac_ui.h"
-/* TODO:
- - write the code for tuning more thresholds;
- - split this file in smaller parts with functions that can be recycled for different computations.
- */
-
-/*************************************************************/
-/* Section macros: common macros, for swing/fac/bin (&sieve) */
-/*************************************************************/
-
/* This is intended for constant THRESHOLDs only, where the compiler
can completely fold the result. */
#define LOG2C(n) \
@@ -43,12 +33,6 @@
((n) >= 0x100) + ((n) >= 0x200) + ((n) >= 0x400) + ((n) >= 0x800) + \
((n) >= 0x1000) + ((n) >= 0x2000) + ((n) >= 0x4000) + ((n) >= 0x8000))
-#define FACTOR_LIST_APPEND(PR, MAX_PR, VEC, I) \
- if ((PR) > (MAX_PR)) { \
- (VEC)[(I)++] = (PR); \
- (PR) = 1; \
- }
-
#define FACTOR_LIST_STORE(P, PR, MAX_PR, VEC, I) \
do { \
if ((PR) > (MAX_PR)) { \
@@ -58,519 +42,12 @@
(PR) *= (P); \
} while (0)
-#define LOOP_ON_SIEVE_CONTINUE(prime,end,sieve) \
- __max_i = (end); \
- \
- do { \
- ++__i; \
- if (((sieve)[__index] & __mask) == 0) \
- { \
- (prime) = id_to_n(__i)
-
-#define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \
- do { \
- mp_limb_t __mask, __index, __max_i, __i; \
- \
- __i = (start)-(off); \
- __index = __i / GMP_LIMB_BITS; \
- __mask = CNST_LIMB(1) << (__i % GMP_LIMB_BITS); \
- __i += (off); \
- \
- LOOP_ON_SIEVE_CONTINUE(prime,end,sieve)
-
-#define LOOP_ON_SIEVE_STOP \
- } \
- __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \
- __index += __mask & 1; \
- } while (__i <= __max_i) \
-
-#define LOOP_ON_SIEVE_END \
- LOOP_ON_SIEVE_STOP; \
- } while (0)
-
-/*********************************************************/
-/* Section sieve: sieving functions and tools for primes */
-/*********************************************************/
-
-static mp_limb_t
-bit_to_n (mp_limb_t bit) { return (bit*3+4)|1; }
-
-/* id_to_n (x) = bit_to_n (x-1) = (id*3+1)|1*/
-static mp_limb_t
-id_to_n (mp_limb_t id) { return id*3+1+(id&1); }
-
-/* n_to_bit (n) = ((n-1)&(-CNST_LIMB(2)))/3U-1 */
-static mp_limb_t
-n_to_bit (mp_limb_t n) { return ((n-5)|1)/3U; }
-
-static mp_size_t
-primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; }
-
-#if GMP_LIMB_BITS > 61
-#define SIEVE_SEED CNST_LIMB(0x3294C9E069128480)
-#define SEED_LIMIT 202
-#else
-#if GMP_LIMB_BITS > 30
-#define SIEVE_SEED CNST_LIMB(0x69128480)
-#define SEED_LIMIT 114
-#else
-#if GMP_LIMB_BITS > 15
-#define SIEVE_SEED CNST_LIMB(0x8480)
-#define SEED_LIMIT 54
-#else
-#if GMP_LIMB_BITS > 7
-#define SIEVE_SEED CNST_LIMB(0x80)
-#define SEED_LIMIT 34
-#else
-#define SIEVE_SEED CNST_LIMB(0x0)
-#define SEED_LIMIT 24
-#endif /* 7 */
-#endif /* 15 */
-#endif /* 30 */
-#endif /* 61 */
-
-static void
-first_block_primesieve (mp_ptr bit_array, mp_limb_t n)
-{
- mp_size_t bits, limbs;
-
- ASSERT (n > 4);
-
- bits = n_to_bit(n);
- limbs = bits / GMP_LIMB_BITS + 1;
-
- /* FIXME: We can skip 5 too, filling with a 5-part pattern. */
- MPN_ZERO (bit_array, limbs);
- bit_array[0] = SIEVE_SEED;
-
- if ((bits + 1) % GMP_LIMB_BITS != 0)
- bit_array[limbs-1] |= MP_LIMB_T_MAX << ((bits + 1) % GMP_LIMB_BITS);
-
- if (n > SEED_LIMIT) {
- mp_limb_t mask, index, i;
-
- ASSERT (n > 49);
-
- mask = 1;
- index = 0;
- i = 1;
- do {
- if ((bit_array[index] & mask) == 0)
- {
- mp_size_t step, lindex;
- mp_limb_t lmask;
- unsigned maskrot;
-
- step = id_to_n(i);
-/* lindex = n_to_bit(id_to_n(i)*id_to_n(i)); */
- lindex = i*(step+1)-1+(-(i&1)&(i+1));
-/* lindex = i*(step+1+(i&1))-1+(i&1); */
- if (lindex > bits)
- break;
-
- step <<= 1;
- maskrot = step % GMP_LIMB_BITS;
-
- lmask = CNST_LIMB(1) << (lindex % GMP_LIMB_BITS);
- do {
- bit_array[lindex / GMP_LIMB_BITS] |= lmask;
- lmask = lmask << maskrot | lmask >> (GMP_LIMB_BITS - maskrot);
- lindex += step;
- } while (lindex <= bits);
-
-/* lindex = n_to_bit(id_to_n(i)*bit_to_n(i)); */
- lindex = i*(i*3+6)+(i&1);
-
- lmask = CNST_LIMB(1) << (lindex % GMP_LIMB_BITS);
- for ( ; lindex <= bits; lindex += step) {
- bit_array[lindex / GMP_LIMB_BITS] |= lmask;
- lmask = lmask << maskrot | lmask >> (GMP_LIMB_BITS - maskrot);
- };
- }
- mask = mask << 1 | mask >> (GMP_LIMB_BITS-1);
- index += mask & 1;
- i++;
- } while (1);
- }
-}
-
-static void
-block_resieve (mp_ptr bit_array, mp_size_t limbs, mp_limb_t offset,
- mp_srcptr sieve, mp_limb_t sieve_bits)
-{
- mp_size_t bits, step;
-
- ASSERT (limbs > 0);
-
- bits = limbs * GMP_LIMB_BITS - 1;
-
- /* FIXME: We can skip 5 too, filling with a 5-part pattern. */
- MPN_ZERO (bit_array, limbs);
-
- LOOP_ON_SIEVE_BEGIN(step,0,sieve_bits,0,sieve);
- {
- mp_size_t lindex;
- mp_limb_t lmask;
- unsigned maskrot;
-
-/* lindex = n_to_bit(id_to_n(i)*id_to_n(i)); */
- lindex = __i*(step+1)-1+(-(__i&1)&(__i+1));
-/* lindex = __i*(step+1+(__i&1))-1+(__i&1); */
- if (lindex > bits + offset)
- break;
-
- step <<= 1;
- maskrot = step % GMP_LIMB_BITS;
-
- if (lindex < offset)
- lindex += step * ((offset - lindex - 1) / step + 1);
-
- lindex -= offset;
-
- lmask = CNST_LIMB(1) << (lindex % GMP_LIMB_BITS);
- for ( ; lindex <= bits; lindex += step) {
- bit_array[lindex / GMP_LIMB_BITS] |= lmask;
- lmask = lmask << maskrot | lmask >> (GMP_LIMB_BITS - maskrot);
- };
-
-/* lindex = n_to_bit(id_to_n(i)*bit_to_n(i)); */
- lindex = __i*(__i*3+6)+(__i&1);
- if (lindex > bits + offset)
- continue;
-
- if (lindex < offset)
- lindex += step * ((offset - lindex - 1) / step + 1);
-
- lindex -= offset;
-
- lmask = CNST_LIMB(1) << (lindex % GMP_LIMB_BITS);
- for ( ; lindex <= bits; lindex += step) {
- bit_array[lindex / GMP_LIMB_BITS] |= lmask;
- lmask = lmask << maskrot | lmask >> (GMP_LIMB_BITS - maskrot);
- };
- }
- LOOP_ON_SIEVE_END;
-}
-
-#define BLOCK_SIZE 2048
-
-/* Fills bit_array with the characteristic function of composite
- numbers up to the parameter n. I.e. a bit set to "1" represent a
- composite, a "0" represent a prime.
-
- The primesieve_size(n) limbs pointed to by bit_array are
- overwritten. The returned value counts prime integers in the
- interval [4, n]. Note that n > 4.
-
- Even numbers and multiples of 3 are excluded "a priori", only
More information about the gmp-commit
mailing list