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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/cf919bf89833
changeset: 16332:cf919bf89833
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Mar 13 06:01:08 2014 +0100
description:
mini-gmp/mini-gmp.c: micro-optimizations.

details:   /var/hg/gmp/rev/249ecfa2f704
changeset: 16333:249ecfa2f704
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Mar 13 06:03:38 2014 +0100
description:
ChangeLog

details:   /var/hg/gmp/rev/bc1acf98be53
changeset: 16334:bc1acf98be53
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Mar 13 06:16:33 2014 +0100
description:
mini-gmp/mini-gmp.c (mpz__probab_prime_p): Comments.

details:   /var/hg/gmp/rev/f035584cd747
changeset: 16335:f035584cd747
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Mar 13 06:19:41 2014 +0100
description:
mini-gmp/tests/t-pprime_p.c (check_small): trigger the y<=1 branch.

diffstat:

 ChangeLog                   |   4 ++++
 mini-gmp/mini-gmp.c         |  19 +++++++++++--------
 mini-gmp/mini-gmp.h         |   3 +--
 mini-gmp/tests/t-pprime_p.c |   2 +-
 4 files changed, 17 insertions(+), 11 deletions(-)

diffs (93 lines):

diff -r 3f9086cd12d3 -r f035584cd747 ChangeLog
--- a/ChangeLog	Wed Mar 12 20:57:10 2014 +0100
+++ b/ChangeLog	Thu Mar 13 06:19:41 2014 +0100
@@ -1,3 +1,7 @@
+2014-02-21 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* mini-gmp/mini-gmp.c (mpz_probab_prime_p): Micro-optimisation.
+
 2014-03-12  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/x86/bd2/gmp-mparam.h: New file.
diff -r 3f9086cd12d3 -r f035584cd747 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c	Wed Mar 12 20:57:10 2014 +0100
+++ b/mini-gmp/mini-gmp.c	Thu Mar 13 06:19:41 2014 +0100
@@ -3363,7 +3363,7 @@
 gmp_millerrabin (const mpz_t n, const mpz_t nm1, mpz_t y,
 		 const mpz_t q, mp_bitcnt_t k)
 {
-  mp_bitcnt_t i;
+  assert (k > 0);
 
   /* Caller must initialize y to the base. */
   mpz_powm (y, y, q, n);
@@ -3371,12 +3371,15 @@
   if (mpz_cmp_ui (y, 1) == 0 || mpz_cmp (y, nm1) == 0)
     return 1;
 
-  for (i = 1; i < k; i++)
+  while (--k > 0)
     {
       mpz_powm_ui (y, y, 2, n);
       if (mpz_cmp (y, nm1) == 0)
 	return 1;
-      if (mpz_cmp_ui (y, 1) == 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, 1) <= 0)
 	return 0;
     }
   return 0;
@@ -3427,21 +3430,21 @@
   mpz_init (y);
 
   /* Find q and k, where q is odd and n = 1 + 2**k * q.  */
-  mpz_abs (nm1, n);
-  mpz_sub_ui (nm1, nm1, 1);
+  nm1->_mp_size = mpz_abs_sub_ui (nm1, n, 1);
   k = mpz_scan1 (nm1, 0);
   mpz_tdiv_q_2exp (q, nm1, k);
   
-  for (j = 0, is_prime = 1; is_prime && j < reps; j++)
+  for (j = 0, is_prime = 1; is_prime & (j < reps); j++)
     {
       mpz_set_ui (y, (unsigned long) j*j+j+41);
       if (mpz_cmp (y, nm1) >= 0)
 	{
-	  /* Don't try any further bases. */
+	  /* Don't try any further bases. This "early" break does not affect
+	     the result for any reasonable reps value (<=5000 was tested) */
 	  assert (j >= 30);
 	  break;
 	}
-      is_prime &= gmp_millerrabin (n, nm1, y, q, k);
+      is_prime = gmp_millerrabin (n, nm1, y, q, k);
     }
   mpz_clear (nm1);
   mpz_clear (q);
diff -r 3f9086cd12d3 -r f035584cd747 mini-gmp/mini-gmp.h
--- a/mini-gmp/mini-gmp.h	Wed Mar 12 20:57:10 2014 +0100
+++ b/mini-gmp/mini-gmp.h	Thu Mar 13 06:19:41 2014 +0100
@@ -215,8 +215,7 @@
 void mpz_fac_ui (mpz_t, unsigned long);
 void mpz_bin_uiui (mpz_t, unsigned long, unsigned long);
 
-int
-mpz_probab_prime_p (const mpz_t, int);
+int mpz_probab_prime_p (const mpz_t, int);
 
 int mpz_tstbit (const mpz_t, mp_bitcnt_t);
 void mpz_setbit (mpz_t, mp_bitcnt_t);
diff -r 3f9086cd12d3 -r f035584cd747 mini-gmp/tests/t-pprime_p.c
--- a/mini-gmp/tests/t-pprime_p.c	Wed Mar 12 20:57:10 2014 +0100
+++ b/mini-gmp/tests/t-pprime_p.c	Thu Mar 13 06:19:41 2014 +0100
@@ -93,7 +93,7 @@
 
   mpz_init (n);
 
-  for (i = 0; i < 300; i++)
+  for (i = 0; i < 1700; i++)
     {
       mpz_set_si (n, i);
       check_pn (n, isprime (i));