Schönhage's algorithm for fast integer GCD
Sat, 05 Jul 2003 10:53:50 +1000
firstname.lastname@example.org (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
then you're probably better off doing
if (limb & GMP_NUMB_HIGHBIT)
since count_leading_zeros is often slow.