Would someone mind elaborating the explanation in the manual?

Kevin Ryde user42 at zip.com.au
Wed Oct 29 06:37:59 CET 2003

Brian Hurt <bhurt at spnz.org> writes:
> In 32-bit.  In 64-bit, if n = 3, then n * 0xAAAAAAAB becomes 0x200000001, 
> and the test fails.

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

> 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).  :)

More information about the gmp-discuss mailing list