Would someone mind elaborating the explanation in the manual?

[Kevin Ryde]

Brian Hurt <bhurt at spnz.org> writes:
>
> IMHO, this is something the compiler should do- like rewritting /8 into 
>>>3.

I'm about to submit a wishlist bug for gcc to do it.  It already does
constant exact division (for pointer subtraction) the corresponding
way.  (This is all following the "Division by Invariant Integers"
paper in the GMP references.)

> But
> replacing a modulo requires a shift and a multiply (to do the divide) and
> then another multiply and a subtract (to get the remainder).

If you're only testing divisibility then for instance n%3==0 becomes

	(n * 0xAAAAAAAB) <= 0x55555555

which is one multiply.

In the next gmp the tests in mpn/generic/perfsqr.c will be written
that way.  (Explicitly, to take it out of the hands of the compiler.)
	
> Which isn't always faster than a divide instruction.

True, that should be checked, but almost everywhere one multiply is
faster than a divide.