Bit-packed arithmetic over Z/nZ for tiny n

[fredrik-johansson]

Consider n < 256. We get 8x memory reduction using nmod8 instead of nmod, so it would be interesting to optimize the arithmetic in the nmod8 representation. Some low-hanging fruit here is to do batch modular reduction using SIMD operations.

For really small n we can do even better by bit packing. Obviously for n = 2 we want to use a single word to represent a chunk of 64 entries. Polynomial multiplication is easy on modern hardware since there are now dedicated CLMUL instructions

What about other tiny n?

We can store an entry of Z/3Z using 2 bits, so it's possible to pack 32 entries into a word. Packing as tightly as possible is not obviously optimal: using 3 or 4 bits or even 6 or 8 bits has the benefit that one can do some arithmetic in-place before reducing. When packing to 2 bits, the article https://doi.org/10.36045/bbms/1369316548 discusses a nonstandard encoding which makes the arithmetic operations easier to implement using bitwise operations. To figure out what works best, one probably needs some implementation experiments.

It should be possible to do some more small cases like n = 5 and 7 very similarly.

[fredrik-johansson]

Consider mod 5 arithmetic for example.

If 0 <= a <= 9 then a - 5 * (((a + 3) & 8) >> 3) does a % 5, so with 4-bit packing a 16-fold a + b can be implemented as (a + b) - 5 * ((((a + b) + 0x3333333333333333) & 0x8888888888888888) >> 3). GCC should generate really nice SIMD code for this if you put it in a loop. Probably there is some even better instruction sequence.

Alternatively, consider the logic approach with 3-bit packing. Denote the bits of a by a0, a1, a2 and the bits of b by b0, b1, b2 (in the standard representation). Feeding the addition table in this representation into Mathematica's BooleanFunction gives the expressions

c0 = (~a0 & ~a1 & b0) | (~a2 & b0) 
c1 = (~a0 & ~a1 & b1) | (~a2 & b1)
c2 = (~a0 & ~a1 & ~b0 & ~b1 & b2) | (~a2 & ~b0 & ~b1 & b2)

for the output bits. Should also do very well for SIMD. One would need to experiment a bit with how one arranges the bits inside words to minimize shuffling.