Code Poetry
and Text Adventures

by catid posted (>30 days ago) 12:53am Wed. May 17th 2017 PDT
For implementing math modulo Q, a number of the form Q = 2^^n - c, there's a neat trick I learned a while back called partial reduction.

The trick is to allow the inputs and outputs to your "add" and "subtract" functions to go outside the range 0..(Q-1).  Instead of having to constantly fix the result of every operation to go back in that range, the code can be sloppy (and faster) during calculations.

For a simple practical example from some recent code I'm working on, here are add/sub routines for Q = 65535, which also works for Q = 255.

typedef uint16_t GFSymbol;
static const unsigned kGFBits = 16;

//------------------------------------------------------------------------------
// Mod Q Field Operations
//
// Q is the maximum symbol value, e.g. 255 or 65535.

// z = x + y (mod Q)
static inline GFSymbol AddModQ(GFSymbol a, GFSymbol b)
{
   const unsigned sum = (unsigned)a + b;

   // Partial reduction step, allowing for Q to be returned
   return static_cast<GFSymbol>(sum + (sum >> kGFBits));
}

// z = x - y (mod Q)
static inline GFSymbol SubModQ(GFSymbol a, GFSymbol b)
{
   const unsigned dif = (unsigned)a - b;

   // Partial reduction step, allowing for Q to be returned
   return static_cast<GFSymbol>(dif + (dif >> kGFBits));
}

To convince myself, I verified these with a unit test that tries all possible inputs and checks to make sure the result makes sense.

From X % 65535 the Visual Studio 2017 compiler will generate a multiply and shift in this case, which is definitely not as nice as the shift + add above.  And for subtraction it would need an extra add.
last edit by catid edited (>30 days ago) 12:59am Wed. May 17th 2017 PDT