gcd_11 (was: Re: mpn_perfpow: do we need a special GCD for mp_bitcnt_t?)
Niels Möller
nisse at lysator.liu.se
Fri Sep 5 19:55:19 UTC 2014
tg at gmplib.org (Torbjörn Granlund) writes:
> I don't think gcd(0,0) is possible to define.
At least Knuth claims "it is convenient to set gcd(0,0) = 0", TAoCP,
4.5.2. Then gcd(u, 0) = |u| for *all* integers u. Also PARI/GP seems to
follow Knuth here. Which doesn't necessarily make that definition
appropriate in the mpn interface, of course.
> We should in the usual low-level spirit only define gcd(a,0), a > 0 if
> it doesn't cost the same as a test in the caller.
If the gcd_11 function starts with
t = u | v;
if (t == 0)
return 0;
count_trailing_zeros (common_zeros, t);
it will be *marginally* cheaper checking for zero here than doing it in
the caller, because we need u | v anyway.
But maybe it is better to require both operands non-zero, so one can
start with
count_trailing_zeros (u_zeros, u);
count_trailing_zeros (v_zeros, v);
u >>= u_zeros;
v >>= v_zeros;
common_zeros = MIN(u_zeros, v_zeros);
Then I see no advantage of adding any zero tests here rather than in the
caller.
Hmm. I think it's best to require non-zero inputs for the time being; we
can extend the range of valid inputs later if it turns out it is cheap
enough.
> It is still very much useful, although the name is odd. The cost of
> computing the bdiv inverse is much lower than computing the inverses
> needed for mod_1_*. The cutoff points are here:
> https://gmplib.org/devel/thres/BMOD_1_TO_MOD_1_THRESHOLD.html
I see. Threshold typically in the range 15-25 limbs.
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