7
$\begingroup$

Related to, but not the same question: Distinguishing modulo (Euclidean division) from remainder

There are multiple ways a modulo operation can be performed. Most implementations, in C, for example, use truncated division/modulo. The sign of the result equals the sign of the dividend: Truncated Division (Wikipedia Image)

However, most of the time in practice the Euclidean modulo is more useful. The result is always 0 or positive. This leads to idioms along the lines of:

unsigned euclidean_mod(int a, int b) {
    int m = a % b;
    return m < 0 ? m + b : m;
}

This leads to Euclidean modulo:

Euclidean Division (Wikipedia Image)

My question is, what factors lead the former to be the 'default' in programming languages such as C, even if the latter is more useful in practice?

$\endgroup$
8
  • $\begingroup$ The answer by Jules to the question you linked seems to cover this: you can't (or shouldn't) choose a modulo definition in isolation, only alongside a corresponding division definition, and the definition of Euclidean division isn't particularly intuitive. $\endgroup$
    – IMSoP
    Jan 25 at 21:19
  • 3
    $\begingroup$ Originally, C didn't define the details of division, and just used whatever the hardware it was running on used for division. But (almost) all hardware that supports integer division directly defines it as truncating towards 0 $\endgroup$
    – Chris Dodd
    Jan 25 at 21:49
  • $\begingroup$ I don't think it's the norm. Most likely they learned from C. $\endgroup$
    – user23013
    Jan 26 at 7:17
  • $\begingroup$ @IMSoP, whilst it seems obvious why the definition of remainder should be related to integer division, why should the modulo necessarily be related to division (or at least, why should it have to be related to the same definition of division as the remainder operator)? $\endgroup$
    – Steve
    Jan 26 at 12:02
  • 2
    $\begingroup$ @Steve I'm not sure if I'm following you correctly. Distinguishing between "remainder" (as the complement of integer division) and "modulo" (as an unpaired "Euclidean" operator) might be a valid design decision, but most languages just have a single operator, such as %. Whether you pronounce it "remainder", "modulo", or "that percent-y thing" doesn't change the expectation: that you can reverse an integer division by multiplying by the divisor and adding the result of the % operator. Generally, what the Boute paper calls a "div-dominant definition" is used: define /, then make % match. $\endgroup$
    – IMSoP
    Jan 26 at 12:30

1 Answer 1

5
$\begingroup$

The answer is largely given at the top of the answer by Jules to the question you linked:

In short, div-mod operations come in pairs satisfying the equation

x = (x/n)*n + (x%n)

In words, "you can reverse an integer division by multiplying by the divisor and adding the result of the % operator".

Since division is a more common operation than modulo on its own, it's not surprising that most implementations choose what Raymond Boute refers to as a "div-dominant" implementation: a definition of / is chosen first, and the definition of % is simply the one which satisfies the above equation.

As mentioned in this answer, the equation can actually be used to implement a modulo on an architecture which doesn't have a dedicated instruction; essentially:

let quotient = a / b
let temp = quotient * b
let remainder = a - temp

This is all very straight-forward for unsigned integers - all algorithms agree that 8 / 3 is 2 and so 8 % 3 is 8 - (2 * 3) which is 2. But once you allow negative numbers, things become more complicated.

A simple conceptualisation is as "sign and magnitude": to calculate a / b, first calculate abs(a) / abs(b), and then choose a sign for the result based on the signs of a and b. Specifically, if a and b have the same sign, the result is positive; else, it is negative. This is mathematically equivalent to "truncating" or "rounding toward zero": the true value of -8 / 3 is -2.666... and we give the result as -2.

Using our definition of modulo above, we then end up with -8 - (3 * -2), which is -2. It turns out that in this definition, the sign of the remainder is always the same as the sign of the dividend, so again, we can treat it as "sign and magnitude": calculate 8 % 3, then copy the sign of the dividend.

This is the operator that is commonly implemented, either in hardware (e.g. in the 8086 IDIV instruction, which calculates division and modulo simultaneously) or in the compiler.

It would be possible to use a "mod-dominant definition" of both operators, and choose Euclidean modulo for the % operator, but this leads to a less intuitive definition of division: 8 / -3 is -2, but -8 / 3 is -3.

It would also be possible to include a separate "Euclidean modulo" operator - and some languages do - but that leads us to the general question of why languages don't include all the maths operations you might need. As I state in my answer to that question:

The bottom line is you can't have everything.

Every feature you add to a language, or processor instruction set, has a cost; and evidently a separate Euclidean modulo hasn't proven a sufficiently common requirement to justify that cost in the eyes of language and processor designers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .