mpn/generic/mu_divappr_q.c

3    Compute Q = floor(N / D) + e.  N is nn limbs, D is dn limbs and must be
4    normalized, and Q must be nn-dn limbs, 0 <= e <= 4.  The requirement that Q
5    is nn-dn limbs (and not nn-dn+1 limbs) was put in place in order to allow us
29 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
44     demonstrated by the fact that the mpn_invertappr function's scratch needs
45     mean that we need to keep a large allocation long after it is needed.
46     Things are worse as mpn_mul_fft does not accept any scratch parameter,
48     general, a peak scratch need in the beginning of a function isn't
66 		  mp_srcptr np,
67 		  mp_size_t nn,
78   qn = nn - dn;
83       np += dn - (qn + 1);
84       nn -= dn - (qn + 1);
95      results.  FIXMEs: (1) Temp allocation needs not analysed (2) itch function
96      not adapted (3) mpn_invertappr scratch needs not met.  */
143   qh = mpn_preinv_mu_divappr_q (qp, np, nn, dp, dn, ip, in, scratch + in);
150 			 mp_srcptr np,
151 			 mp_size_t nn,
167   qn = nn - dn;
169   np += qn;
172   qh = mpn_cmp (np, dp, dn) >= 0;
174     mpn_sub_n (rp, np, dp, dn);
176     MPN_COPY (rp, np, dn);
188       np -= in;
191       /* Compute the next block of quotient limbs by multiplying the inverse I
202 	 subtracted from the partial remainder combined with new limbs from the
203 	 dividend N.  We only really need the low dn limbs.  */
211 	  wn = dn + in - tn;			/* number of wrapped limbs */
224       /* Subtract the product from the partial remainder combined with new
225 	 limbs from the dividend N, generating a new partial remainder R.  */
228 	  cy = mpn_sub_n (tp, np, tp, in);	/* get next 'in' limbs from N */
234 	  cy = mpn_sub_n (rp, np, tp, in);	/* get next 'in' limbs from N */
240       /* Check the remainder R and adjust the quotient as needed.  */
269 		printf ("\n");
275      quotient.  For now, just make sure the returned quotient is >= the real
277   qn = nn - dn;
314 	  /* Compute an inverse size that is a nice partition of the quotient.  */
315 	  b = (qn - 1) / dn + 1;	/* ceil(qn/dn), number of blocks */
338 mpn_mu_divappr_q_itch (mp_size_t nn, mp_size_t dn, int mua_k)
342   qn = nn - dn;