dead code in div_q.c?
Niels Möller
nisse at lysator.liu.se
Fri Apr 20 19:48:29 UTC 2018
paul zimmermann <Paul.Zimmermann at inria.fr> writes:
> together with Raphaël Rieu-Hleft (in cc), we believe we have found some dead code in
> mpn/generic/div_q.c around lines 173-182:
>
> else if (UNLIKELY (qh != 0))
> {
> /* This happens only when the quotient is close to B^n and
> mpn_*_divappr_q returned B^n. */
I think your right. This comment is wrong in two ways: First, divappr is
not called (directly) for this branch of code, and second, the quotient
can be at most close to B^n/2.
Maybe we can also make the above store
if (cy == 0)
tp[qn] = qh;
unconditional (tp has space for qn+1 limbs, and a store might be cheaper
than a branch).
tp[qn] = qh;
ASSERT (cy == 0 || qh == 0); /* Or ASSERT ((cy & -qh) == 0); */
There's similar logic around lines 265-274. There divappr *is* called
directly, but I think the other part of the argument still applies: When
D is unnormalized, and the left shift of of N makes it grow one limb (cy
> 0), then the quotient can not be larger than appr B^n/2, and divappr
error can't make that even close to B^n. Hence, we must have qh == 0 in
that case too.
It's long time since we worked on this division code...
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list