Vibe check: `rem_euclid_unsigned`

libs
1

Before firing off an ACP, just checking that I haven't missed anything. Not sure if this was discussed when the _euclid() methods were first introduced.

Motivation: I recently wrote some wrapper code that allows indexing slices with isize, giving modulo-len wraparound semantics which is often useful.

fn index(&self, i: isize) -> T {
    self[i.rem_euclid(self.len() as isize) as usize]
}

This implementation has two casts too many for my taste, neither of which can fail or wrap[1] but the compiler doesn't know that. Using try_into() would just introduce noise.

The current Euclidean remainder methods for iNN are defined as

fn rem_euclid(self, divisor: Self) -> Self

This is consistent with how most other arithmetic operations are typed, but it has a couple of consequences:

  • The return type is signed but the result is always nonnegative by definition;
  • Typical use cases (indexing an array) thus require an immediate cast to unsigned that can't fail or wrap but that can't be statically checked;
  • There's an extra panic path for self = Self::MIN and divisor = -1[2]
  • For all other paths, a.rem_euclid(b) == a.rem_euclid(-b), making negative divisors redundant;
  • But on the other hand, an unsigned divisor would have a lot of additional perfectly cromulent values even though the result is not very interesting (a for all a ≥ 0, b+a (that is, b-a.abs()) for the rest.)

So, I'd like to propose

impl iNN {
    pub fn rem_euclid_unsigned(self, divisor: uNN) -> uNN
}

I haven't though much about whether a div_euclid_unsigned would be similarly helpful.

  1. except if T is a ZST I guess ↩︎

  2. it's the division that overflows, the remainder is well-defined: zero. ↩︎

6 Likes
2

I think the euclid part might be redundant. It's pretty much implied from the return type, since of course the remainder the gives an unsigned value would be the one that's by definition non-negative. Also, if the divisor is also unsigned, then that also means there's no different between Euclidean and flooring division.

So rather than rem_euclid_unsigned, I'd suggest fn rem_unsigned(iN, uN) -> uN and fn div_unsigned(iN, uN) -> iN.

The fact that these are both Euclidean division and flooring division simultaneously, having them would enable the side benefit of not needing to guess which of the two would be faster. I'd suspect that div_unsigned would be able to completely replace most uses of both div_floor and div_euclid.

2 Likes
3

but to me div_unsigned implies using truncating division (since that's the default kind of division in Rust), where -3 / 4 == 0 but (-3i32).div_floor(4) == -1), so using div_unsigned to refer to flooring division sounds highly unintuitive to me.

So, I think it should be div_floor_unsigned, and we can also have div_ceil_unsigned (for ceiling division) and div_unsigned (for truncating division) and all the corresponding rem_*_unsigned functions.

4

In fairness, div to me means flooring division, and nothing means truncating division. I consider CPU signed integer division to be broken by design (unsigned integer division is fine).

Also I could just as easily say that -7 / 4 = -1 when truncating, which is definitely not more unsigned than (-7i32).div_floor(4) == -2.

1 Like
5

This is now an ACP. Add `rem_euclid_unsigned()` for signed integer types · Issue #838 · rust-lang/libs-team · GitHub

6

It would be nice to generalize the principle behind this to, not just producing an unsigned output, but producing a potentially narrower output, taking advantage of the fact that the result is necessarily smaller than the divisor to provide a function that can change numeric type without ever overflowing:

impl iNN {
    pub fn rem_euclid_unsigned<U: UnsignedInt>(self, divisor: U) -> U
}

(or the corresponding family of methods instead of generics)

7 Likes