Lines Matching refs:qn
11 The time complexity of this is O(qn*qn+M(dn,qn)), where M(m,n) is the time
172 limbs forming a quotient of qn=nn-dn+1 limbs. When qn is small
175 dependent only on qn.
179 1) Divide the 2 x qn most significant limbs from the numerator
180 by the qn most significant limbs from the denominator. Call
201 mp_size_t qn;
209 qn = nn - dn;
210 qp[qn] = 0; /* zero high quotient limb */
211 qn += adjust; /* qn cannot become bigger */
213 if (qn == 0)
220 in = dn - qn; /* (at least partially) ignored # of limbs in ops */
229 d2p = TMP_ALLOC_LIMBS (qn);
230 mpn_lshift (d2p, dp + in, qn, cnt);
233 n2p = TMP_ALLOC_LIMBS (2 * qn + 1);
234 cy = mpn_lshift (n2p, np + nn - 2 * qn, 2 * qn, cnt);
237 n2p[2 * qn] = cy;
242 n2p[0] |= np[nn - 2 * qn - 1] >> (GMP_NUMB_BITS - cnt);
250 n2p = TMP_ALLOC_LIMBS (2 * qn + 1);
251 MPN_COPY (n2p, np + nn - 2 * qn, 2 * qn);
254 n2p[2 * qn] = 0;
260 if (qn == 1)
267 else if (qn == 2)
271 invert_pi1 (dinv, d2p[qn - 1], d2p[qn - 2]);
272 if (BELOW_THRESHOLD (qn, DC_DIV_QR_THRESHOLD))
273 mpn_sbpi1_div_qr (qp, n2p, 2 * qn, d2p, qn, dinv.inv32);
274 else if (BELOW_THRESHOLD (qn, MU_DIV_QR_THRESHOLD))
275 mpn_dcpi1_div_qr (qp, n2p, 2 * qn, d2p, qn, &dinv);
278 mp_size_t itch = mpn_mu_div_qr_itch (2 * qn, qn, 0);
282 r2p += nn - qn; /* intermediate remainder at N's upper end. */
283 mpn_mu_div_qr (qp, r2p, n2p, 2 * qn, d2p, qn, scratch);
284 MPN_COPY (n2p, r2p, qn);
288 rn = qn;
310 umul_ppmm (h, dummy, x, qp[qn - 1] << GMP_NAIL_BITS);
312 if (n2p[qn - 1] < h)
317 cy = mpn_add_n (n2p, n2p, d2p, qn);
321 n2p[qn] = cy;
337 cy2 = mpn_submul_1 (n2p, qp, qn, dp[in - 1] & (GMP_NUMB_MASK >> cnt));
338 if (qn != rn)
340 ASSERT_ALWAYS (n2p[qn] >= cy2);
341 n2p[qn] -= cy2;
345 n2p[qn] = cy1 - cy2; /* & GMP_NUMB_MASK; */
356 if (in < qn)
364 mpn_mul (tp, qp, qn, dp, in);
367 mpn_mul (tp, dp, in, qp, qn);
369 cy = mpn_sub (n2p, n2p, rn, tp + in, qn);
Indexes created Fri Aug 21 00:24:51 UTC 2026