bdiv vs redc

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I see a final sub_n which looks like it could be adjusted to make the
> remainder end up in the low end.

You're right, I missed that because it's conditional. But the other
branch from that condition is extremely unlikely (essentially, I think
it happens only when all qn low limbs were already zero in the input).

> A comment says:
>   /* FIXME: Add ASSERTs for allowable overlapping; i.e., that qp = np is OK,
>      but some over N/Q overlaps will not work.  */
> I think we changed this during last year.  Putting the quotient in that
> place is a workaround for callers in the absence lf an _r function variant.
>
> Are we talking about different functions?

I'm looking at mpn_sbpi1_bdiv_qr. I suspect that comment doesn't take
the current implementation into account. The typical loop (for the case
qn <= dn) uses these stores:

      np[i] = mpn_addmul_1 (np + i, dp, dn, q);
      qp[i] = ~q;

If q were to be stored at the low end of the n input, np == qp, those
two stores collide.

> But I have no informed opinion about where it would be best to put the
> remainder.

For redc, traditiona mandates the low end. But maybe callers could
accept the high end without additional overhead? That needs some
investigation; if that can work out it will simplify things.

High end seems more "natural" for this operation, and for the calls from
within dc_bdiv and mu_bdiv, I would be surprised if using anything but
the high end doesn't cause trouble. Using the low end as alien in the
same way as having euclidean division place the remainder at the high
end.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.