Small toom43 cleanup

Torbjorn Granlund tg at
Tue Oct 20 23:00:28 CEST 2009

nisse at (Niels Möller) writes:

  Torbjorn Granlund <tg at> 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 mailing list