Basecases of mulmod_bnm1.c and sqrmod_bnm1.c

[Torbjorn Granlund]

Why do we call mpn_mul, mpn_mul_n, and mpn_sqr in the bnm1 functions'
basecases?

I'd say we should call mpn_mul_basecase and mpn_sqr_basecase instead,
for a few cycles less overhead.

It seems MUL_TOOM22_THRESHOLD > MULMOD_BNM1_THRESHOLD and
SQR_TOOM2_THRESHOLD > SQRMOD_BNM1_THRESHOLD for all machines.

Possible patch:

diff -Nrc2 gmp-main.ede4cbbb7737/mpn/generic/mulmod_bnm1.c 
gmp-main/mpn/generic/mulmod_bnm1.c
*** gmp-main.ede4cbbb7737/mpn/generic/mulmod_bnm1.c     Thu Aug 29 18:03:29 2013
--- gmp-main/mpn/generic/mulmod_bnm1.c  Thu Aug 29 18:03:29 2013
***************
*** 42,46 ****
    ASSERT (0 < rn);
  
!   mpn_mul_n (tp, ap, bp, rn);
    cy = mpn_add_n (rp, tp, tp + rn, rn);
    /* If cy == 1, then the value of rp is at most B^rn - 2, so there can
--- 42,46 ----
    ASSERT (0 < rn);
  
!   mpn_mul_basecase (tp, ap, rn, bp, rn);
    cy = mpn_add_n (rp, tp, tp + rn, rn);
    /* If cy == 1, then the value of rp is at most B^rn - 2, so there can
***************
*** 62,66 ****
    ASSERT (0 < rn);
  
!   mpn_mul_n (tp, ap, bp, rn + 1);
    ASSERT (tp[2*rn+1] == 0);
    ASSERT (tp[2*rn] < GMP_NUMB_MAX);
--- 62,66 ----
    ASSERT (0 < rn);
  
!   mpn_mul_basecase (tp, ap, rn + 1, bp, rn + 1);
    ASSERT (tp[2*rn+1] == 0);
    ASSERT (tp[2*rn] < GMP_NUMB_MAX);
***************
*** 100,109 ****
          if (UNLIKELY (an + bn <= rn))
            {
!             mpn_mul (rp, ap, an, bp, bn);
            }
          else
            {
              mp_limb_t cy;
!             mpn_mul (tp, ap, an, bp, bn);
              cy = mpn_add (rp, tp, rn, tp + rn, an + bn - rn);
              MPN_INCR_U (rp, rn, cy);
--- 100,109 ----
          if (UNLIKELY (an + bn <= rn))
            {
!             mpn_mul_basecase (rp, ap, an, bp, bn);
            }
          else
            {
              mp_limb_t cy;
!             mpn_mul_basecase (tp, ap, an, bp, bn);
              cy = mpn_add (rp, tp, rn, tp + rn, an + bn - rn);
              MPN_INCR_U (rp, rn, cy);
diff -Nrc2 gmp-main.ede4cbbb7737/mpn/generic/sqrmod_bnm1.c 
gmp-main/mpn/generic/sqrmod_bnm1.c
*** gmp-main.ede4cbbb7737/mpn/generic/sqrmod_bnm1.c     Thu Aug 29 18:03:29 2013
--- gmp-main/mpn/generic/sqrmod_bnm1.c  Thu Aug 29 18:03:29 2013
***************
*** 41,45 ****
    ASSERT (0 < rn);
  
!   mpn_sqr (tp, ap, rn);
    cy = mpn_add_n (rp, tp, tp + rn, rn);
    /* If cy == 1, then the value of rp is at most B^rn - 2, so there can
--- 41,45 ----
    ASSERT (0 < rn);
  
!   mpn_sqr_basecase (tp, ap, rn);
    cy = mpn_add_n (rp, tp, tp + rn, rn);
    /* If cy == 1, then the value of rp is at most B^rn - 2, so there can
***************
*** 60,64 ****
    ASSERT (0 < rn);
  
!   mpn_sqr (tp, ap, rn + 1);
    ASSERT (tp[2*rn+1] == 0);
    ASSERT (tp[2*rn] < GMP_NUMB_MAX);
--- 60,64 ----
    ASSERT (0 < rn);
  
!   mpn_sqr_basecase (tp, ap, rn + 1);
    ASSERT (tp[2*rn+1] == 0);
    ASSERT (tp[2*rn] < GMP_NUMB_MAX);
***************
*** 95,104 ****
          if (UNLIKELY (2*an <= rn))
            {
!             mpn_sqr (rp, ap, an);
            }
          else
            {
              mp_limb_t cy;
!             mpn_sqr (tp, ap, an);
              cy = mpn_add (rp, tp, rn, tp + rn, 2*an - rn);
              MPN_INCR_U (rp, rn, cy);
--- 95,104 ----
          if (UNLIKELY (2*an <= rn))
            {
!             mpn_sqr_basecase (rp, ap, an);
            }
          else
            {
              mp_limb_t cy;
!             mpn_sqr_basecase (tp, ap, an);
              cy = mpn_add (rp, tp, rn, tp + rn, 2*an - rn);
              MPN_INCR_U (rp, rn, cy);

-- 
Torbjörn
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel