Schönhage's algorithm for fast integer GCD

Kevin Ryde
Sat, 05 Jul 2003 10:53:50 +1000 (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?).


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.