[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#10519: guile and (mini-)gmp
From: |
Mark H Weaver |
Subject: |
bug#10519: guile and (mini-)gmp |
Date: |
Wed, 27 Mar 2013 13:00:03 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) |
Hi Niels,
address@hidden (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
bug#10519: guile and (mini-)gmp, Niels Möller, 2013/03/02