Would someone mind elaborating the explanation in the manual?

Brian Hurt bhurt at spnz.org
Sun Oct 26 15:37:46 CET 2003


On Mon, 27 Oct 2003, Kevin Ryde wrote:

> Sisyphus <kalinabears at iinet.net.au> writes:
> >
> > the number of
> > small integers for which divisibility needs to be tested.
> 
> On some chips gcc "%" operator isn't very fast unfortunately.  (Alpha
> is a bit notorious in this respect.)  If it's a constant divisor you
> can re-write it as a mul-by-inverse though.

IMHO, this is something the compiler should do- like rewritting /8 into 
>>3.  This (converting modulo into multiply by the inverse) is tricky to 
do portably, and not always a win.  Generally, replacing division by a
shift and a multiply is a win on every architecture I know of.  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).  Which isn't
always faster than a divide instruction.  So wether you want to apply this
operation or not depends upon what architecture you are on.  Also, what
constant you need to multiply by changes with your wordsize.  So now how
you apply this optimization changes.  On the other hand, this optimization 
is easy for the compiler to implement.

Brian




More information about the gmp-discuss mailing list