[Gmp-commit] /var/hg/gmp-proj/mini-gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Jan 7 23:26:36 CET 2012
details: /var/hg/gmp-proj/mini-gmp/rev/df583d064cf0
changeset: 54:df583d064cf0
user: Niels M?ller <nisse at lysator.liu.se>
date: Sat Jan 07 15:11:40 2012 +0100
description:
Use LDFLAGS.
details: /var/hg/gmp-proj/mini-gmp/rev/bce64808b6df
changeset: 55:bce64808b6df
user: Niels M?ller <nisse at lysator.liu.se>
date: Sat Jan 07 20:51:18 2012 +0100
description:
Implemented mpz_cmp_d (not yet tested).
details: /var/hg/gmp-proj/mini-gmp/rev/27bedcc7be34
changeset: 56:27bedcc7be34
user: Niels M?ller <nisse at lysator.liu.se>
date: Sat Jan 07 23:26:00 2012 +0100
description:
Implemented mpz_size, mpz_getlimbn, mpz_popcount, mpz_hamdist. Fixed
typing of exponent bit in mpz_ui_pow_ui.
diffstat:
mini-gmp.c | 181 +++++++++++++++++++++++++++++++++++++++++++++++++++++---
mini-gmp.h | 6 +
tests/Makefile | 3 +-
3 files changed, 177 insertions(+), 13 deletions(-)
diffs (288 lines):
diff -r b8e2f8a30856 -r 27bedcc7be34 mini-gmp.c
--- a/mini-gmp.c Sat Jan 07 14:50:51 2012 +0100
+++ b/mini-gmp.c Sat Jan 07 23:26:00 2012 +0100
@@ -28,20 +28,11 @@
/* Missing functions, needed by guile:
- mpz_cmp_d
mpz_divisible_p
mpz_divisible_ui_p
mpz_export
- mpz_getlimbn
- mpz_hamdist
mpz_lcm_ui
- mpz_popcount
*/
-/* Missing functions for gmp/gen-bases.c:
-
- mpz_out_str
- mpz_tdiv_q_2exp
-*/
#include <assert.h>
#include <ctype.h>
@@ -62,6 +53,9 @@
#define GMP_HLIMB_BIT ((mp_limb_t) 1 << (GMP_LIMB_BITS / 2))
#define GMP_LLIMB_MASK (GMP_HLIMB_BIT - 1)
+#define GMP_ULONG_BITS (sizeof(unsigned long) * CHAR_BIT)
+#define GMP_ULONG_HIGHBIT ((unsigned long) 1 << (GMP_ULONG_BITS - 1))
+
#define GMP_ABS(x) ((x) >= 0 ? (x) : -(x))
#define GMP_MIN(a, b) ((a) < (b) ? (a) : (b))
@@ -1391,6 +1385,21 @@
return u->_mp_size == 0 ? 0 : u->_mp_d[0];
}
+size_t
+mpz_size (const mpz_t u)
+{
+ return GMP_ABS (u->_mp_size);
+}
+
+mp_limb_t
+mpz_getlimbn (const mpz_t u, mp_size_t n)
+{
+ if (n >= 0 && n < GMP_ABS (u->_mp_size))
+ return u->_mp_d[n];
+ else
+ return 0;
+}
+
/* Conversions and comparison to double. */
void
@@ -1461,7 +1470,7 @@
double x;
double B = 2.0 * (double) GMP_LIMB_HIGHBIT;
- un = GMP_ABS (u->_mp_size);
+ un = GMP_ABS (u->_mp_size);
if (un == 0)
return 0.0;
@@ -1476,6 +1485,66 @@
return x;
}
+int
+mpz_cmp_d (const mpz_t x, double d)
+{
+ mp_size_t xn = x->_mp_size;
+ int sign;
+ double B, Bi;
+ mp_size_t i;
+
+ if (xn == 0)
+ {
+ if (d < 0)
+ return 1;
+ else if (d > 0)
+ return -1;
+ else
+ return 0;
+ }
+
+ if (xn < 0)
+ {
+ xn = -xn;
+ d = -d;
+ sign = -1;
+ }
+ else
+ sign = 1;
+
+ if (d < 1.0)
+ return sign;
+
+ B = 2.0 * (double) GMP_LIMB_HIGHBIT;
+ Bi = 1.0 / B;
+ for (i = 1; i < xn; i++)
+ {
+ d *= Bi;
+ if (d < 1.0)
+ return sign;
+ }
+ if (d >= B)
+ return -sign;
+
+ for (i = xn; i-- > 0; i++)
+ {
+ mp_limb_t f, xl;
+
+ f = (mp_limb_t) d;
+ xl = x->_mp_d[i];
+ if (xl > f)
+ return sign;
+ else if (xl < f)
+ return -sign;
+ d = B * (d - f);
+ }
+
+ if (d > 0)
+ return -sign;
+ else
+ return 0;
+}
+
/* MPN comparisons and the like. */
int
@@ -2659,10 +2728,10 @@
void
mpz_ui_pow_ui (mpz_t r, unsigned long b, unsigned long e)
{
- mp_limb_t bit;
+ unsigned long bit;
mpz_set_ui (r, 1);
- for (bit = GMP_LIMB_HIGHBIT; bit > 0; bit >>= 1)
+ for (bit = GMP_ULONG_HIGHBIT; bit > 0; bit >>= 1)
{
mpz_mul (r, r, r);
if (e & bit)
@@ -3137,6 +3206,94 @@
r->_mp_size = rx ? -un : un;
}
+static unsigned
+gmp_popcount_limb (mp_limb_t x)
+{
+ unsigned c;
+
+ /* Do 16 bits at a time, to avoid limb-sized constants. */
+ for (c = 0; x > 0; x >>= 16)
+ {
+ unsigned w = ((x & 0xaaaa) >> 1) + (x & 0x5555);
+ w = ((w & 0xcccc) >> 2) + (w & 0x3333);
+ w = ((w & 0xf0f0) >> 4) + (w & 0x0f0f);
+ w = (w >> 8) + (w & 0x00ff);
+ c += w;
+ }
+ return c;
+}
+
+mp_bitcnt_t
+mpz_popcount (const mpz_t u)
+{
+ mp_size_t un, i;
+ mp_bitcnt_t c;
+
+ un = u->_mp_size;
+
+ if (un < 0)
+ return ~(mp_bitcnt_t) 0;
+
+ for (c = 0, i = 0; i < un; i++)
+ c += gmp_popcount_limb (u->_mp_d[i]);
+
+ return c;
+}
+
+mp_bitcnt_t
+mpz_hamdist (const mpz_t u, const mpz_t v)
+{
+ mp_size_t un, vn, i;
+ mp_limb_t uc, vc, ul, vl, comp;
+ mp_srcptr up, vp;
+ mp_bitcnt_t c;
+
+ un = u->_mp_size;
+ vn = v->_mp_size;
+
+ if ( (un ^ vn) < 0)
+ return ~(mp_bitcnt_t) 0;
+
+ if (un < 0)
+ {
+ assert (vn < 0);
+ un = -un;
+ vn = -vn;
+ uc = vc = 1;
+ comp = - (mp_limb_t) 1;
+ }
+ else
+ uc = vc = comp = 0;
+
+ up = u->_mp_d;
+ vp = v->_mp_d;
+
+ if (un < vn)
+ MPN_SRCPTR_SWAP (up, un, vp, vn);
+
+ for (i = 0, c = 0; i < vn; i++)
+ {
+ ul = (up[i] ^ comp) + uc;
+ uc = ul < uc;
+
+ vl = (vp[i] ^ comp) + vc;
+ vc = vl < vc;
+
+ c += gmp_popcount_limb (ul ^ vl);
+ }
+ assert (vc == 0);
+
+ for (; i < vn; i++)
+ {
+ ul = (up[i] ^ comp) + uc;
+ uc = ul < uc;
+
+ c += gmp_popcount_limb (ul ^ comp);
+ }
+
+ return c;
+}
+
/* MPZ base conversion. */
diff -r b8e2f8a30856 -r 27bedcc7be34 mini-gmp.h
--- a/mini-gmp.h Sat Jan 07 14:50:51 2012 +0100
+++ b/mini-gmp.h Sat Jan 07 23:26:00 2012 +0100
@@ -92,6 +92,7 @@
int mpz_cmp (const mpz_t, const mpz_t);
int mpz_cmpabs_ui (const mpz_t, unsigned long);
int mpz_cmpabs (const mpz_t, const mpz_t);
+int mpz_cmp_d (const mpz_t, double);
void mpz_abs (mpz_t, const mpz_t);
void mpz_neg (mpz_t, const mpz_t);
@@ -154,11 +155,16 @@
void mpz_ior (mpz_t, const mpz_t, const mpz_t);
void mpz_xor (mpz_t, const mpz_t, const mpz_t);
+mp_bitcnt_t mpz_popcount (const mpz_t);
+mp_bitcnt_t mpz_hamdist (const mpz_t, const mpz_t);
+
int mpz_fits_slong_p (const mpz_t);
int mpz_fits_ulong_p (const mpz_t);
long int mpz_get_si (const mpz_t);
unsigned long int mpz_get_ui (const mpz_t);
double mpz_get_d (const mpz_t);
+size_t mpz_size (const mpz_t);
+mp_limb_t mpz_getlimbn (const mpz_t, mp_size_t);
void mpz_set_si (mpz_t, signed long int);
void mpz_set_ui (mpz_t, unsigned long int);
diff -r b8e2f8a30856 -r 27bedcc7be34 tests/Makefile
--- a/tests/Makefile Sat Jan 07 14:50:51 2012 +0100
+++ b/tests/Makefile Sat Jan 07 23:26:00 2012 +0100
@@ -3,6 +3,7 @@
CC = gcc
OPTFLAGS = -O
CFLAGS = $(OPTFLAGS) -Wall -g -I ..
+LDFLAGS =
LIBS = -lgmp -lm -lmcheck
@@ -29,7 +30,7 @@
$(CC) $(CFLAGS) -c ../mini-gmp.c -o mini-gmp.o
%: %.o $(MISC_OBJS)
- $(CC) $^ $(LIBS) -o $@
+ $(CC) $(LDFLAGS) $^ $(LIBS) -o $@
check: $(CHECK_PROGRAMS)
./run-tests $(CHECK_PROGRAMS)
More information about the gmp-commit
mailing list