Constant division and modulo via carrysave modulo reduction

A method comprising:

• receiving an input value including a plurality of bits;
• and
• computing a quotient of the input value with respect to an odd integer constant via a circuit configured to perform constant modulo and division operations via concurrent bitwise operations, the concurrent bitwise operations including:
• computing an array of values based on a plurality of multi-bit groups of the plurality of bits of the input value, each value in the array of values including a modulus of a corresponding multi-bit group with respect to the odd integer constant, wherein after computation, the array of values includes a value equal to the modulus of the input value with respect to the odd integer constant;
• computing the quotient based on the array of values, the input value, and the odd integer constant;
• and
• outputting the modulus and the quotient.

A data processing system comprising:

• a memory device;
• and
• one or more processors coupled with the memory device, the one or more processors including a graphics processor, the graphics processor configured to:
• receive an input value including a plurality of bits;
• and
• compute a quotient of the input value with respect to an odd integer constant via a circuit of the graphics processor, the circuit configured to perform constant modulo and division operations via concurrent bitwise operations, including to:
• compute an array of values based on a plurality of multi-bit groups of the plurality of bits of the input value, each value in the array of values including a modulus of a corresponding multi-bit group with respect to the odd integer constant, wherein after computation, the array of values includes a value equal to the modulus of the input value with respect to the odd integer constant;
• compute the quotient based on the array of values, the input value, and the odd integer constant;
• and
• output the modulus and the quotient.