(Mathematical) modulo operator

language design
1

Rust currently has a remainder operator in the form of %, which behaves as the operator of the same symbol does in languages like C or Java. It is also similar to the modulo operator found in languages such as Python or Haskell, except for its behaviour for negative arguments – remainder is based on truncating division, whereas modulo is based on flooring division.

In the vast majority of cases whilst programming (see http://dl.acm.org/citation.cfm?doid=128861.128862), the behaviour of the modulo operator is more useful than that of the remainder operator. Therefore, it would be useful to add a modulo operator to the language.

This issue has been discussed before: https://mail.mozilla.org/pipermail/rust-dev/2013-April/003680.html, as well as having been brought up in various other places (https://github.com/rust-lang/rust/issues/13909, https://stackoverflow.com/questions/31210357/is-there-a-modulus-not-remainder-function-operation, https://users.rust-lang.org/t/proper-modulo-support/903, https://www.reddit.com/r/rust/comments/3yoo1q/remainder/, etc.), but although the general consensus seems to be that having an operator for modulo (in addition to the remainder operator) would be very useful: as it is, there is no operator or standard library method to achieve this.

As no progress seems to have been made on this issue for a while now, I’d like to make an RFC to add a new operator, %% (bike-shedding aside: alternatives like mod are also fine, but I think having an operator as opposed to just a method is very helpful) that implements this functionality. Below is a snippet showing some of the differences between the two operations:

// Remainder operator (%)
5 % 3 // 2
5 % -3 // 2
-5 % 3 // -2
-5 % -3 // -2

// Modulo operator (%%)
5 %% 3 // 2
5 %% -3 // -1
-5 %% 3 // 1
-5 %% -3 // -2

It may also be helpful to define a flooring division operator \, which forms a pair with modulo, as / is paired with %, so that just as (a / b) * b + (a % b) == a, we have: (a \ b) * b + (a %% b) == a. (The syntax is unimportant for now.)

Is an RFC the right place to start? What details are important to clarify in such an RFC?

7 Likes
2

Sounds good, this discussion needs to be restarted. Unfortunately the golden moment for RFCs has just passed, we’re in the Impl period now. But I agree that it’s a good idea to write this RFC now still.

If an operator like “%%” will be refused, then a standard library or Prelude mod() method will be acceptable, in my opinion. The flooring division div() is equally nice.

1 Like
3

I’m also very much in favor of adding this functionality. Of course, the exact operator names (or method names) have to be discussed.

1 Like
4

There’s a good reason rem is not called mod. (Try making your own mod; you’ll see).

A corresponding division operator is an absolute must. The modulus is next to worthless without one.

Forget floored division. Can’t we be the first language to actually get this right, by implementing Euclidean division?

Euclidean modulus - It’s in [0, n), period.

 2 %%  5 == 2
-2 %%  5 == 3
 2 %% -5 == 2
-2 %% -5 == 3

(Edit: Apparently I can’t math. Fixed.)

8 Likes
5

As this is a functionality that is very useful once in while, but not overly common, I’d prefer an std function instead of introducing extra syntax.

11 Likes
6

I agree with @konstin. Adding some Modulo trait which is implemented for all numerics is probably a better idea given how % is usually good enough for normal programming. It’s also a lot easier to add something to std than adding new operators to the language.

What about something like this?

pub trait Modulo<RHS=Self> {
  type Output;
  fn modulo(&self, rhs: &RHS) -> Self::Output;
}

Then insert use std::num::Modulo into the prelude.

While we’re at it, it’d be nice to have something like Python’s divmod() too (or just steal it from num) :stuck_out_tongue_winking_eye:

4 Likes
7

Note that you’ll need to introduce checked_modulo(), wrapping_modulo() and overflowing_modulo() in additional to the normal modulo method.

8

An advantage of having extra syntax is that it's less easy to forget/ignore. The problem with % is that you have to remember how it works on negative numbers (and often it's not the behaviour you want). But I agree that having mod() and div() could be acceptable...

9

Even with two operators you had to remember which does what, so two unambiguously named functions would be perfect.

10

I would also prefer descriptive names such as ‘mod’ and ‘div’ to purely symbolic operators, given how subtle the differences in behavior are. Euclidean division as proposed by @ExpHP is probably the most conceptual and least confusing way a ‘division with remainder’ operation can be specced, but this particular detail would not be that important to me given how rare use cases for negative moduli should be. In any case having ‘mod’ around would be quite useful.

11

The biggest problem with using %% for flooring remainder is that we can’t use // for flooring quotient.

3 Likes
12

