gcd_22

[Marco Bodrato]

Ciao,

Il 2019-08-27 16:35 tg at gmplib.org ha scritto:
> I got something working.  It runs quite well, and seems to beat the

Great!

> static inline void
> mpn_gcd_NN (mp_limb_t *rp, mp_limb_t *up, mp_limb_t *vp, size_t N)

I see that your idea is to obtain a N-loop-unrolled version...

>       if (UNLIKELY (cy))
> 	mpn_neg (up, up, N);

This is an unlikely branch, but I'd really suggest
  {mpn_neg (up, up, N -1); up[N-1] = 0;}
because mpn_neg is full of branches :-)

>       if (UNLIKELY (up[0] == 0))
> 	{

This unlikely branch may end up with an odd up[0]...

> 	}
>       int cnt;
>       count_trailing_zeros (cnt, up[0]);
>       mpn_rshift (up, up, N, cnt);

... and on some platform mpn_rshift may not support cnt==0.

Maybe (for the C version) we should duplicate the ctz/shift instruction, 
both inside the UNLIKELY (*up == 0) branch (deciding whether to shift or 
copy) and in an else (likely) branch.

m

-- 
http://bodrato.it/papers/