Small toom43 cleanup
tg at gmplib.org
Tue Oct 20 23:00:28 CEST 2009
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> mp_size_t is a signed type, for various reasons. size_t is an unsigned
> type. Unsigned division by constants is a few cycles faster.
How are these divisions by constants implemented? I guess it depends
on the compiler, but this is precisely the type of application your
and Montgomery's paper is about, right? IIRC, it should be a multiply,
possibly some shifting, and unlike udiv_qrnn_preinv, one may even get
away without any adjustment steps.
This is in the paper of Montgomery and me, it is indeed its main theme.
It is typically a multiply and a right shift. There are no adjustment
steps, but for certain divisors an extra bit of precision is needed. In
rare cases, the post-shift equals the word size and then no actual shift
is needed, just a multiply. (This happens for 641 for 32-bit divide and
274177 for 64-bit divide.)
Signed division needs a few more instructions; we basically do an
unsigned division and then put back the sign.
More information about the gmp-devel