I have not had time or energy to post here for a month now but I HAD to share something quite amusing, borderline useful but curious enough that I wonder if somebody had already come up with this sort of HAKMEM.

So far, you should already know that you can compute a number modulo a power of two by masking the MSB off.

For example if you want to perform mod 128,

A = B & 127;

This is because 128=2^7 and the mask is the modulo minus one.

This is why we computer people LOVE powers of two : it's quick and painless.

BUT this is not always the case and the generalised PEAC algo made me scratch my head a bit, until I found something amusing.

The typical method for modulo operation is the modulo operator (%) but it's is known to be "expensive".

There is also the method that performs a division by multiplying by the reciprocal, but then you have to perform adjustments, and then a sbutraction.

If you *know* that the original value is less than 2× the modulus, then you can compare, conditional jump and subtract.

if (A >= mod)
   A -= mod;

This is the preferred version these days, with the OOO cores, but there are several alternatives, for example if you explicitly precompute the adjusted value. This is where it gets funky.

For example, you can precompute B:

B = A - mod;
if (A >= mod)
   A = B;

But then you think, oh well, if I compare A with mod, it's equivalent to a subtraction, which I have already performed on the previous line, so why the redundancy ? But then the language gets in the way.

B = A - mod;
if (B >= 0)
   A = B;

That's usually another comparison with 0... Which should be avoided since the previous subtraction might provide a few flags about the result. So the if-then is simply a conditional move, CMOV, as can be found on x86 or ARM.

But not all CPUs have CMOV. And then you realise that B can have crazy values, depending on the type: signed or unsigned ?

When A < mod, then B=A-mod < 0 and when using 2s complement with unsigned format, the value jumps through the roof. So the following line should work:

B = A - mod;
A = umin(A,B)

• if B becomes negative, then its unsigned value goes above A, which is chosen.
• If B is positive, thus a lower value than A (because it is A-mod) then B is chosen.

Voilà ! You have your funky mod. But there is a little catch: it doesn't work for the gPEAC because the assigned value is off-by-one.

Sigh