gcd_11 (was: Re: mpn_perfpow: do we need a special GCD for mp_bitcnt_t?)

[Niels Möller]

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.