[Gmp-commit] /var/hg/gmp: 3 new changesets

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/529179d938d8
changeset: 16395:529179d938d8
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Wed May 21 09:42:08 2014 +0200
description:
mpn/generic/invert.c: remove unused TMP_MARK
mpn/generic/invertappr.c: Avoid a branch

details:   /var/hg/gmp/rev/54baa034ffd3
changeset: 16396:54baa034ffd3
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Wed May 21 09:48:26 2014 +0200
description:
mpz/millerrabin.c (millerrabin): Consider the rare case n is a power

details:   /var/hg/gmp/rev/d302a660e966
changeset: 16397:d302a660e966
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Wed May 21 09:48:34 2014 +0200
description:
ChangeLog

diffstat:

 ChangeLog                |   4 ++++
 mpn/generic/invert.c     |  14 ++++----------
 mpn/generic/invertappr.c |   5 ++++-
 mpz/millerrabin.c        |   8 ++++++--
 4 files changed, 18 insertions(+), 13 deletions(-)

diffs (92 lines):

diff -r 0f8b31a18f15 -r d302a660e966 ChangeLog
--- a/ChangeLog	Tue May 20 19:45:10 2014 +0200
+++ b/ChangeLog	Wed May 21 09:48:34 2014 +0200
@@ -5,6 +5,10 @@
 	* mini-gmp/mini-gmp.c: Likewise.
 	* rand/randmts.c: Likewise.
 
+	* mpn/generic/invert.c: Remove unused TMP_MARK.
+	* mpn/generic/invertappr.c: Avoid a branch.
+	* mpz/millerrabin.c (millerrabin): Consider the rare case n is a power.
+
 2014-05-15 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* mini-gmp/mini-gmp.c: Micro-optimisations.
diff -r 0f8b31a18f15 -r d302a660e966 mpn/generic/invert.c
--- a/mpn/generic/invert.c	Tue May 20 19:45:10 2014 +0200
+++ b/mpn/generic/invert.c	Wed May 21 09:48:34 2014 +0200
@@ -49,12 +49,8 @@
 
   if (n == 1)
     invert_limb (*ip, *dp);
-  else {
-    TMP_DECL;
-
-    TMP_MARK;
-    if (BELOW_THRESHOLD (n, INV_APPR_THRESHOLD))
-      {
+  else if (BELOW_THRESHOLD (n, INV_APPR_THRESHOLD))
+    {
 	/* Maximum scratch needed by this branch: 2*n */
 	mp_size_t i;
 	mp_ptr xp;
@@ -74,8 +70,8 @@
 	  /* FIXME: should we use dcpi1_div_q, for big sizes? */
 	  mpn_sbpi1_div_q (ip, xp, 2 * n, dp, n, inv.inv32);
 	}
-      }
-    else { /* Use approximated inverse; correct the result if needed. */
+    }
+  else { /* Use approximated inverse; correct the result if needed. */
       mp_limb_t e; /* The possible error in the approximate inverse */
 
       ASSERT ( mpn_invert_itch (n) >= mpn_invertappr_itch (n) );
@@ -88,7 +84,5 @@
 	if (! mpn_add (scratch, scratch, 2*n, dp, n))
 	  MPN_INCR_U (ip, n, 1); /* The value was wrong, correct it.  */
       }
-    }
-    TMP_FREE;
   }
 }
diff -r 0f8b31a18f15 -r d302a660e966 mpn/generic/invertappr.c
--- a/mpn/generic/invertappr.c	Tue May 20 19:45:10 2014 +0200
+++ b/mpn/generic/invertappr.c	Wed May 21 09:48:34 2014 +0200
@@ -106,8 +106,11 @@
     mp_size_t i;
     xp = tp + n + 2;				/* 2 * n limbs */
 
-    for (i = n - 1; i >= 0; i--)
+    /* n > 1 here */
+    i = n - 1;
+    do
       xp[i] = GMP_NUMB_MAX;
+    while (--i >= 0);
     mpn_com (xp + n, dp, n);
 
     /* Now xp contains B^2n - {dp,n}*B^n - 1 */
diff -r 0f8b31a18f15 -r d302a660e966 mpz/millerrabin.c
--- a/mpz/millerrabin.c	Tue May 20 19:45:10 2014 +0200
+++ b/mpz/millerrabin.c	Wed May 21 09:48:34 2014 +0200
@@ -9,7 +9,8 @@
    CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
    FUTURE GNU MP RELEASES.
 
-Copyright 1991, 1993, 1994, 1996-2002, 2005 Free Software Foundation, Inc.
+Copyright 1991, 1993, 1994, 1996-2002, 2005, 2014 Free Software
+Foundation, Inc.
 
 Contributed by John Amanatides.
 
@@ -117,7 +118,10 @@
       mpz_powm_ui (y, y, 2L, n);
       if (mpz_cmp (y, nm1) == 0)
 	return 1;
-      if (mpz_cmp_ui (y, 1L) == 0)
+      /* y == 1 means that the previous y was a non-trivial square root
+	 of 1 (mod n). y == 0 means that n is a power of the base.
+	 In either case, n is not prime. */
+      if (mpz_cmp_ui (y, 1L) <= 0)
 	return 0;
     }
   return 0;