[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Apr 11 11:07:18 CEST 2012
details: /var/hg/gmp/rev/ab7afaf5104d
changeset: 14805:ab7afaf5104d
user: Torbjorn Granlund <tege at gmplib.org>
date: Sat Apr 07 11:41:59 2012 +0200
description:
Rewrite inner loop to use ctz table.
details: /var/hg/gmp/rev/3b4e2745b0de
changeset: 14806:3b4e2745b0de
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Apr 11 11:07:15 2012 +0200
description:
Trivial merge.
diffstat:
ChangeLog | 22 +++++++
gen-fac_ui.c | 33 -----------
mini-gmp/mini-gmp.c | 66 +++++++++++++++++++++++-
mini-gmp/mini-gmp.h | 6 +-
mini-gmp/tests/Makefile | 2 +-
mini-gmp/tests/t-reuse.c | 4 +-
mini-gmp/tests/t-root.c | 80 ++++++++++++++++++++++++++++
mpn/ia64/gcd_1.asm | 132 +++++++++++++++++++++-------------------------
mpz/2fac_ui.c | 7 +-
9 files changed, 238 insertions(+), 114 deletions(-)
diffs (truncated from 522 to 300 lines):
diff -r ebea11b4a7e6 -r 3b4e2745b0de ChangeLog
--- a/ChangeLog Thu Apr 05 10:08:42 2012 +0200
+++ b/ChangeLog Wed Apr 11 11:07:15 2012 +0200
@@ -1,3 +1,25 @@
+2012-04-11 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp/mini-gmp.h (mpz_root, mpz_rootrem): define (correctly).
+ * mini-gmp/mini-gmp.c (mpz_rootrem): Extended code from _root.
+ (mpz_root): Use mpz_rootrem.
+
+ * mini-gmp/tests/Makefile (CHECK_PROGRAMS): add t-root.
+ * mini-gmp/tests/t-root.c: New file
+ * mini-gmp/tests/t-reuse.c: Enable root{,rem} tests.
+
+2012-04-10 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * gen-fac_ui.c (mpz_root): Remove.
+ * mini-gmp/mini-gmp.c (mpz_root): New, support negative operands.
+ * mini-gmp/mini-gmp.h (mpz_root): define.
+ (mpz_out_str): Test also __STDIO_LOADED (for VMS).
+ * mpz/2fac_ui.c: Cosmetic change.
+
+2012-04-07 Torbjorn Granlund <tege at gmplib.org>
+
+ * mpn/ia64/gcd_1.asm: Rewrite inner loop to use ctz table.
+
2012-04-05 Torbjorn Granlund <tege at gmplib.org>
* mpn/powerpc64/p7/popcount.asm: Properly extend arg n for mode32.
diff -r ebea11b4a7e6 -r 3b4e2745b0de gen-fac_ui.c
--- a/gen-fac_ui.c Thu Apr 05 10:08:42 2012 +0200
+++ b/gen-fac_ui.c Wed Apr 11 11:07:15 2012 +0200
@@ -23,39 +23,6 @@
#include "bootstrap.c"
-/* x=floor(y^(1/z)) */
-void
-mpz_root (mpz_t x, mpz_t y, unsigned long z)
-{
- mpz_t t, u, v;
-
- if (mpz_cmp_ui (y, 1) <= 0)
- {
- mpz_set (x, y);
- return;
- }
- mpz_init (t);
- mpz_init (v);
- mpz_init_set_ui (u, 1);
- mpz_mul_2exp (u, u, mpz_sizeinbase (y, 2) / z + 1);
- do
- {
- mpz_pow_ui (t, u, z - 1);
- mpz_tdiv_q (t, y, t);
- mpz_mul_ui (v, u, z - 1);
- mpz_add (t, t, v);
- mpz_tdiv_q_ui (t, t, z);
- if (mpz_cmp (t, u) >= 0)
- break;
- mpz_set (u, t);
- }
- while (1);
- mpz_set (x, u);
- mpz_clear (u);
- mpz_clear (v);
- mpz_clear (t);
-}
-
/* returns 0 on success */
int
gen_consts (int numb, int nail, int limb)
diff -r ebea11b4a7e6 -r 3b4e2745b0de mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Thu Apr 05 10:08:42 2012 +0200
+++ b/mini-gmp/mini-gmp.c Wed Apr 11 11:07:15 2012 +0200
@@ -2938,7 +2938,7 @@
}
-/* Higher level operations (sqrt and pow) */
+/* Higher level operations (sqrt, pow and root) */
/* Compute s = floor(sqrt(u)) and r = u - s^2. Allows r == NULL */
void
@@ -3143,6 +3143,70 @@
mpz_clear (e);
}
+/* x=floor(y^(1/z)), r=y-x^z */
+void
+mpz_rootrem (mpz_t x, mpz_t r, const mpz_t y, unsigned long z)
+{
+ int sgn;
+ mpz_t t, u, v, ty;
+
+ sgn = y->_mp_size < 0;
+ if (sgn && (z & 1) == 0)
+ gmp_die ("mpz_rootrem: Negative argument, with even root.");
+ if (z == 0)
+ gmp_die ("mpz_rootrem: Zeroth root.");
+
+ if (mpz_cmp_ui (y, 1) <= 0) {
+ mpz_set (x, y);
+ if (r)
+ r->_mp_size = 0;
+ return;
+ }
+
+ ty->_mp_size = GMP_ABS (y->_mp_size);
+ ty->_mp_d = y->_mp_d;
+
+ mpz_init (t);
+ mpz_init (v);
+ mpz_init (u);
+ mpz_setbit (t, mpz_sizeinbase (ty, 2) / z + 1);
+
+ do {
+ mpz_set (u, t);
+ mpz_pow_ui (t, u, z - 1);
+ mpz_tdiv_q (t, ty, t);
+ mpz_mul_ui (v, u, z - 1);
+ mpz_add (t, t, v);
+ mpz_tdiv_q_ui (t, t, z);
+ } while (mpz_cmp (t, u) < 0);
+
+ if (r) {
+ mpz_pow_ui (t, u, z);
+ mpz_sub (r, y, t);
+ }
+ if (sgn)
+ mpz_neg (x, u);
+ else
+ mpz_set (x, u);
+ mpz_clear (u);
+ mpz_clear (v);
+ mpz_clear (t);
+}
+
+int
+mpz_root (mpz_t x, const mpz_t y, unsigned long z)
+{
+ int res;
+ mpz_t r;
+
+ mpz_init (r);
+ mpz_rootrem (x, r, y, z);
+ res = r->_mp_size == 0;
+ mpz_clear (r);
+
+ return res;
+}
+
/* Logical operations and bit manipulation. */
diff -r ebea11b4a7e6 -r 3b4e2745b0de mini-gmp/mini-gmp.h
--- a/mini-gmp/mini-gmp.h Thu Apr 05 10:08:42 2012 +0200
+++ b/mini-gmp/mini-gmp.h Wed Apr 11 11:07:15 2012 +0200
@@ -177,6 +177,9 @@
void mpz_powm (mpz_t, const mpz_t, const mpz_t, const mpz_t);
void mpz_powm_ui (mpz_t, const mpz_t, unsigned long, const mpz_t);
+void mpz_rootrem (mpz_t, mpz_t, const mpz_t, unsigned long);
+int mpz_root (mpz_t, const mpz_t, unsigned long);
+
int mpz_tstbit (const mpz_t, mp_bitcnt_t);
void mpz_setbit (mpz_t, mp_bitcnt_t);
void mpz_clrbit (mpz_t, mp_bitcnt_t);
@@ -230,7 +233,8 @@
|| defined (__STDIO__) /* Apple MPW MrC */ \
|| defined (_MSL_STDIO_H) /* Metrowerks */ \
|| defined (_STDIO_H_INCLUDED) /* QNX4 */ \
- || defined (_ISO_STDIO_ISO_H) /* Sun C++ */
+ || defined (_ISO_STDIO_ISO_H) /* Sun C++ */ \
+ || defined (__STDIO_LOADED) /* VMS */
size_t mpz_out_str (FILE *, int, const mpz_t);
#endif
diff -r ebea11b4a7e6 -r 3b4e2745b0de mini-gmp/tests/Makefile
--- a/mini-gmp/tests/Makefile Thu Apr 05 10:08:42 2012 +0200
+++ b/mini-gmp/tests/Makefile Wed Apr 11 11:07:15 2012 +0200
@@ -12,7 +12,7 @@
CHECK_PROGRAMS = t-add t-sub t-mul t-invert t-div t-div_2exp \
t-double t-gcd t-lcm \
- t-sqrt t-powm t-logops t-bitops t-scan t-str \
+ t-sqrt t-root t-powm t-logops t-bitops t-scan t-str \
t-reuse
MISC_OBJS = hex-random.o mini-random.o mini-gmp.o
diff -r ebea11b4a7e6 -r 3b4e2745b0de mini-gmp/tests/t-reuse.c
--- a/mini-gmp/tests/t-reuse.c Thu Apr 05 10:08:42 2012 +0200
+++ b/mini-gmp/tests/t-reuse.c Wed Apr 11 11:07:15 2012 +0200
@@ -361,7 +361,7 @@
if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0)
FAIL2 (mpz_sqrtrem, in1, NULL, NULL);
}
-#if 0
+
if (mpz_sgn (in1) >= 0)
{
mpz_root (ref1, in1, in2i % 0x1000 + 1);
@@ -394,7 +394,7 @@
if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0)
FAIL2 (mpz_rootrem, in1, in2, NULL);
}
-#endif
+
if (pass < reps / 2) /* run fewer tests since gcdext lots of time */
{
mpz_gcdext (ref1, ref2, ref3, in1, in2);
diff -r ebea11b4a7e6 -r 3b4e2745b0de mini-gmp/tests/t-root.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mini-gmp/tests/t-root.c Wed Apr 11 11:07:15 2012 +0200
@@ -0,0 +1,80 @@
+#include <limits.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "mini-random.h"
+
+#define MAXBITS 400
+#define COUNT 10000
+
+static void
+dump (const char *label, const mpz_t x)
+{
+ char *buf = mpz_get_str (NULL, 16, x);
+ fprintf (stderr, "%s: %s\n", label, buf);
+ free (buf);
+}
+
+/* Called when s is supposed to be floor(root(u,z)), and r = u - s^z */
+static int
+rootrem_valid_p (const mpz_t u, const mpz_t s, const mpz_t r, unsigned long z)
+{
+ mpz_t t;
+
+ mpz_init (t);
+ mpz_pow_ui (t, s, z);
+ mpz_sub (t, u, t);
+ if (mpz_sgn (t) != mpz_sgn(u) || mpz_cmp (t, r) != 0)
+ {
+ mpz_clear (t);
+ return 0;
+ }
+ mpz_add_ui (t, s, 1);
+ mpz_pow_ui (t, t, z);
+ if (mpz_cmpabs (t, u) <= 0)
+ {
+ mpz_clear (t);
+ return 0;
+ }
+
+ mpz_clear (t);
+ return 1;
+}
+
+int
+main (int argc, char **argv)
+{
+ unsigned i;
+ unsigned long e;
+ mpz_t u, s, r, bs;
+
+ hex_random_init ();
+
+ mpz_init (u);
+ mpz_init (s);
+ mpz_init (r);
+ mpz_init (bs);
+
+ for (i = 0; i < COUNT; i++)
+ {
+ mini_rrandomb (u, MAXBITS);
+ mini_rrandomb (bs, 10);
+ e = mpz_getlimbn (bs, 0) % mpz_sizeinbase (u, 2) + 2;
+ mpz_rootrem (s, r, u, e);
+
+ if (!rootrem_valid_p (u, s, r, e))
+ {
+ fprintf (stderr, "mpz_rootrem(%lu-th) failed:\n", e);
+ dump ("u", u);
+ dump ("root", s);
+ dump ("rem", r);
+ abort ();
+ }
+ }
+ mpz_clear (bs);
+ mpz_clear (u);
+ mpz_clear (s);
+ mpz_clear (r);
+
+ return 0;
+}
diff -r ebea11b4a7e6 -r 3b4e2745b0de mpn/ia64/gcd_1.asm
--- a/mpn/ia64/gcd_1.asm Thu Apr 05 10:08:42 2012 +0200
+++ b/mpn/ia64/gcd_1.asm Wed Apr 11 11:07:15 2012 +0200
@@ -1,8 +1,9 @@
dnl Itanium-2 mpn_gcd_1 -- mpn by 1 gcd.
More information about the gmp-commit
mailing list