t...@gmplib.org (Torbjörn Granlund) writes:
> I switched focus to a general mpn_gcd_basecase, using the table-based
> approach Niels and me discussed a week ot two ago here.
>
> I decided to still keep away from data-dependent branches, which may not
> be the best solution as the operands grow.
>
> Ignoring unlikely cases, we have this loop:
>
> while (n > 2)
> {
> CMP_SWAP (up, vp, n);
>
> a = up[0];
> b = vp[0];
> m = tab[((a & mask) << (4 - 1)) + ((b & mask) >> 1)];
If we allow data dependent branches, would it be unreasonable to go all
the way and make the table a jump table, something like
switch (((a & mask) << (4 - 1)) + ((b & mask) >> 1)) { ...}
?
If we can afford a fair amount of different cases, I find the variant
choosing between alternatives a±b, a±3b, (a, b) <-- (3 a - 5b, 3a +
5b) etc neat. Shifting at least 4 bits per iteration.
It's tempting to use two's complement to deal with negative values.
I see two complications:
1. We need an efficient way to find out which of |u| and |v| is
smallest, for CMP_SWAP. But we can likely get away with something a
bit sloppy, and accept arbitrary results in the case that u and v are
"close", e.g., same bit size.
2. For the variant without branches, we'd need an mpn_addmul_1s working
with two's complement. It could be implemented as mpn_addmul_1 +
mpn_cnd_sub, but not sure if there's some easy way to implement with
a single pass, somehow sign extending on the fly.
> cy = mpn_addmul_1 (up, vp, n, m);
> a = up[0];
> count_trailing_zeros (cnt, a);
One could move the count_trailing_zeros before mpn_addmul_1 by
duplicating the mul, a = up[0] + m * vp[0]. Would make more sense if we
also have an addmul + shift loop.
> mpn_rshift (up, up, n, cnt);
> up[n - 1] |= cy << (GMP_LIMB_BITS - cnt);
>
> if (mpn_cmp (up, vp, n) == 0)
> we're done
The large gcd exit case belongs inside the if (UNLIKELY (a == 0)) branch
needed for count_trailing_zeros.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
