[Gmp-commit] /home/hgfiles/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Jan 6 20:15:08 CET 2010
details: /home/hgfiles/gmp/rev/d8cc718a2a9e
changeset: 13333:d8cc718a2a9e
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 06 18:55:41 2010 +0100
description:
Manual updates.
details: /home/hgfiles/gmp/rev/a602318a8423
changeset: 13334:a602318a8423
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 06 18:58:32 2010 +0100
description:
Update version numbers.
details: /home/hgfiles/gmp/rev/88051875b695
changeset: 13335:88051875b695
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 06 19:10:03 2010 +0100
description:
*** empty log message ***
details: /home/hgfiles/gmp/rev/a59704097650
changeset: 13336:a59704097650
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 06 19:40:56 2010 +0100
description:
One more np=scratch fix.
diffstat:
ChangeLog | 12 +++++++++++
Makefile.am | 2 +-
NEWS | 2 +-
doc/gmp.texi | 56 +++++++++++++++++++++++++++-------------------------
gmp-h.in | 8 +++---
mp-h.in | 2 +-
mpn/generic/div_q.c | 12 +++-------
7 files changed, 52 insertions(+), 42 deletions(-)
diffs (219 lines):
diff -r 745b770b85b2 -r a59704097650 ChangeLog
--- a/ChangeLog Wed Jan 06 18:44:56 2010 +0100
+++ b/ChangeLog Wed Jan 06 19:40:56 2010 +0100
@@ -1,5 +1,17 @@
2010-01-06 Torbjorn Granlund <tege at gmplib.org>
+ * Version 5.0.0 released.
+
+ * gmp-h.in (__GNU_MP__): Bump.
+ (__GNU_MP_VERSION,__GNU_MP_VERSION_MINOR,__GNU_MP_VERSION_PATCHLEVEL):
+ Bump version info.
+ * mp-h.in (__GNU_MP__): Bump.
+ * Makefile.am (LIBGMP_LT_*, LIBGMPXX_LT_*, LIBMP_LT_*):
+ Bump version info.
+
+ * doc/gmp.texi: Rewrite mpn_gcdext text. Remove some out-of-date
+ text in Algorithms chapter.
+
* mpn/generic/div_q.c: Properly handle np=scratch. Fix critical typo
in final adjustment code. Misc cleanups.
diff -r 745b770b85b2 -r a59704097650 Makefile.am
--- a/Makefile.am Wed Jan 06 18:44:56 2010 +0100
+++ b/Makefile.am Wed Jan 06 19:40:56 2010 +0100
@@ -65,7 +65,7 @@
# 4.3.0 8:0:5 5:0:1 4:14:1
# 4.3.1 8:1:5 5:1:1 4:15:1 WRONG Really used same as 4.3.0
# 4.3.2 8:2:5 5:2:1 4:16:1
-# 4.4.0 9:0:6 6:0:2 4:20:1 PRELIMINARY
+# 5.0.0 9:0:6 6:0:2 4:20:1 PRELIMINARY
#
# Starting at 3:0:0 is a slight abuse of the versioning system, but it
# ensures we're past soname libgmp.so.2, which was used on Debian GNU/Linux
diff -r 745b770b85b2 -r a59704097650 NEWS
--- a/NEWS Wed Jan 06 18:44:56 2010 +0100
+++ b/NEWS Wed Jan 06 19:40:56 2010 +0100
@@ -5,7 +5,7 @@
in any medium, provided this notice is preserved.
-Changes between GMP version 4.3.X and 4.4.0
+Changes between GMP version 4.3.X and 5.0.0
BUGS FIXED
* None (contains the same fixes as release 4.3.2).
diff -r 745b770b85b2 -r a59704097650 doc/gmp.texi
--- a/doc/gmp.texi Wed Jan 06 18:44:56 2010 +0100
+++ b/doc/gmp.texi Wed Jan 06 19:40:56 2010 +0100
@@ -5376,23 +5376,27 @@
@var{s2limb}. Both operands must be non-zero.
@end deftypefun
- at deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, mp_size_t *@var{r2n}, mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t *@var{s2p}, mp_size_t @var{s2n})
-Calculate the greatest common divisor of @{@var{s1p}, @var{s1n}@} and
-@{@var{s2p}, @var{s2n}@}. Store the gcd at @{@var{r1p}, @var{retval}@} and
-the first cofactor at @{@var{r2p}, *@var{r2n}@}, with *@var{r2n} negative if
-the cofactor is negative. @var{r1p} and @var{r2p} should each have room for
- at math{@var{s1n}+1} limbs, but the return value and value stored through
- at var{r2n} indicate the actual number produced.
-
- at math{@{@var{s1p}, @var{s1n}@} @ge{} @{@var{s2p}, @var{s2n}@}} is required,
-and both must be non-zero. The regions @{@var{s1p}, @math{@var{s1n}+1}@} and
-@{@var{s2p}, @math{@var{s2n}+1}@} are destroyed (i.e.@: the operands plus an
-extra limb past the end of each).
-
-The cofactor @var{r2} will satisfy @m{r_2 s_1 + k s_2 = r_1, @var{r2}*@var{s1}
-+ @var{k}*@var{s2} = @var{r1}}. The second cofactor @var{k} is not calculated
-but can easily be obtained from @m{(r_1 - r_2 s_1) / s_2, (@var{r1} -
- at var{r2}*@var{s1}) / @var{s2}} (this division will be exact).
+ at deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{gp}, mp_limb_t *@var{sp}, mp_size_t *@var{sn}, mp_limb_t *@var{up}, mp_size_t @var{un}, mp_limb_t *@var{vp}, mp_size_t @var{vn})
+Let @m{U, at var{U}} be defined by @{@var{up}, @var{un}@} and
+let @m{V, at var{V}} be defined by @{@var{vp}, @var{vn}@}.
+
+Compute the greatest common divisor @math{G} of @math{U} and @math{V}. Compute
+a cofactor @math{S} such that @math{G = US + VT}. The second cofactor @var{T}
+is not calculated but can easily be obtained from @m{(G - US) / V, (@var{G} -
+ at var{U}*@var{S}) / @var{V}} (the division will be exact). It is required that
+ at math{U @ge V > 0}.
+
+FIXME: Say something about the range of @math{S}.
+
+Store @math{G} at @var{gp} and let the return value define its limb count.
+Store @math{S} at @var{sp} and let |*@var{sn}| define its limb count. Some
+versions of GMP will make @math{S} negative; when this happens *@var{sn} will
+be negative. The areas at @var{gp} and @var{sp} should each have room for
+ at math{@var{un}+1} limbs.
+
+The areas @{@var{up}, @math{@var{un}+1}@} and @{@var{vp}, @math{@var{vn}+1}@}
+are destroyed (i.e.@: the input operands plus an extra limb past the end of
+each).
@end deftypefun
@deftypefun mp_size_t mpn_sqrtrem (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, const mp_limb_t *@var{sp}, mp_size_t @var{n})
@@ -8230,7 +8234,7 @@
@node Divide and Conquer Division, Exact Division, Basecase Division, Division Algorithms
@subsection Divide and Conquer Division
-For divisors larger than @code{DIV_DC_THRESHOLD}, division is done by dividing.
+For divisors larger than @code{DC_DIV_QR_THRESHOLD}, division is done by dividing.
Or to be precise by a recursive divide and conquer algorithm based on work by
Moenck and Borodin, Jebelean, and Burnikel and Ziegler (@pxref{References}).
@@ -8248,9 +8252,9 @@
These overheads mean that it's only when N/2 is above
@code{MUL_TOOM22_THRESHOLD} that divide and conquer is of use.
- at code{DIV_DC_THRESHOLD} is based on the divisor size N, so it will be somewhere
+ at code{DC_DIV_QR_THRESHOLD} is based on the divisor size N, so it will be somewhere
above twice @code{MUL_TOOM22_THRESHOLD}, but how much above depends on the
-CPU at . An optimized @code{mpn_mul_basecase} can lower @code{DIV_DC_THRESHOLD} a
+CPU at . An optimized @code{mpn_mul_basecase} can lower @code{DC_DIV_QR_THRESHOLD} a
little by offering a ready-made advantage over repeated @code{mpn_submul_1}
calls.
@@ -8674,11 +8678,7 @@
The modular multiplies and squares use either a simple division or the REDC
method by Montgomery (@pxref{References}). REDC is a little faster,
essentially saving N single limb divisions in a fashion similar to an exact
-remainder (@pxref{Exact Remainder}). The current REDC has some limitations.
-It's only @math{O(N^2)} so above @code{POWM_THRESHOLD} division becomes faster
-and is used. It doesn't attempt to detect small bases, but rather always uses
-a REDC form, which is usually a full size operand. And lastly it's only
-applied to odd moduli.
+remainder (@pxref{Exact Remainder}).
@node Root Extraction Algorithms, Radix Conversion Algorithms, Powering Algorithms, Algorithms
@@ -10354,13 +10354,15 @@
Niels M@"oller wrote the sub-quadratic GCD and extended GCD code, the
quadratic Hensel division code, and (with Torbj@"orn) the new divide and
conquer division code for GMP 4.3. Niels also helped implement the new Toom
-multiply code for GMP 4.3. He wrote the original version of mpn_mulmod_bnm1.
+multiply code for GMP 4.3 and implemented helper functions to simplify Toom
+evaluations for GMP 5.0. He wrote the original version of mpn_mulmod_bnm1.
Alberto Zanoni and Marco Bodrato suggested the unbalanced multiply strategy,
and found the optimal strategies for evaluation and interpolation in Toom
multiplication.
-Marco Bodrato helped implement the new Toom multiply code for GMP 4.3 and 4.4.
+Marco Bodrato helped implement the new Toom multiply code for GMP 4.3 and
+implemented most of the new Toom multiply and squaring code for 5.0.
He is the main author of the current mpn_mulmod_bnm1 and mpn_mullo_n. Marco
also wrote the functions mpn_invert and mpn_invertappr.
diff -r 745b770b85b2 -r a59704097650 gmp-h.in
--- a/gmp-h.in Wed Jan 06 18:44:56 2010 +0100
+++ b/gmp-h.in Wed Jan 06 19:40:56 2010 +0100
@@ -43,7 +43,7 @@
gmp.h and mp.h to allow both to be included in an application or during
the library build. */
#ifndef __GNU_MP__
-#define __GNU_MP__ 4
+#define __GNU_MP__ 5
#define __need_size_t /* tell gcc stddef.h we only want size_t */
#if defined (__cplusplus)
@@ -2271,9 +2271,9 @@
#define __GMP_CFLAGS "@CFLAGS@"
/* Major version number is the value of __GNU_MP__ too, above and in mp.h. */
-#define __GNU_MP_VERSION 4
-#define __GNU_MP_VERSION_MINOR 4
-#define __GNU_MP_VERSION_PATCHLEVEL -1
+#define __GNU_MP_VERSION 5
+#define __GNU_MP_VERSION_MINOR 0
+#define __GNU_MP_VERSION_PATCHLEVEL 0
#define __GMP_H__
#endif /* __GMP_H__ */
diff -r 745b770b85b2 -r a59704097650 mp-h.in
--- a/mp-h.in Wed Jan 06 18:44:56 2010 +0100
+++ b/mp-h.in Wed Jan 06 19:40:56 2010 +0100
@@ -26,7 +26,7 @@
gmp.h and mp.h to allow both to be included in an application or during
the library build. Use the t-gmp-mp-h.pl script to check. */
#ifndef __GNU_MP__
-#define __GNU_MP__ 4
+#define __GNU_MP__ 5
#define __need_size_t /* tell gcc stddef.h we only want size_t */
#if defined (__cplusplus)
diff -r 745b770b85b2 -r a59704097650 mpn/generic/div_q.c
--- a/mpn/generic/div_q.c Wed Jan 06 18:44:56 2010 +0100
+++ b/mpn/generic/div_q.c Wed Jan 06 19:40:56 2010 +0100
@@ -160,7 +160,7 @@
if (cy == 0)
qp[qn - 1] = qh;
}
- else /* divisior is already normalised */
+ else /* divisor is already normalised */
{
if (new_np != np)
MPN_COPY (new_np, np, nn);
@@ -204,6 +204,7 @@
we need to allocate separate space for new_np. */
new_np = TMP_ALLOC_LIMBS (new_nn + 1);
+
dh = dp[dn - 1];
if (LIKELY ((dh & GMP_NUMB_HIGHBIT) == 0))
{
@@ -241,14 +242,9 @@
if (cy == 0)
tp[qn] = qh;
}
- else /* divisior is already normalised */
+ else /* divisor is already normalised */
{
- new_nn = 2 * qn + 1;
- new_np = scratch;
- if (new_np != np)
- MPN_COPY (new_np, np + nn - new_nn, new_nn); /* pointless of MU will be used */
- else
- new_np += nn - new_nn;
+ MPN_COPY (new_np, np + nn - new_nn, new_nn); /* pointless of MU will be used */
new_dp = (mp_ptr) dp + dn - (qn + 1);
More information about the gmp-commit
mailing list