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