divexact_1 and bdiv_q_1

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> I spent some time trying to understand the difference between the two
> functions: mpn_divexact_1 and mpn_bdiv_q_1 .
> As far as I can see they should compute the same mpn, but the first one
> does not return anything, while the second one returns an mp_limb_t. What
> is that returned value supposed to be?

If I remember correctly, it should work like this. Inputs are U (n
limbs) and d (single limb, and odd!). Then we should get back Q (n
limbs), defined by Q = U d^{-1} (mod B^n) and and r (single limb) such that

  U = Q * d - B^n r

It seems we'll usually (always?) get 0 <= r < d.

(This is a bit different from the interface of general bdiv, where an
n/1 division would produce a quotient of n-1 limbs and a remainder
corresponding to U = Q * d + B^{n-1} r, where r may be positive or
negative. I think this interface inconsistency has been discussed on the
list).

So it seems that at least r == 0 if and only if d divides U, which makes
the return value useful for divisibility tests. Or if you have some
application where you want to know if d divides U exactly, and care
about the actual quotient only in the case that d does divide U exactly.

And if you *only* want the divisibility test, then one could use a
separate function which omits storing of q.

Regards,
/Niels

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