mpn/generic/mu_bdiv_q.c

2    storing the result in {qp,nn}.  Overlap allowed between Q and N; all other
28 or both in parallel, as here.
30 The GNU MP Library is distributed in the hope that it will be useful, but
42    than used in the standard Barrett algorithm, and thus save time in the
65 	  particular, when dn==in, tp and rp could use the same space.
75   mp_size_t in;
91 #define ip           scratch			/* in */
92 #define rp           (scratch + in)		/* dn or rest >= binvert_itch(in) */
93 #define tp           (scratch + in + dn)	/* dn+in or next_size(dn) */
94 #define scratch_out  (scratch + in + dn + tn)	/* mulmod_bnm1_itch(next_size(dn)) */
98       in = (qn - 1) / b + 1;	/* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
102 	 When in = dn, R dies when mpn_mullo returns, if in < dn the low in
108       mpn_binvert (ip, dp, in, rp);
114       mpn_mullo_n (qp, rp, ip, in);
115       qn -= in;
117       while (qn > in)
119 	  if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
120 	    mpn_mul (tp, dp, dn, qp, in);	/* mulhi, need tp[dn+in-1...in] */
124 	      mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
125 	      wn = dn + in - tn;		/* number of wrapped limbs */
133 	  qp += in;
134 	  if (dn != in)
136 	      /* Subtract tp[dn-1...in] from partial remainder.  */
137 	      cy += mpn_sub_n (rp, rp + in, tp + in, dn - in);
144 	  /* Subtract tp[dn+in-1...dn] from dividend.  */
145 	  cy = mpn_sub_nc (rp + dn - in, np, tp + dn, in, cy);
146 	  np += in;
147 	  mpn_mullo_n (qp, rp, ip, in);
148 	  qn -= in;
155       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
156 	mpn_mul (tp, dp, dn, qp, in);		/* mulhi, need tp[qn+in-1...in] */
160 	  mpn_mulmod_bnm1 (tp, tn, dp, dn, qp, in, scratch_out);
161 	  wn = dn + in - tn;			/* number of wrapped limbs */
169       qp += in;
170       if (dn != in)
172 	  cy += mpn_sub_n (rp, rp + in, tp + in, dn - in);
180       mpn_sub_nc (rp + dn - in, np, tp + dn, qn - (dn - in), cy);
193 #define ip           scratch		/* in */
194 #define tp           (scratch + in)	/* qn+in or next_size(qn) or rest >= binvert_itch(in) */
195 #define scratch_out  (scratch + in + tn)/* mulmod_bnm1_itch(next_size(qn)) */
198       in = qn - (qn >> 1);
200       mpn_binvert (ip, dp, in, tp);
202       mpn_mullo_n (qp, np, ip, in);		/* low `in' quotient limbs */
204       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
205 	mpn_mul (tp, dp, qn, qp, in);		/* mulhigh */
209 	  mpn_mulmod_bnm1 (tp, tn, dp, qn, qp, in, scratch_out);
210 	  wn = qn + in - tn;			/* number of wrapped limbs */
218       mpn_sub_n (tp, np + in, tp + in, qn - in);
219       mpn_mullo_n (qp + in, tp, ip, qn - in);	/* high qn-in quotient limbs */
240   mp_size_t qn, in, tn, itch_binvert, itch_out, itches;
250       in = (qn - 1) / b + 1;	/* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
251       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
253 	  tn = dn + in;
259 	  itch_out = mpn_mulmod_bnm1_itch (tn, dn, in);
265       in = qn - (qn >> 1);
266       if (BELOW_THRESHOLD (in, MUL_TO_MULMOD_BNM1_FOR_2NXN_THRESHOLD))
268 	  tn = qn + in;
274 	  itch_out = mpn_mulmod_bnm1_itch (tn, qn, in);
279   itch_binvert = mpn_binvert_itch (in);
280   return in + MAX (itches, itch_binvert);