Summing up and responding to some of the points in the replies so far:

  • While an operator would be convenient, it’s not necessary: it would probably be best to add a method (and the corresponding traits/methods/etc.) first, and then see how often it is used to decide whether a dedicated operator would then be useful.
  • Modulo operations with negative divisors are very uncommon (unlike negative dividends), so either the flooring or Euclidean modulo would be appreciated. (Personally, I have no great preference either way.) Perhaps it would be useful to examine some particular use cases, open up a vote or consider adding both as suitably-named methods.
  • The %% operator is awkward, in that it cannot be symmetrical with a // operator. If an operator was added, we’d want to think more carefully about this, but it seems the preference is simply for a method to begin with anyway.
  • The timing with the impl. period is unfortunate, but it’ll take some time to work out something that seems most sensible, so it means there’s less pressure to get something done too quickly.

The reaction has been positive so far, so I’ll start working out some of the more technical details. Do share any more thoughts you have about anything brought up so far, and I’ll share when I have something a little more concrete!

5 Likes
13

The C Standard states:

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (This is often called ‘truncation toward zero’). If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

This matches actual behavior of at least x86 "div" and "idiv" instructions:

Non-integral results are truncated (chopped) towards 0. The remainder is always less than the divisor in magnitude.

Decision to step aside from this "traditional" semantics may result in consequences that should be at least documented:

  1. Does the "new modulo" operator result in extra assembly instructions (and extra run-time costs) on popular cpu architectures?
  2. Does the "new modulo + new divide" pair have extra "overflow" situations near the corner values (like diving INT_MIN by -1)?
14

Nobody wants to change the existing / or % operators, and they’re not going to be deprecated either.

1 Like
15

It just occurred to me that f32 and f64 implement Rem with absolutely no way to get the corresponding integer division. That just breaks my heart.

Edit:

fn f64_div_rem(x: f64, m: f64) -> (f64, f64) {
    // strawman implementation; might not have the best possible accuracy
    let rem = x % m;
    let div = (x - rem) / m;
    (div, rem)   // satisfies  x == div * m + rem
}
16

It’s faster to avoid doing two divisions:

    let div = (x / m).trunc();
    let rem = x - div * m;
17

Some languages like Haskell have a syntax for infix functions, so a `mod` b does the same thing as a.mod(b). Of the two I think I would prefer allowing general infix functions.

18

There's an RFC issue for infix notation:

19

With the general consensus that functions will be sufficient for now, the implementation becomes simpler and more minimal. I feel there’s really just one question left now, other than the bikeshedding. Other than that, this proposal should be fairly minimal (and it’s just a case of making sure the arithmetic is correct in all the edge cases).

1. General Division/Modulo functions

The primary question now is whether both flooring and Euclidean division/modulo are useful enough to warrant adding the functionality of both (as it will be simpler to devise a more flexible solution now than later, should it be decided useful later on). Assuming this could be useful, my preference would be to add general division and modulo functions, implemented by each integer type, with an enum (in core::num) specifying the division mode:

pub enum DivisionMode {
    Truncating,
    Flooring,
    Euclidean,
}
// Generalised division and modulo, to be implemented for all integer types
div_round(self, rhs: Self, mode: DivisionMode) -> Self
mod_round(self, rhs: Self, mode: DivisionMode) -> Self

These would then be implemented fairly simply in Rust, e.g.:

fn mod_round(self, rhs: Self, mode: DivisionMode) -> Self {
    match mode {
        DivisionMode::Truncating => self % rhs,
        DivisionMode::Flooring => ((self % rhs) + rhs) % other,
        DivisionMode::Euclidean => self.mod_round(rhs.abs(), DivisionMode::Flooring),
    }
}

2. Single division/modulo functions

If it seems unlikely that both flooring modulo and Euclidean modulo would be useful independently, there’s little point in adding both. Unless there’s a good reason not to, I would lean towards flooring modulo which has the advantages that: (a) it requires one fewer (abs) operations; (b) can easily be used to implement Euclidean modulo if really needed.

There’s a slight annoyance here, as Rust names its operators inconsistently to other languages like Haskell. Rust’s truncating integer division is called div, as opposed to the more typical quot, so reusing this naming for flooring division and modulo could be confusing. I’d therefore suggest a more explicit naming scheme:

// Flooring division and modulo, to be implemented for all integer types
fn divf(self, rhs: Self) -> Self
fn modf(self, rhs: Self) -> Self

Other points

  • Whichever method we go with, they’re probably going to need overflowing, checked and wrapping versions (leading to another 6 functions), as the edge cases are different to that of truncating division and remainder. However, this should probably be it: I can’t see any other places new functions or traits should need to be added.
  • I don’t think sweating over the assembly generated for these functions is important at this stage — for the most part, the factor of 2 or less (https://stackoverflow.com/questions/4102423/efficiently-implementing-floored-euclidean-integer-division) is very unlikely to be important – in such cases, it is likely the remainder operator would suffice.

Personally, I think the Euclidean variants are probably unnecessary, and prefer the second option. Once I’ve heard the feedback you have, I’ll write up the RFC proper!

1 Like
20

I suggest to restrict a little the scope of your proposal…

1 Like