# Schönhage's algorithm for fast integer GCD

**Niels Möller
**
nisse@lysator.liu.se

*05 Jul 2003 21:54:32 +0200*

Kevin Ryde <user42@zip.com.au> 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 important thing for the lehmer step is to compute the one-limb
quotient of two two-limb numbers a and b, q = floor(a/b), a >= b.
What's the fastest way of doing that? I know I could do some special
casing for small quotients by subtracting a few times before trying a
proper division, but I don't know of any obvious way to speed up the
general case.
>* mpn_neg can probably use mpn_com_n.
*
I looked for a function like that, but I couldn't fint it in the
manual. Anyway, the current code doesn't need that function anymore.
>* 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);
*>* ...
*
Do you mean
if (! (limb & GMP_NUMB_HIGHBIT))
{
count_leading_zeros(shift, limb);
...
?
Thanks for the hints,
/Niels