divexact_1 and bdiv_q_1

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Both divexact_1 and bdiv_q_1 accept an even divisor. They remove any even
> factor, then implement (or call) a pi1_bdiv_q_1 routine.

What happens if divisor is even but dividend is odd? I guess divexact_1 is not
expected to return anything sensible in that case, but what does
bdiv_q_1 do? Shift out and ignore low bits of the dividend? And focusing
on the return value, does it make any sense in this case?

> Well... bdiv_q does not return any reminder, and I do not expect any
> returned by bdiv_q_1.

A was about to write than a bdiv_q_1 with a return value should maybe
be renamed bdiv_qr_1...

> I mean, if size (n) is one, the returned value is always zero, regardless
> of divisibility.

Then there are two cases where the return value is a bit fishy: even d,
and n == 1. Unless we can come up with a reasonable and useful
definition of what the return value should be for all valid inputs, it
would make sense to me to eliminate the return value.

> The returned value is the most significant limb of the result, right?

Hmm, if that's how it works, that's completely different from what I
remembered. That convention makes some sense to me. Except that I'd
prefer that the most significant quotient limb is not stored in memory,
letting the caller do

  qp[n-1] = mpn_bdiv_q_1(...)

if desired.

Returning the high quotient limb (a single bit if divisor is normalized)
is a common convention for the new div functions. However, most bdiv
functions instead return the remainder sign (or rather, the borrow from
the subtraction U - Q*D). So it would be slightly surprising if bdiv_q_1
adopts the div convention (even though it makes perfect sense for
divexact).

Regards,
/Niels

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