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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/43076be6de30
changeset: 18048:43076be6de30
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Mar 09 16:47:38 2020 +0100
description:
mpn/generic/mulmod_bnm1.c (mpn_bc_mulmod_bnp1): Simplify special cases.

details:   /var/hg/gmp/rev/8b37c2b90379
changeset: 18049:8b37c2b90379
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Mar 09 16:54:36 2020 +0100
description:
mpz/bin_ui.c (rek_raising_fac4): Reduce allocations

details:   /var/hg/gmp/rev/d302798cd0a2
changeset: 18050:d302798cd0a2
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Mar 09 17:01:17 2020 +0100
description:
mpz/bin_ui.c (mpz_bin_ui): Siplify special cases.

diffstat:

 mpn/generic/mulmod_bnm1.c |  11 +-----
 mpz/bin_ui.c              |  75 +++++++++++++++++++++++-----------------------
 2 files changed, 39 insertions(+), 47 deletions(-)

diffs (133 lines):

diff -r bcca14c8a090 -r d302798cd0a2 mpn/generic/mulmod_bnm1.c
--- a/mpn/generic/mulmod_bnm1.c	Thu Mar 05 00:43:26 2020 +0100
+++ b/mpn/generic/mulmod_bnm1.c	Mon Mar 09 17:01:17 2020 +0100
@@ -1,4 +1,3 @@
-
 /* mulmod_bnm1.c -- multiplication mod B^n-1.
 
    Contributed to the GNU project by Niels Möller, Torbjorn Granlund and
@@ -74,14 +73,8 @@
 
   if (UNLIKELY (ap[rn] | bp [rn]))
     {
-      if (UNLIKELY (ap[rn] & bp [rn]))
-	{
-	  *rp = 1;
-	  MPN_FILL (rp + 1, rn, 0);
-	  return;
-	}
-      else if (bp[rn] == 0)
-	cy = mpn_neg (rp, bp, rn);
+      if (ap[rn])
+	cy = bp [rn] + mpn_neg (rp, bp, rn);
       else /* ap[rn] == 0 */
 	cy = mpn_neg (rp, ap, rn);
     }
diff -r bcca14c8a090 -r d302798cd0a2 mpz/bin_ui.c
--- a/mpz/bin_ui.c	Thu Mar 05 00:43:26 2020 +0100
+++ b/mpz/bin_ui.c	Mon Mar 09 17:01:17 2020 +0100
@@ -69,7 +69,7 @@
 #else
   ASSERT (SIZ (r) > 0);
   MPN_INCR_U (PTR (r), SIZ (r) + 1, in);
-  SIZ (r) += (PTR (r)[SIZ (r)] != 0);
+  SIZ (r) += PTR (r)[SIZ (r)];
 #endif
 }
 
@@ -146,22 +146,17 @@
       mpz_t lt;
       unsigned long int m;
 
+      ALLOC (lt) = 0;
+      SIZ (lt) = 0;
+      if (t == NULL)
+	t = lt;
       m = ((k + lk) >> 1) + 1;
       rek_raising_fac4 (r, p, P, k, m, t);
 
       posmpz_inc_ui (p, 4*m+2);
       mpz_addmul_ui (P, p, 4*m);
       posmpz_dec_ui (P, m);
-      if (t == NULL)
-	{
-	  mpz_init_set (lt, P);
-	  t = lt;
-	}
-      else
-	{
-	  ALLOC (lt) = 0;
-	  mpz_set (t, P);
-	}
+      mpz_set (t, P);
       rek_raising_fac4 (t, p, P, m - 1, lk, NULL);
 
       mpz_mul (r, r, t);
@@ -384,36 +379,40 @@
 	  MPZ_NEWALLOC (r, 1)[0] = 1;
 	}
 #if APARTAJ_KALKULOJ > 2
-      else if (k == 2)
+      else if (k > 1)
 	{
-	  mpz_add_ui (ni, ni, 1);
-	  mpz_mul (r, ni, ni);
-	  mpz_add (r, r, ni);
-	  posmpz_rsh1 (r);
-	}
-#endif
+	  mpz_add_ui (ni, ni, 1 + (APARTAJ_KALKULOJ > 2 && k > 2));
+	  mpz_mul (r, ni, ni); /* r = (n + (k>2))^2 */
+	  if (APARTAJ_KALKULOJ == 2 || k == 2)
+	    {
+	      mpz_add (r, r, ni); /* n^2+n= n(n+1) */
+	      posmpz_rsh1 (r);
+	    }
 #if APARTAJ_KALKULOJ > 3
-      else if (k > 2)
-	{ /* k = 3, 4 */
-	  mpz_add_ui (ni, ni, 2); /* n+1 */
-	  mpz_mul (r, ni, ni); /* (n+1)^2 */
-	  mpz_sub_ui (r, r, 1); /* (n+1)^2-1 */
-	  if (k == 3)
-	    {
-	      mpz_mul (r, r, ni); /* ((n+1)^2-1)(n+1) = n(n+1)(n+2) */
-	      /* mpz_divexact_ui (r, r, 6); /\* 6=3<<1; div_by3 ? *\/ */
-	      mpn_pi1_bdiv_q_1 (PTR(r), PTR(r), SIZ(r), 3, GMP_NUMB_MASK/3*2+1, 1);
-	      MPN_NORMALIZE_NOT_ZERO (PTR(r), SIZ(r));
+#if APARTAJ_KALKULOJ != 5
+#error Not implemented! 3 < APARTAJ_KALKULOJ != 5
+#endif
+	  else /* k > 2 */
+	    { /* k = 3, 4 */
+	      mpz_sub_ui (r, r, 1); /* (n+1)^2-1 */
+	      if (k == 3)
+		{
+		  mpz_mul (r, r, ni); /* ((n+1)^2-1)(n+1) = n(n+1)(n+2) */
+		  /* mpz_divexact_ui (r, r, 6); /\* 6=3<<1; div_by3 ? *\/ */
+		}
+	      else /* k = 4 */
+		{
+		  mpz_add (ni, ni, r); /* (n+1)^2+n */
+		  mpz_mul (r, ni, ni); /* ((n+1)^2+n)^2 */
+		  /* We should subtract one: ((n+1)^2+n)^2-1 = n(n+1)(n+2)(n+3). */
+		  /* PTR (r) [0] ^= 1; would suffice, but it is not even needed, */
+		  /* because the next division will shift away this bit anyway.  */
+		  /* mpz_divexact_ui (r, r, 24); /\* 24=3<<3; div_by3 ? *\/ */
+		}
+	      mpn_pi1_bdiv_q_1 (PTR(r), PTR(r), SIZ(r), 3, GMP_NUMB_MASK/3*2+1, 1 | (k>>1));
+	      SIZ(r) -= PTR(r) [SIZ(r) - 1] == 0;
 	    }
-	  else /* k = 4 */
-	    {
-	      mpz_add (ni, ni, r); /* (n+1)^2+n */
-	      mpz_mul (r, ni, ni); /* ((n+1)^2+n)^2 */
-	      mpz_sub_ui (r, r, 1); /* ((n+1)^2+n)^2-1 = n(n+1)(n+2)(n+3) */
-	      /* mpz_divexact_ui (r, r, 24); /\* 24=3<<3; div_by3 ? *\/ */
-	      mpn_pi1_bdiv_q_1 (PTR(r), PTR(r), SIZ(r), 3, GMP_NUMB_MASK/3*2+1, 3);
-	      MPN_NORMALIZE_NOT_ZERO (PTR(r), SIZ(r));
-	    }
+#endif
 	}
 #endif
       else