[PATCH] expansion: Improve double-word modulo by certain constant divisors [PR97459]

Thomas Koenig tkoenig@netcologne.de
Sat Nov 28 14:55:54 GMT 2020


Hello Jakub,

thanks a lot for taking this on!

As far as I can tell, the patch works very well, and really speeds up
things.

As (somewhat confusingly) discussed in the PR, there are a couple of
things that could still be done incrementally with this method.

Fist, it can be combined with, or even used for, the calulation
of the quotient.  Let a be a number for which your patch works,
for example 5.

If you want to calculate n / 5, you can do

   rem = n % 5;  /* Fast, with your patch.  */
   quot = (n - rem) * magic;

in a fast way, where magic is the multiplicative inverse of 5
modulo 2^128 (for a 128-bit number) or 2^64 (for a 64-bit number),
which can be calculated using gmp_invert. The multiplicative inverse
for division works because n - rem is divisible by 5.

Second, you can also use this for the quotient and/or remainder
by 2*a (for example 10), with a slight adjustment:

   rem5 = n % 5;
   quot5 = (n - rem5) * magic;
   rem10 = (quot5 % 2) * 5 + rem5;
   quot10 = quot5 / 2;

This would cover the important use case of getting the quotient and
remainder for division by 10.

However, a benchmark (source attached) indicates that this method
is much faster even when only one of quotient and remainder
of division by 10 is needed.  Numbers I got indicate that this
method is faster by about a factor of five than calling the
library version.

I hope this clears up the somewhat confusing string of comments
in the PR.

Best regards

	Thomas
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bench.c
Type: text/x-csrc
Size: 1145 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20201128/b8172cd5/attachment.bin>


More information about the Gcc-patches mailing list