divexact_1 and bdiv_q_1
Niels Möller
nisse at lysator.liu.se
Wed Jan 19 19:34:14 CET 2011
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.
More information about the gmp-devel
mailing list