Proposed patch for mpn_trialdiv

[Marco Bodrato]

Ciao,

the current code in mpn/generic/trialdiv.c contain a comment that 
suggest to remove "one of the outer loop conditions".

The patch I attach removes it by checking only the number of primes, and 
limiting the maximum for the latter.

I also added a possible optimisation for a single limb.

A call to mpn_trialdiv should be used also in mpz/pprime_p.c , instead 
of the "Do more dividing." loop.

The original code was by Torbjorn. Any comment?

*** ../gmp-head/mpn/generic/trialdiv.c	2018-05-08 06:15:55.711524824 
+0200
--- mpn/generic/trialdiv.c	2020-04-03 23:46:03.500943337 +0200
***************
*** 76,84 ****
   #include "trialdivtab.h"
   #undef WANT_dtab
   #undef P
-   {0,0}
   };

   static const struct gmp_primes_ptab gmp_primes_ptab[] =
   {
   #define WANT_ptab
--- 76,85 ----
   #include "trialdivtab.h"
   #undef WANT_dtab
   #undef P
   };

+ #define DTAB_LINES (numberof (gmp_primes_dtab))
+
   static const struct gmp_primes_ptab gmp_primes_ptab[] =
   {
   #define WANT_ptab
***************
*** 88,95 ****

   #define PTAB_LINES (sizeof (gmp_primes_ptab) / sizeof 
(gmp_primes_ptab[0]))

- /* FIXME: We could optimize out one of the outer loop conditions if we
-    had a final ptab entry with a huge np field.  */
   mp_limb_t
   mpn_trialdiv (mp_srcptr tp, mp_size_t tn, mp_size_t nprimes, int 
*where)
   {
--- 89,94 ----
***************
*** 101,108 ****

     ASSERT (tn >= 1);

!   for (i = *where; i < PTAB_LINES; i++)
       {
         ppp = gmp_primes_ptab[i].ppp;
         cps = gmp_primes_ptab[i].cps;

--- 100,136 ----

     ASSERT (tn >= 1);

!   ASSERT (DTAB_LINES == gmp_primes_ptab[PTAB_LINES - 1].np +
! 			gmp_primes_ptab[PTAB_LINES - 1].idx);
!   nprimes = MIN (nprimes, DTAB_LINES);
!
! #if 0
!   if (tn == 1)
!     {
!       dp = gmp_primes_dtab;
!       r = *tp;
!       /* In this branch the value *where is interpreted differently.
! 	 If tn decreases to 1, some primes will be checked again.
! 	 The opposite (tn increases) should not happen.
!
! 	 THINK: Should we avoid this? Maybe using positive and
! 	 negative values for the two differen uses? So that we can
! 	 detect when we switch from one another.
!       */
!       for (i = *where; i < nprimes; ++i)
! 	if (r * dp[i].binv <= dp[i].lim)
! 	  {
! 	    *where = i + 1;
! 	    return dp[i].binv;
! 	  }
!       return 0;
!     }
! #endif
!
!   nprimes -= gmp_primes_ptab[*where].idx;
!   for (i = *where; nprimes > 0; ++i)
       {
+       ASSERT (i < PTAB_LINES);
         ppp = gmp_primes_ptab[i].ppp;
         cps = gmp_primes_ptab[i].cps;

***************
*** 113,118 ****
--- 141,147 ----

         /* Check divisibility by individual primes.  */
         dp = &gmp_primes_dtab[idx] + np;
+       ASSERT (idx + np <= DTAB_LINES);
         for (j = -np; j < 0; j++)
   	{
   	  q = r * dp[j].binv;
***************
*** 124,131 ****
   	}

         nprimes -= np;
-       if (nprimes <= 0)
- 	return 0;
       }
     return 0;
   }
--- 153,158 ----


Ĝis,
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: trialdiv.diff
Type: text/x-diff
Size: 2047 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200404/f72a4200/attachment.bin>