GNU bug report logs - #10519
guile and (mini-)gmp

Previous Next

Full log

Message #80 received at 10519 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: nisse <at> lysator.liu.se (Niels Möller)
Cc: Andy Wingo <wingo <at> pobox.com>, 10519 <at> debbugs.gnu.org,
	Ludovic Courtès <ludo <at> gnu.org>,
	Torbjorn Granlund <tg <at> gmplib.org>
Subject: Re: bug#10519: guile and (mini-)gmp
Date: Wed, 27 Mar 2013 13:00:03 -0400

Hi Niels,

nisse <at> 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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.