[Gmpcommit] /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 +++++++++++++++++++++++++++
gmph.in  8 +++
mph.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 @@
20100106 Torbjorn Granlund <tege at gmplib.org>
+ * Version 5.0.0 released.
+
+ * gmph.in (__GNU_MP__): Bump.
+ (__GNU_MP_VERSION,__GNU_MP_VERSION_MINOR,__GNU_MP_VERSION_PATCHLEVEL):
+ Bump version info.
+ * mph.in (__GNU_MP__): Bump.
+ * Makefile.am (LIBGMP_LT_*, LIBGMPXX_LT_*, LIBMP_LT_*):
+ Bump version info.
+
+ * doc/gmp.texi: Rewrite mpn_gcdext text. Remove some outofdate
+ 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 nonzero.
@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 nonzero. 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 readymade 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 subquadratic 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 gmph.in
 a/gmph.in Wed Jan 06 18:44:56 2010 +0100
+++ b/gmph.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 mph.in
 a/mph.in Wed Jan 06 18:44:56 2010 +0100
+++ b/mph.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 tgmpmph.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 gmpcommit
mailing list