Hi Niels,
ni...@lysator.liu.se (Niels Möller) writes:
> For the small integer gcd code, you may want to have a look at the
> tricks used in
> http://gmplib.org:8000/gmp/file/304af17b9ccc/mpn/generic/gcd_1.c, the
> code under GCD_1_METHOD == 2
>
> 1. Shift out the least significant bit of both a and b (they're always
> one). Maybe you don't need this of you have some extra bits already
> (signed types, or some bits reserved for type info).
>
> 2. Then, the sign bit of a - b correctly gives the result of the
> comparison a < b. Constructing a mask from this difference is then a
> simple right shift (if >> on a signed int is not an arithmetic right
> shift, you need shift and a negation).
>
> 3. Use this bit mask when forming the absolute value |a - b|, and when
> swapping values around, to avoid unpredictable branches which
> typically are quite expensive.
Excellent tricks! Thanks for sharing. I'll try to find the time to
apply these ideas soon, but probably not before 2.0.8 -- there are too
many more important things to do for that, and not enough time.
Regards,
Mark
