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.

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.

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));

}

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