gcd_22

[Marco Bodrato]

Ciao,

Il Lun, 26 Agosto 2019 4:36 pm, Torbjörn Granlund ha scritto:
>        for (;;) {
>          if (up[N-1] < vp[N-1])
> 	   swap up,vp
> 	back:
> 	 cy = mpn_sub_n (up, up, vp, N);
> 	 if (UNLIKELY (cy)) { swap up,vp; goto back }
> 	 if (UNLIKELY (up[0] == 0)) {
> 	   // handle any number zeros including that U = 0
> 	 }
> 	 count_trailing_zeros (cnt, up[0]);
> 	 mpn_rshift (up, up, N, cnt);
>        }

Some messages ago, Niels suggested that discarding the smallest number
keeping the largest one in some unlikely case could be a good idea.

I did not completely understand what he meant... But here I can see his
suggestion was quite clever.
I'd suggest
  if (UNLIKELY (cy)) { mpn_neg(up,up, N-1); up[N-1] = 0; }
without jumping back... :-)


Ĝis,
m

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