Schönhage's algorithm for fast integer GCD

[Niels Möller]

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