Would someone mind elaborating the explanation in the manual?

Brian Hurt bhurt at spnz.org
Tue Oct 28 17:05:22 CET 2003

On Wed, 29 Oct 2003, Kevin Ryde wrote:

> You can write an expression like "(~0 / 3) * 2 + 1", per
> MODLIMB_INVERSE_3 in gmp-impl.h.  Not sure if all divisors are
> amenable to such an expression, 3 is slightly special in that
> 2^32%3==1.

Point.  I'd have to think about it to see if it was applicable to other 

> > I'm not sure it's true that a divide is slower than 
> > 2 multiplies, a shift, and a subtract (which is what I was comparing it 
> > to).
> Every decent chip I know of.  Only old stuff like 80386 would be
> exceptions (mul and div both 40 cycles there I think).  :)

The 386 had early-out multiplication depending upon the high bit of the
multiplicand.  The imul instruction could be as fast as 12 cycles, or as
slow as 41 (not counting memory accesses).  The idiv instruction was 
always 43 clocks.

And it's sad that I didn't even have to leave my chair to look that info 


More information about the gmp-discuss mailing list