[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