Schönhage's algorithm for fast integer GCD

[Kevin Ryde]

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.