[Gmp-commit] /home/hgfiles/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Thu Dec 31 18:22:59 CET 2009
details: /home/hgfiles/gmp/rev/75be8c520c6e
changeset: 13281:75be8c520c6e
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Dec 31 18:04:00 2009 +0100
description:
Permit N = R for mpn_tdiv_qr.
details: /home/hgfiles/gmp/rev/fddf0c4b7bf4
changeset: 13282:fddf0c4b7bf4
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Dec 31 18:05:15 2009 +0100
description:
Handle numerator/remainder overlap in MU case.
details: /home/hgfiles/gmp/rev/4b0d5f8eb266
changeset: 13283:4b0d5f8eb266
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Dec 31 18:06:21 2009 +0100
description:
Change some tests to try larger arguments.
details: /home/hgfiles/gmp/rev/0df04d180ab6
changeset: 13284:0df04d180ab6
user: Torbjorn Granlund <tege at gmplib.org>
date: Thu Dec 31 18:22:52 2009 +0100
description:
Add items.
diffstat:
ChangeLog | 15 +++++++++++++++
NEWS | 18 +++++++++++++-----
doc/gmp.texi | 8 ++++----
mpn/generic/tdiv_qr.c | 10 ++++++----
tests/mpz/convert.c | 13 ++++++-------
tests/mpz/dive.c | 9 ++++-----
tests/mpz/reuse.c | 10 +++++-----
tests/mpz/t-gcd.c | 9 ++++-----
tests/mpz/t-powm.c | 5 ++---
tests/mpz/t-root.c | 9 ++++-----
tests/mpz/t-sqrtrem.c | 9 ++++-----
tests/mpz/t-tdiv.c | 5 ++---
tests/tests.h | 29 +++++++++++++++++++++++++++++
13 files changed, 98 insertions(+), 51 deletions(-)
diffs (truncated from 416 to 300 lines):
diff -r c76ca84094b5 -r 0df04d180ab6 ChangeLog
--- a/ChangeLog Thu Dec 31 12:20:47 2009 +0100
+++ b/ChangeLog Thu Dec 31 18:22:52 2009 +0100
@@ -1,3 +1,18 @@
+2009-12-31 Torbjorn Granlund <tege at gmplib.org>
+
+ * mpn/generic/tdiv_qr.c: Handle numerator/remainder overlap in MU case.
+
+ * tests/tests.h (TESTS_REPS): New macro.
+ * tests/mpz/dive.c: Use larger operands, decrease default reps, use
+ TESTS_REPS.
+ * tests/mpz/convert.c: Likewise.
+ * tests/mpz/t-sqrtrem.c: Likewise.
+ * tests/mpz/reuse: Likewise.
+ * tests/mpz/t-root.c: Likewise.
+ * tests/mpz/t-tdiv.c: Likewise.
+ * tests/mpz/t-gcd.c: Likewise.
+ * tests/mpz/t-powm.c: Likewise.
+
2009-12-31 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mpn/generic/toom8_sqr.c (SQR_TOOM8_MAX): Avoid overflow.
diff -r c76ca84094b5 -r 0df04d180ab6 NEWS
--- a/NEWS Thu Dec 31 12:20:47 2009 +0100
+++ b/NEWS Thu Dec 31 18:22:52 2009 +0100
@@ -23,14 +23,17 @@
addition of many new Toom function, and by selecting underlying
functions better from the main multiply functions.
- * Division has been overhauled, for both small and large operands:
+ * Division and mod have been overhauled:
(1) Plain "schoolbook" division is reimplemented using faster quotient
approximation.
(2) Division Q = N/D, R = N mod D where both the quotient and remainder
are needed now runs in time O(M(log(N))). This is an improvement of
a factor log(log(N))
- (3) Division where just the quotient needed is now O(M(log(Q))) on
+ (3) Division where just the quotient is needed is now O(M(log(Q))) on
average.
+ (4) Modulo operations using Montgomery REDC form now take time O(M(n)).
+ (5) Exact division Q = N/D by means of mpz_divexact has been improved
+ for all sizes, and now runs in time O(M(log(N))).
* The function mpz_powm is now faster for all sizes. Its complexity has
gone from O(M(n)log(n)m) to O(M(n)m) where n is the size of the modulo
@@ -45,9 +48,6 @@
improved by using well-tuned Newton iterations, and wrap-around
multiplication using mpn_mulmod_bnm1.
- * Exact division Q = N/D by means of mpz_divexact has been improved for
- all sizes, and now runs in time O(M(log(N))).
-
* A new algorithm makes mpz_perfect_power_p asymptotically faster.
* The function mpz_remove uses a much faster algorithm, is better tuned,
@@ -69,6 +69,8 @@
* A new type, mp_bitcnt_t for bignum bit counts, has been introduced.
+ * Support for Windows64 through mingw64 has been added.
+
* The cofactors of mpz_gcdext and mpn_gcdext are now more strictly
normalised, returning to how GMP 4.2 worked. (Note that also release
4.3.2 has this change.)
@@ -77,6 +79,12 @@
* The mpn_mul function should no longer be used for squaring,
instead use the new mpn_sqr.
+ * The algorithm selection has been improved, the number of thresholds have
+ more than doubled, and the tuning and use of existing thresholds have
+ been improved.
+
+ * The tune/speed program can measure many of new functions.
+
* The mpn_bdivmod function has been removed. We do not consider this an
incompatible change, since the function was marked as preliminary.
diff -r c76ca84094b5 -r 0df04d180ab6 doc/gmp.texi
--- a/doc/gmp.texi Thu Dec 31 12:20:47 2009 +0100
+++ b/doc/gmp.texi Thu Dec 31 18:22:52 2009 +0100
@@ -5245,10 +5245,10 @@
at @{@var{qp}, @var{nn}@minus{}@var{dn}+1@} and the remainder at @{@var{rp},
@var{dn}@}. The quotient is rounded towards 0.
-No overlap is permitted between arguments. @var{nn} must be greater than or
-equal to @var{dn}. The most significant limb of @var{dp} must be non-zero.
-The @var{qxn} operand must be zero.
- at comment FIXME: Relax overlap requirements!
+No overlap is permitted between arguments, except that @var{np} might equal
+ at var{rp}. The dividend size @var{nn} must be greater than or equal to divisor
+size @var{dn}. The most significant limb of the divisor must be non-zero. The
+ at var{qxn} operand must be zero.
@end deftypefun
@deftypefun mp_limb_t mpn_divrem (mp_limb_t *@var{r1p}, mp_size_t @var{qxn}, mp_limb_t *@var{rs2p}, mp_size_t @var{rs2n}, const mp_limb_t *@var{s3p}, mp_size_t @var{s3n})
diff -r c76ca84094b5 -r 0df04d180ab6 mpn/generic/tdiv_qr.c
--- a/mpn/generic/tdiv_qr.c Thu Dec 31 12:20:47 2009 +0100
+++ b/mpn/generic/tdiv_qr.c Thu Dec 31 18:22:52 2009 +0100
@@ -6,8 +6,7 @@
Preconditions:
1. The most significant limb of of the divisor must be non-zero.
- 2. No argument overlap is permitted. (??? relax this ???)
- 3. nn >= dn, even if qxn is non-zero. (??? relax this ???)
+ 2. nn >= dn, even if qxn is non-zero. (??? relax this ???)
The time complexity of this is O(qn*qn+M(dn,qn)), where M(m,n) is the time
complexity of multiplication.
@@ -270,8 +269,11 @@
{
mp_size_t itch = mpn_mu_div_qr_itch (2 * qn, qn, 0);
mp_ptr scratch = TMP_ALLOC_LIMBS (itch);
- mpn_mu_div_qr (qp, rp, n2p, 2 * qn, d2p, qn, scratch);
- MPN_COPY (n2p, rp, qn);
+ mp_ptr r2p = rp;
+ if (np == r2p) /* If N and R share space, put ... */
+ r2p += nn - qn; /* intermediate remainder at N's upper end. */
+ mpn_mu_div_qr (qp, r2p, n2p, 2 * qn, d2p, qn, scratch);
+ MPN_COPY (n2p, r2p, qn);
}
}
diff -r c76ca84094b5 -r 0df04d180ab6 tests/mpz/convert.c
--- a/tests/mpz/convert.c Thu Dec 31 12:20:47 2009 +0100
+++ b/tests/mpz/convert.c Thu Dec 31 18:22:52 2009 +0100
@@ -78,13 +78,12 @@
size_t len;
tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
rands = RANDS;
mpz_init (bs);
- if (argc == 2)
- reps = atoi (argv[1]);
-
mpz_init (op1);
mpz_init (op2);
@@ -93,8 +92,8 @@
/* 1. Generate random mpz_t and convert to a string and back to mpz_t
again. */
mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 15 + 2; /* 2..16 */
- mpz_urandomb (bs, rands, size_range); /* 3..65536 bits */
+ size_range = mpz_get_ui (bs) % 17 + 2; /* 2..18 */
+ mpz_urandomb (bs, rands, size_range); /* 3..262144 bits */
size = mpz_get_ui (bs);
mpz_rrandomb (op1, rands, size);
@@ -127,8 +126,8 @@
/* 2. Generate random string and convert to mpz_t and back to a string
again. */
mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 14 + 1; /* 1..14 */
- mpz_urandomb (bs, rands, size_range); /* 1..16384 digits */
+ size_range = mpz_get_ui (bs) % 16 + 1; /* 1..16 */
+ mpz_urandomb (bs, rands, size_range); /* 1..65536 digits */
len = mpz_get_ui (bs) + 1;
buf = (*__gmp_allocate_func) (len + 1);
if (base == 0)
diff -r c76ca84094b5 -r 0df04d180ab6 tests/mpz/dive.c
--- a/tests/mpz/dive.c Thu Dec 31 12:20:47 2009 +0100
+++ b/tests/mpz/dive.c Thu Dec 31 18:22:52 2009 +0100
@@ -31,21 +31,20 @@
mpz_t prod, quot;
mp_size_t size;
int i;
- int reps = 200000;
+ int reps = 5000;
gmp_randstate_ptr rands;
mpz_t bs;
unsigned long bsi, size_range;
tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
rands = RANDS;
mp_trace_base = -16;
mpz_init (bs);
- if (argc == 2)
- reps = atoi (argv[1]);
-
mpz_init (op1);
mpz_init (op2);
mpz_init (prod);
@@ -54,7 +53,7 @@
for (i = 0; i < reps; i++)
{
mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 10 + 2; /* 0..2047 bit operands */
+ size_range = mpz_get_ui (bs) % 17 + 2; /* 0..2047 bit operands */
mpz_urandomb (bs, rands, size_range);
size = mpz_get_ui (bs);
diff -r c76ca84094b5 -r 0df04d180ab6 tests/mpz/reuse.c
--- a/tests/mpz/reuse.c Thu Dec 31 12:20:47 2009 +0100
+++ b/tests/mpz/reuse.c Thu Dec 31 18:22:52 2009 +0100
@@ -180,11 +180,12 @@
#endif
+
int
main (int argc, char **argv)
{
int i;
- int pass, reps = 1000;
+ int pass, reps = 100;
mpz_t in1, in2, in3;
unsigned long int in2i;
mp_size_t size;
@@ -198,13 +199,12 @@
unsigned long bsi, size_range;
tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
rands = RANDS;
mpz_init (bs);
- if (argc == 2)
- reps = atoi (argv[1]);
-
mpz_init (in1);
mpz_init (in2);
mpz_init (in3);
@@ -219,7 +219,7 @@
for (pass = 1; pass <= reps; pass++)
{
mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 12 + 2;
+ size_range = mpz_get_ui (bs) % 17 + 2;
mpz_urandomb (bs, rands, size_range);
size = mpz_get_ui (bs);
diff -r c76ca84094b5 -r 0df04d180ab6 tests/mpz/t-gcd.c
--- a/tests/mpz/t-gcd.c Thu Dec 31 12:20:47 2009 +0100
+++ b/tests/mpz/t-gcd.c Thu Dec 31 18:22:52 2009 +0100
@@ -108,12 +108,11 @@
gmp_randstate_ptr rands;
mpz_t bs;
unsigned long bsi, size_range;
- int reps = 100;
-
- if (argc == 2)
- reps = atoi (argv[1]);
+ int reps = 200;
tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
rands = RANDS;
check_data ();
@@ -152,7 +151,7 @@
of that other ASSERTs are triggered before it. */
mpz_urandomb (bs, rands, 32);
- size_range = mpz_get_ui (bs) % 13 + 2;
+ size_range = mpz_get_ui (bs) % 17 + 2;
mpz_urandomb (bs, rands, size_range);
mpz_urandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_BITSIZE);
diff -r c76ca84094b5 -r 0df04d180ab6 tests/mpz/t-powm.c
--- a/tests/mpz/t-powm.c Thu Dec 31 12:20:47 2009 +0100
+++ b/tests/mpz/t-powm.c Thu Dec 31 18:22:52 2009 +0100
@@ -40,13 +40,12 @@
unsigned long bsi, size_range;
tests_start ();
+ TESTS_REPS (reps, argv, argc);
+
rands = RANDS;
mpz_init (bs);
- if (argc == 2)
- reps = atoi (argv[1]);
-
mpz_init (base);
mpz_init (exp);
mpz_init (mod);
diff -r c76ca84094b5 -r 0df04d180ab6 tests/mpz/t-root.c
--- a/tests/mpz/t-root.c Thu Dec 31 12:20:47 2009 +0100
+++ b/tests/mpz/t-root.c Thu Dec 31 18:22:52 2009 +0100
@@ -98,20 +98,19 @@
mpz_t root1;
mp_size_t x2_size;
int i;
- int reps = 20000;
+ int reps = 500;
unsigned long nth;
gmp_randstate_ptr rands;
More information about the gmp-commit
mailing list