# Schönhage's algorithm for fast integer GCD

**Kevin Ryde
**
user42@zip.com.au

*Sat, 05 Jul 2003 10:53:50 +1000*

nisse@lysator.liu.se (Niels Möller) writes:
>*
*>* Here, hgcd_2 is the work horse for Lehmer steps,
*
Is q=ah/bh the primary quotient step? Bear in mind that "/" is pretty
woeful on a lot of chips.
The quotient is usually small (per Knuth), so going bitwise is usually
more efficient. It's been on the tasks list for quite a while to have
mpn_gcdext use the bitwise Lehmer outlined in Knuth (and elsewhere?).
>* http://www.lysator.liu.se/~nisse/misc/gcd-0.3.tar.gz
*
mpn_neg can probably use mpn_com_n.
The reason SHIFT_LEFT doesn't work on count==0 is the right shift by
BITS_PER_MP_LIMB won't give zero, on most cpus. In fact ia64 is the
only one I know of which does.
If you find yourself with
count_leading_zeros(shift, limb);
if (shift)
...
then you're probably better off doing
if (limb & GMP_NUMB_HIGHBIT)
{
count_leading_zeros(shift, limb);
...
since count_leading_zeros is often slow.