Would someone mind elaborating the explanation in the manual?
user42 at zip.com.au
Mon Oct 27 08:30:44 CET 2003
Brian Hurt <bhurt at spnz.org> writes:
> IMHO, this is something the compiler should do- like rewritting /8 into
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.)
> 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.
More information about the gmp-discuss