Subject: bug#10519: guile and (mini-)gmp

From: Mark H Weaver <[email-masked]>
Date: Wed, 27 Mar 2013 13:00:03 -0400

Hi Niels,

[email-masked] (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