div_qr_1 interface

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   The interesting thing is that the next higher function, mpn_div_qr_1,
>   should return the high quotient limb separately.
>
> I am not sure I agree.  Please explain.

A long time ago, we choose an interface for sbpi1_div_qr which does
*not* store the most significant limb; instead it returns it. I think it
was the intention that a new top-level mpn_div_qr should follow that
convention, and not store the top limb. I don't remember if that was
purely for esthetic reasons, or if it also simplified the divide&conquer
division code.

Having some of the special division case functions, like mpn_div_qr_1,
storing the top quotient limb leads to unnecessary complications when
writing the general mpn_div_qr; it forces mpn_div_qr for n/1 to do the
top limb itself and call mpn_div_qr_1 with (n-1)/1, which seems like a
case of bad impedance mismatch.

But then, requirements for div_qr_1 don't necessarily translate to
requirements for the primitive division loops we're discussing now.

For the recent mpn_div_qr_1 and mpn_div_qr_1n_pi1, it turned out to work
fine to have mpn_div_qr_1 for n/1 do the top quotient limb up front, and
let mpn_div_qr_1n_pi1 generate n-1 quotient limbs (but n-1 *full* limbs,
since we pass in a high u limb, reduced to uh < d).

It's unclear to me if the best design for the unnormalized case is to
follow mpn_div_qr_1n_pi1 or not. It get be clearer after writing a
decent mpn_div_qr_1u_pi1.

Regards,
/Niels




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