dead code in div_q.c?

[Niels Möller]

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.