Ada, C, rem and mod

2014-01-14

Ada has two similar operators, rem and mod.

rem is a mathematical remainder in the sense of the remainder of an integer division:

(x rem y) + (x div y)*y == x

The mod operator, on the other hand, is designed to satisfy a cyclic property across the number line:

∃ n : x mod y + y * n == x

(in other words, there is a value of n such that x mod y + y*n == x)

To visualize the differences between these operations, look at the below graphs:

Figure 1: rem operator

Mod operator graph where second operand is positive

Figure 2 mod operator (where second operand is positive)

Mod operator graph where second operand is negative

Figure 3: mod operator (where second operand is negative)

Things to note:

If both operands are positive, rem and mod give the same result.
For rem, the sign of the second operand has no effect on the result
For rem, the sign of the first operand is the same as the sign of the result
For mod, the sign of the second operand is the same as the sign of the result

Somewhat confusingly, in C99 standard the % operator is usually referred to as mod, although it actually implements the behavior of rem.

It's important to point out that before C99, the behavior of the % operator for negative numbers is implementation-specific, so should probably be avoided. The rationale for keeping this behavior in the ANSI-C standard was discussed here.

Since C only implements the behaviour of rem, one might wonder if the mod behaviour from Ada is easy to implement as well. Here's one possibility for the little-endian x86 target. As we like to reduce variation in execution time (this makes for better worst-case execution times), it's been written to be jump-free. Since it involves a divide and a multiply, though, there is still the potential for some variation from those instructions - this will depend on the exact target and the type of data being processed.

int do_mod( int x, int y )
{
long long work_buffer = 0;
int mask_1;
int result;
result = x % y;                  // compute basic result
*(int *)(&work_buffer) = result; // put it in a longer variable, no ext
mask_1 = (-work_buffer) >> 32;   // negate and shift: zero if x&y is zero
mask_1 &= ((x*y)>>31);           // mask out when signs are the same too
result += (mask_1&y);            // if x%y non zero and signs differ, adjust
return result;
}

Hand-coding this algorithm in assembler could potentially lead to some significant improvements. For example, the manipulation to check for all zeros could be handled with a test and a set instruction.