Schönhage's algorithm for fast integer GCD
06 Jul 2003 11:50:49 +0200
firstname.lastname@example.org (Niels Möller) writes:
Kevin Ryde <email@example.com> 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
Perhaps the bitwise div2 function from mpn/generic/gcdext.c could
be used. That function accepts a two-limb divisor, but
simplifying it to just handle a one-limb divisor should be
Do you mean
if (! (limb & GMP_NUMB_HIGHBIT))
Please use "!= 0" for numerical data.