Dividing 2 limbs by one limb saving 30% of time ?

Andy borucki.andrzej at gmail.com
Tue Nov 12 19:56:52 UTC 2019


void mpn_tdiv_qr (mp_ptr qp, mp_ptr rp, mp_size_t qxn,
    mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn)
................................
case 1:
      {
if (nn == 1)
{
mp_limb_t n = *np;
mp_limb_t d = *dp;
qp[0] = n / d;
rp[0] = n % d;
}
else if (nn == 2 && np[1] < *dp)
{
udiv_qrnnd(qp, rp, np[1], np[0], *dp);
}
else
rp[0] = mpn_divrem_1 (qp, (mp_size_t) 0, np, nn, dp[0]);

Test ( np[1] < *dp ) (but not <=) is necessary and sufficient to fit result
in one limb and not throw integer exception.
The whole 50% of the random cases satisfy this test.
Condition saved time 1.3 x

Will udiv_qrnnd give the right result in this case, or is it not possible
to do right?


More information about the gmp-devel mailing list