<p>Related to, but not the same question: <a href="https://langdev.stackexchange.com/q/259/38">Distinguishing modulo (Euclidean division) from remainder</a></p>
<p>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:
<a href="https://i.sstatic.net/lzmwD.png" rel="noreferrer"><img src="https://i.sstatic.net/lzmwD.png" alt="Truncated Division (Wikipedia Image)" /></a></p>
<p>However, most of the time in practice the Euclidean modulo is <a href="https://langdev.stackexchange.com/a/285/38">more useful</a>. The result is always 0 or positive. This leads to idioms along the lines of:</p>
<pre><code>unsigned euclidean_mod(int a, int b) {
    int m = a % b;
    return m &lt; 0 ? m + b : m;
}
</code></pre>
<p>This leads to Euclidean modulo:</p>
<p><a href="https://i.sstatic.net/VZczP.png" rel="noreferrer"><img src="https://i.sstatic.net/VZczP.png" alt="Euclidean Division (Wikipedia Image)" /></a></p>
<p>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?</p>

<math><division><modulo>
Why is truncated or non-Euclidean division/modulo the norm?
CC BY-SA 4.0
2024-01-25T21:19:32.467Z
[The answer by Jules to the question you linked](https://langdev.stackexchange.com/a/505/1769) 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.
IMSoP
CC BY-SA 4.0
2024-01-25T21:49:58.847Z
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
Chris Dodd
CC BY-SA 4.0
2024-01-26T07:17:46.753Z
I don't think it's the norm. Most likely they learned from C.
user23013
CC BY-SA 4.0
2024-01-26T12:02:14.170Z
@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)?
Steve
CC BY-SA 4.0
2024-01-26T12:30:10.343Z
@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.
IMSoP
CC BY-SA 4.0
2024-01-26T14:40:37.687Z
@IMSoP, the reason I'm distinguishing "remainder" from "modulo" is precisely to emphasise that they are not the same operators and they are not used for the same purposes. The fact that many languages conflate the terminology or furnish only one of these two operators is part of the problem. We accept the equation of `quotient * divisor + remainder = dividend` should constrain the definition of the division and remainder operator pair. (1/2)
Steve
CC BY-SA 4.0
2024-01-26T14:41:00.613Z
But I don't consider Euclidean modulo to be a "remainder" at all in an arithmetic sense, but as an operator of its own kind. Why therefore shouldn't there be a modulo operator (distinct from the remainder operator) which need not accord with the definition of the standard division and remainder? Effectively, in terms of the OP's question, why shouldn't C have furnished both operators? (2/2)
Steve
CC BY-SA 4.0
2024-01-26T14:55:46.653Z
@Steve I think that's a subtly different question (why is there not an _extra_ operator, rather than why is there not a _different_ operator), and is basically just an extra example for this one: https://langdev.stackexchange.com/q/3158/1769 (Which I have referred to in my answer below.)
IMSoP
<p>The answer is largely given at the top of <a href="https://langdev.stackexchange.com/a/505/1769">the answer by Jules to the question you linked</a>:</p>
<blockquote>
<p>In short, div-mod operations come in pairs satisfying the equation</p>
<p><code>x = (x/n)*n + (x%n)</code></p>
</blockquote>
<p>In words, &quot;you can reverse an integer division by multiplying by the divisor and adding the result of the % operator&quot;.</p>
<p>Since division is a more common operation than modulo on its own, it's not surprising that most implementations choose what <a href="https://dl.acm.org/doi/pdf/10.1145/128861.128862" rel="nofollow noreferrer">Raymond Boute</a> refers to as a &quot;div-dominant&quot; implementation: a definition of <code>/</code> is chosen first, and the definition of <code>%</code> is simply the one which satisfies the above equation.</p>
<p>As <a href="https://retrocomputing.stackexchange.com/a/17448/11790">mentioned in this answer</a>, the equation can actually be used to <em>implement</em> a modulo on an architecture which doesn't have a dedicated instruction; essentially:</p>
<pre><code>let quotient = a / b
let temp = quotient * b
let remainder = a - temp
</code></pre>
<p>This is all very straight-forward for unsigned integers - all algorithms agree that <code>8 / 3</code> is <code>2</code> and so <code>8 % 3</code> is <code>8 - (2 * 3)</code> which is <code>2</code>. But once you allow negative numbers, things become more complicated.</p>
<p>A simple conceptualisation is as &quot;sign and magnitude&quot;: to calculate <code>a / b</code>, first calculate <code>abs(a) / abs(b)</code>, 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 &quot;truncating&quot; or &quot;rounding toward zero&quot;: the true value of <code>-8 / 3</code> is <code>-2.666...</code> and we give the result as <code>-2</code>.</p>
<p>Using our definition of modulo above, we then end up with <code>-8 - (3 * -2)</code>, which is <code>-2</code>. 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 &quot;sign and magnitude&quot;: calculate <code>8 % 3</code>, then copy the sign of the dividend.</p>
<p>This is the operator that is commonly implemented, either in hardware (e.g. in the 8086 <code>IDIV</code> instruction, which calculates division and modulo simultaneously) or in the compiler.</p>
<p>It would be <em>possible</em> to use a &quot;mod-dominant definition&quot; of both operators, and choose Euclidean modulo for the <code>%</code> operator, but this leads to a less intuitive definition of division: <code>8 / -3</code> is <code>-2</code>, but <code>-8 / 3</code> is <code>-3</code>.</p>
<p>It would also be possible to include a separate &quot;Euclidean modulo&quot; operator - and some languages do - but that leads us to the general question of <a href="https://langdev.stackexchange.com/q/3158/1769">why languages don't include all the maths operations you might need</a>. As I state in my answer to that question:</p>
<blockquote>
<p>The bottom line is you can't have everything.</p>
</blockquote>
<p>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.</p>

CC BY-SA 4.0
2024-01-26T14:54:50.300Z
2024-01-26T16:09:26.717Z
2024-01-26T16:09:26.717Z
IMSoP
# Why is truncated or non-Euclidean division/modulo the norm?
Posted by: username_0 on 2024-01-25
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:

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:

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?
**Tags:** math division modulo
> **Comments:**
> **username_1**: [The answer by Jules to the question you linked](https://langdev.stackexchange.com/a/505/1769) 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.  
> **username_2**: 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  
> **username_3**: I don't think it's the norm. Most likely they learned from C.  
> **username_4**: @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)?  
> **username_1**: @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.  
> **username_4**: @IMSoP, the reason I'm distinguishing "remainder" from "modulo" is precisely to emphasise that they are not the same operators and they are not used for the same purposes. The fact that many languages conflate the terminology or furnish only one of these two operators is part of the problem. We accept the equation of `quotient * divisor + remainder = dividend` should constrain the definition of the division and remainder operator pair. (1/2)  
> **username_4**: But I don't consider Euclidean modulo to be a "remainder" at all in an arithmetic sense, but as an operator of its own kind. Why therefore shouldn't there be a modulo operator (distinct from the remainder operator) which need not accord with the definition of the standard division and remainder? Effectively, in terms of the OP's question, why shouldn't C have furnished both operators? (2/2)  
> **username_1**: @Steve I think that's a subtly different question (why is there not an _extra_ operator, rather than why is there not a _different_ operator), and is basically just an extra example for this one: https://langdev.stackexchange.com/q/3158/1769 (Which I have referred to in my answer below.)  
---
## 1 answers
### Answer by username_1 on 2024-01-26. Score: 5 | Accepted answer
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.
---
