13
$\begingroup$

The % operator in most programming language provide a remainder from integer division. When both operands are positive all works as expected. But when the number is negative there is a difference between Euclidean modulo and remainder.

The Euclidean division modulo will always be positive if the divisor is positive. In this case a % b will have the range [0, b) provided b is positive. This is where & (powerof2 - 1) is equivalent to % powerof2. (-1) & 15 is 15, and assuming Euclidean division, (-1) % 16 is also 15.

This is not the case for non-Euclidean remainder, where a % b would have the range [-b, b). This would result in negative numbers, causing problems for operations such as normalizing angles between 0 and 360 degrees etc. (-1) % 16 in this case would be -1.

Given that there is only one % operator, how could a programming language allow a programmer to differentiate between these distinct ways to handle negatives in modulo/remainder operations?

$\endgroup$
5
  • $\begingroup$ "differentiate" as in letting the programmer easily know the difference, or provide options for a programmer? $\endgroup$ Commented May 17, 2023 at 2:32
  • $\begingroup$ @justANewbie The latter $\endgroup$
    – CPlus
    Commented May 19, 2023 at 14:40
  • 1
    $\begingroup$ Please note that there exist languages which have both a mod and a rem operator, or both a modulo and a remainder operator, and if you take two languages that do, you'll probably find that the two languages do not agree about which name corresponds to which convention. For instance, it would make sense to name "mod" the operator that follows the same convention as C language's %, and to name "rem" the operator that corresponds to the remainder in the Euclidean division; and that is the exact opposite of the definitions in your question. $\endgroup$
    – Stef
    Commented Jun 30, 2023 at 11:47
  • 1
    $\begingroup$ Also, your question makes the assumption that there are only two possible conventions, but in the expression a % b there are four possible combinations of the signs of a and b, and there is a non-obvious choice to make for at least three of these combinations (only a negative, only b negative, both negative); so in theory there could be up to 8 different conventions; and Wikipedia lists 5 of these conventions as actually in use, which they refer to as "truncated, rounded, floored, ceiled, Euclidean". $\endgroup$
    – Stef
    Commented Jun 30, 2023 at 12:03
  • $\begingroup$ A similar problem is present in the rounding of integer division with negatives. And both issues are probably related. E.g. x86 div/idiv compute both quotient and reminder. $\endgroup$
    – Pablo H
    Commented Jul 21, 2023 at 13:32

5 Answers 5

10
$\begingroup$

Given the usefulness of a proper modulo operator to wrap an integer into a range [0, n) e.g. for an array index or generating a random integer in this range, I find this far more useful than the remainder operator.

Personally if I were to implement both in a language, I would make % the modulo operator and relegate remainders to a function in the standard library, perhaps rem(a, b) for just the remainder and divrem(a, b) for computing both a truncated division and remainder. I just don't see any use for the remainder operator so I don't see any value in having a specific syntax for it.

If you do want both to be operators, another option is to use keywords instead of punctuation, so e.g. a mod b and a rem b to distinguish between them. (This goes better if other operators in your language, like and, or and not, are also keywords.) An upside is that words are much easier to search for online compared to punctuation, for users who don't know the meaning of these operators or the difference between them.

$\endgroup$
2
  • $\begingroup$ Why requiring keywords for operators when identifiers do the job? Scala's x mod y is the same as x.mod(y), Haskell's x `mod` y and Ante's x .mod y are the same as mod x y. $\endgroup$
    – Longinus
    Commented May 27, 2023 at 4:09
  • 1
    $\begingroup$ @Longinus I think that's a separate question. $\endgroup$
    – kaya3
    Commented May 27, 2023 at 9:46
10
$\begingroup$

There are two great articles investigating this question:

  1. Division and Modulus for Computer Scientists by Daan Leijen
  2. The Euclidean Definition of the Functions div and mod by Raymond Boute

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

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

This means that if we define one of the two operations, then we have no choice for the other operation because it is already determined by that equation.

We can define division in these ways:

  1. Round up (ceil)
  2. Round down (floor)
  3. Round nearest (round)
  4. Round toward zero (truncate)

It turns out that round down has the most useful corresponding modulo operation, because the modulo operation associated with round down always produces a number x%n in [0,n) whenever n is positive, even if x is negative.

There is a fifth option, called Euclidean div-mod, which postulates that x%n should always be in the range [0,abs(n)) even if n is negative. This then has an associated div operation that is different from any of the four listed above.

The articles conclude that these are the only two sensible options for a div-mod pair:

  1. Floor: mod gives a number in the range [0,n), div is floored division
  2. Euclidean: mod gives a number in the range [0,abs(n)), then define div in terms of the equation above

These two choices only differ when the divisor n is negative. They agree when n is positive, even when x is negative. Furthermore, it is easy to define option 1 in terms of option 2 and vice versa. The floor div-mod just gives a number in the range [0,n) always, even if n is negative. That is, if n=-10, then the floor mod operation gives a number in the range (-10,0]. In other words, the sign of x%n is the same as the sign of n for the floor option, whereas the sign of x%n is always positive for the Euclidean option.

The articles argue that Euclidean is better because it results in a slightly better mod operation. However, the floor option has the following advantages:

  1. The floored div operation is easy to understand: div(x,n) = floor(x/n). It's a bit less clear what the Euclidean div means for negative n.
  2. These two options only differ for negative divisors, and mod with a negative divisor is almost never useful, but div with a negative divisor is occasionally useful.
  3. It is easy to get the Euclidean mod using the floored mod: mod_euclid(x,n) = x % abs(n). I would argue that if your code is doing mod with negative divisors, then it is in fact clearer to have that explicit abs in your code as a signifier that something is going on.

On the other hand, it is true that Euclidean div-mod makes it more natural to convert numbers to negative base with positive digits.

In my opinion, either of these two options is fine.

$\endgroup$
5
$\begingroup$

One could always take the route of C's pairs of "and" and "or" operators -- call one % and the other %%.

$\endgroup$
3
$\begingroup$

I support Bbrk24's answer, but to add on; whether you use % or %% for Euclidean modulo, you should consider what the target programmers will be more inclined to use. If you predict your language is for JavaScript V8 users, use % for the remainder and %% for Euclidean modulo. If it is for Python, set it the other way around.

This all depends on who you think is going to use your language. Else you'll have disgruntled programmers complaining about having to put weird symbols just to get the intended result when modulo-ing.

$\endgroup$
1
  • $\begingroup$ If it's python you could have a with floored_division: or with truncated_division: environment to modify the behaviour of // and % ;-p $\endgroup$
    – Stef
    Commented Jun 30, 2023 at 12:10
0
$\begingroup$

One solution I thought of that would remove the ambiguity problems with % and %% would be to use &% for proper modulo and % for remainder. Since & with a one less than power of 2 is reminiscent of proper modulo by power of 2, combining & with % to result in a proper Euclidean modulo operation would be consistent.

$\endgroup$

You must log in to answer this question.

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