'Double modulo' operator

I wouldn't mind if the standard `%` operator worked like this and there would be another top-level function `mod(p, q)` that worked like `%` in C. The only times that I've ever needed the modulo operation (https://en.wikipedia.org/wiki/Modulo_operation\) to behave some way on negative values it's always been the suggested remainder-of-flooring-division way.

On the other hand, there's a performance penalty (avoidable by using the other mod operation), so I can understand if not everyone agrees.

And like Steve said below, then we'll need a flooring division function (or operator) as well. And a flooring `(f, r) = divmod(p, q)` too, I suppose.

In any case, I'm probably +1 if a well-thought proposal is brought to the table.

— Pyry

···

Adam Nemecek wrote:

Would you want to make this a function? Or an operator but a different one?

On Mon, May 23, 2016 at 7:30 AM, Stephen Canon <scanon@apple.com> wrote:
I’m not really sold on the `%%` spelling, but I think the operation itself is worth exposing. This is the remainder of a “flooring” division (as opposed to the C-family “truncating” division[1]). If we do provide it, we should also provide the accompanying divide operation.

– Steve

[1] there are several other ways to define division beyond these two: remainder is always positive, remainder is closest to zero, etc. Truncating and flooring division are the most common by a wide margin, however.

1 Like

That kind of breaks backwards compatibility.

Also currently in swift, the % operator is called the remainder operator,
not the modulo operator, so technically the current implementation is
correct. In Haskell for example, there are two functions, rem (as in
remainder) and mod (as in modulo). I guess we could leave % to mean
remainder and introduce a mod function?

···

On Mon, May 23, 2016 at 11:59 AM, Pyry Jahkola <pyry.jahkola@iki.fi> wrote:

I wouldn't mind if the standard `%` operator worked like this and there
would be another top-level function `mod(p, q)` that worked like `%` in C.
The only times that I've ever needed the modulo operation (
https://en.wikipedia.org/wiki/Modulo_operation\) to behave *some way* on
negative values it's always been the suggested
remainder-of-flooring-division way.

On the other hand, there's a performance penalty (avoidable by using the
other mod operation), so I can understand if not everyone agrees.

And like Steve said below, then we'll need a flooring division function
(or operator) as well. And a flooring `(f, r) = divmod(p, q)` too, I
suppose.

In any case, I'm probably +1 if a well-thought proposal is brought to the
table.

— Pyry

Adam Nemecek wrote:

Would you want to make this a function? Or an operator but a different one?

On Mon, May 23, 2016 at 7:30 AM, Stephen Canon <scanon@apple.com> wrote:

I’m not really sold on the `%%` spelling, but I think the operation
itself is worth exposing. This is the remainder of a “flooring” division
(as opposed to the C-family “truncating” division[1]). If we do provide
it, we should also provide the accompanying divide operation.

– Steve

[1] there are several other ways to define division beyond these two:
remainder is always positive, remainder is closest to zero, etc.
Truncating and flooring division are the most common by a wide margin,
however.

I've had to write a "true mod" function enough times across different
projects (usually for circular buffer indexing or angular arithmetic) that
it would absolutely support its inclusion in stdlib (for both integer and
floating point types).

The `%` operator historically has been implemented as "remainder" though
(even when called "modulus"), so while it would be nice to be "pure" and
have `%` do the right thing, I think it would be too confusing for users to
have the operator have a subtly different meaning compared to every other
programming language that looks like it.

I'm not crazy about the `%%` spelling, but I can't think of anything better
either at the moment.

···

On Mon, May 23, 2016 at 12:24 PM Adam Nemecek via swift-evolution < swift-evolution@swift.org> wrote:

That kind of breaks backwards compatibility.

Also currently in swift, the % operator is called the remainder operator,
not the modulo operator, so technically the current implementation is
correct. In Haskell for example, there are two functions, rem (as in
remainder) and mod (as in modulo). I guess we could leave % to mean
remainder and introduce a mod function?

On Mon, May 23, 2016 at 11:59 AM, Pyry Jahkola <pyry.jahkola@iki.fi> > wrote:

I wouldn't mind if the standard `%` operator worked like this and there
would be another top-level function `mod(p, q)` that worked like `%` in C.
The only times that I've ever needed the modulo operation (
https://en.wikipedia.org/wiki/Modulo_operation\) to behave *some way* on
negative values it's always been the suggested
remainder-of-flooring-division way.

On the other hand, there's a performance penalty (avoidable by using the
other mod operation), so I can understand if not everyone agrees.

And like Steve said below, then we'll need a flooring division function
(or operator) as well. And a flooring `(f, r) = divmod(p, q)` too, I
suppose.

In any case, I'm probably +1 if a well-thought proposal is brought to the
table.

— Pyry

Adam Nemecek wrote:

Would you want to make this a function? Or an operator but a different
one?

On Mon, May 23, 2016 at 7:30 AM, Stephen Canon <scanon@apple.com> wrote:

I’m not really sold on the `%%` spelling, but I think the operation
itself is worth exposing. This is the remainder of a “flooring” division
(as opposed to the C-family “truncating” division[1]). If we do provide
it, we should also provide the accompanying divide operation.

– Steve

[1] there are several other ways to define division beyond these two:
remainder is always positive, remainder is closest to zero, etc.
Truncating and flooring division are the most common by a wide margin,
however.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

1 Like

You have both good points.

In that case, if we still want to define new operators here (which might not please everybody), then I'd suggest finding a common prefix or suffix character (e.g. `^/` and `^%`) for both the floored division and floored modulo (for one, because we can't define `//` as an operator).

But I think it'd be clearest to just make them both top-level functions, e.g. `floordiv(p, q)` and `floormod(p, q)`. If anyone uses either a lot, and likes to make it terse, it's easy to define a private operator wrapper for it.

— Pyry

···

Tony Allevato wrote:

I've had to write a "true mod" function enough times across different projects (usually for circular buffer indexing or angular arithmetic) that it would absolutely support its inclusion in stdlib (for both integer and floating point types).

The `%` operator historically has been implemented as "remainder" though (even when called "modulus"), so while it would be nice to be "pure" and have `%` do the right thing, I think it would be too confusing for users to have the operator have a subtly different meaning compared to every other programming language that looks like it.

I'm not crazy about the `%%` spelling, but I can't think of anything better either at the moment.

On Mon, May 23, 2016 at 12:24 PM Adam Nemecek via swift-evolution <swift-evolution@swift.org> wrote:
That kind of breaks backwards compatibility.

Also currently in swift, the % operator is called the remainder operator, not the modulo operator, so technically the current implementation is correct. In Haskell for example, there are two functions, rem (as in remainder) and mod (as in modulo). I guess we could leave % to mean remainder and introduce a mod function?

On Mon, May 23, 2016 at 11:59 AM, Pyry Jahkola <pyry.jahkola@iki.fi> wrote:
I wouldn't mind if the standard `%` operator worked like this and there would be another top-level function `mod(p, q)` that worked like `%` in C. The only times that I've ever needed the modulo operation (https://en.wikipedia.org/wiki/Modulo_operation\) to behave some way on negative values it's always been the suggested remainder-of-flooring-division way.

On the other hand, there's a performance penalty (avoidable by using the other mod operation), so I can understand if not everyone agrees.

And like Steve said below, then we'll need a flooring division function (or operator) as well. And a flooring `(f, r) = divmod(p, q)` too, I suppose.

In any case, I'm probably +1 if a well-thought proposal is brought to the table.

— Pyry

Adam Nemecek wrote:

Would you want to make this a function? Or an operator but a different one?

On Mon, May 23, 2016 at 7:30 AM, Stephen Canon <scanon@apple.com> wrote:
I’m not really sold on the `%%` spelling, but I think the operation itself is worth exposing. This is the remainder of a “flooring” division (as opposed to the C-family “truncating” division[1]). If we do provide it, we should also provide the accompanying divide operation.

– Steve

[1] there are several other ways to define division beyond these two: remainder is always positive, remainder is closest to zero, etc. Truncating and flooring division are the most common by a wide margin, however.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Seems like making it an operator will cause more issues than it solves. I think that floordiv and mod functions are probably the way to go. I'm going to wait a little longer for more feedback and write up a proposal at some point.

···

On Mon, May 23, 2016 at 1:20 PM -0700, "Pyry Jahkola" <pyry.jahkola@iki.fi> wrote:

You have both good points.
In that case, if we still want to define new operators here (which might not please everybody), then I'd suggest finding a common prefix or suffix character (e.g. `^/` and `^%`) for both the floored division and floored modulo (for one, because we can't define `//` as an operator).
But I think it'd be clearest to just make them both top-level functions, e.g. `floordiv(p, q)` and `floormod(p, q)`. If anyone uses either a lot, and likes to make it terse, it's easy to define a private operator wrapper for it.
— Pyry

Tony Allevato wrote:

I've had to write a "true mod" function enough times across different projects (usually for circular buffer indexing or angular arithmetic) that it would absolutely support its inclusion in stdlib (for both integer and floating point types).
The `%` operator historically has been implemented as "remainder" though (even when called "modulus"), so while it would be nice to be "pure" and have `%` do the right thing, I think it would be too confusing for users to have the operator have a subtly different meaning compared to every other programming language that looks like it.
I'm not crazy about the `%%` spelling, but I can't think of anything better either at the moment.
On Mon, May 23, 2016 at 12:24 PM Adam Nemecek via swift-evolution <swift-evolution@swift.org> wrote:
That kind of breaks backwards compatibility.
Also currently in swift, the % operator is called the remainder operator, not the modulo operator, so technically the current implementation is correct. In Haskell for example, there are two functions, rem (as in remainder) and mod (as in modulo). I guess we could leave % to mean remainder and introduce a mod function?

On Mon, May 23, 2016 at 11:59 AM, Pyry Jahkola <pyry.jahkola@iki.fi> wrote:
I wouldn't mind if the standard `%` operator worked like this and there would be another top-level function `mod(p, q)` that worked like `%` in C. The only times that I've ever needed the modulo operation (https://en.wikipedia.org/wiki/Modulo_operation\) to behave some way on negative values it's always been the suggested remainder-of-flooring-division way.
On the other hand, there's a performance penalty (avoidable by using the other mod operation), so I can understand if not everyone agrees.
And like Steve said below, then we'll need a flooring division function (or operator) as well. And a flooring `(f, r) = divmod(p, q)` too, I suppose.
In any case, I'm probably +1 if a well-thought proposal is brought to the table.
— Pyry
Adam Nemecek wrote:

Would you want to make this a function? Or an operator but a different one?
On Mon, May 23, 2016 at 7:30 AM, Stephen Canon <scanon@apple.com> wrote:
I’m not really sold on the `%%` spelling, but I think the operation itself is worth exposing. This is the remainder of a “flooring” division (as opposed to the C-family “truncating” division[1]). If we do provide it, we should also provide the accompanying divide operation.
– Steve
[1] there are several other ways to define division beyond these two: remainder is always positive, remainder is closest to zero, etc. Truncating and flooring division are the most common by a wide margin, however.

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution

Sorry for bumping this thread after more than two years, but it's because of a recent related post and my concurrence with the people upthread who says essentially:

  • I’ve never actually wanted a negative return value from %. It does what I need only as long as the lhs is positive, but not when it's negative. In fact, I wouldn't be surprised if many uses of % are in situations where only a positive lhs has been considered, and if the use case was generalized to work also for a negative lhs, the code wouldn't work as intended unless % is replaced with a "true modulo" operation.

  • I've had to write a true mod function enough times across different projects (circular buffer indexing, angular arithmetic, periodic boundary conditions, subdivision of coordinate grids in games or graphics apps, etc.) that I would absolutely support its inclusion in the Standard Library.

I also think that this thread has arrived at some important conclusions (especially the ones quoted above), so it seems better to continue this discussion here rather than in a new thread. And there might be one more thing that needs to be sorted out before a proposal:

@scanon: According to this Wikipedia article, especially the top right diagram, the requested remainder seems to be the one of a euclidean rather than floored division.

Also, from the related recent post I mentioned above:

Could you please clarify, to make sure we have the correct background for a potential proposal, is it floored or euclidean?

3 Likes

You've requested a different operation than @Adam_Nemecek. He described a floored division ("This operator, unlike normal modulo, takes sign from the divisor") and you've described a Euclidean division ("I'e never actually wanted a negative return value").The former is more common among languages.

1 Like

Sorry for the confusion and thanks for making me realize it was there.

To be clear, I did mean to describe the same operator that @Adam_Nemecek describes:

Which is the % operator of eg Python:

 7 %  3 ==  1
-7 %  3 ==  2
 7 % -3 == -2
-7 % -3 == -2

Here's the % operator of Swift (and eg C) for reference:

 7 %  3 ==  1
-7 %  3 == -1
 7 % -3 ==  1
-7 % -3 == -1

I frequently find myself needing it (ie Python's % operator) in use cases where the dividend (lhs) can be negative, but I've never had a use case where the divisor (rhs) can be negative, meaning I don't care much about negative divisors (rhs), and thus negative remainders (results). That's why I wrote "I’ve never actually wanted a negative return value from %", which I now realize is confusing.

Now, it might be that @Nevin describes a different operator, I'm not sure but he might have just made the same accidentally confusing statement as I did, and if so, he might also be describing Pythons %.

However, I am sure that both @Adam_Nemecek and I mean the operator that is Python's %, ie the one where the sign of the remainder (result) is always the same as the sign of the divisor (rhs).

So I guess my question can be simplified to:
What kind of division and remainder are implied by Python's % operator?

EDIT: I now realized that I misinterpreted the diagram of the Wikipedia article. I now see that the requested operation is the remainder of a floored division, just like @scanon said ... Again, sorry for the confusion. It would still be interesting to know if @Nevin also meant to describe this operation.

It is the floor division, as documented:

The floor division and modulo operators are connected by the following identity: x == (x//y)*y + (x%y)

Btw, this thread is titled “Double modulo operator” but we probably want a version for integers as well. All the above given use cases (such as cyclic indices) are about integers, not about floating point numbers.

1 Like

Lol what a blast from the past. However in the meantime, I've become even more convinced about the usefulness of this operator. A lot of my programming these days is some group related stuff and this comes in handy. I believe that ideally this operator would always return a positive number.

5 Likes

I wouldn't mind completely replacing current %... I never needed its behavior, and it's always a little bit awkward when "true" modulus is needed.
On the other hand, I don't think there is an established operator, so just adding a small function would be great:

let three: Int = 11.mod(4) // 3
three == (-1).mod(4) // true
2 Likes

isn’t the one that rounds toward zero faster in hardware?

Rounding? We aren't talking about modulo for Double, are we? ;-)

Probably, there is some hardware where mod is slower than % - but where's the benefit of hardware acceleration when it doesn't compute what the software needs?

All I can say is that I need mod (which is missing) occasionally, but never used % (which is available) for anything but creating mod on my own.

1 Like

We should not be designing standard library interfaces around what's fastest to do in hardware. This is what C did (if we read "in hardware" as "on a Digital PDP" for some older features and possibly "on x86" for some more recent things), and we're all worse off for it.

We should ensure that it is possible to take advantage of hardware fast paths where appropriate, and that we have a sound rationale when we diverge from common practice, but the design goal for the standard library cannot be "map as closely as possible to the x86 or arm ISA"; assembly language will always be better at that.

Replacing % is a non-starter for me because:

  1. % is not a modulo operator. It is a remainder operator, directly tied to /. We're not going to change the behavior of /, so we won't change % either.
  2. The current behavior of % matches the overwhelming majority of programming languages. Changing it to do something else would completely violate the principle of least surprise, and there's no argument in favor of changing it that clears the necessary bar.

Adding a .mod or .modulo together with more general divide and remainder operations with rounding control is a complete no-brainer to me. Of course we should do that, and I'm planning to write an actual proposal in the next few days, which I will post here for feedback and contributions from anyone who feels like helping.

10 Likes

maybe a tangent, but is there a way to implement it without branching?

Yes, it can be implemented branch-free, but it’s important to note that branches are not bad—poorly predicted branches are. The branch in the naive implementation is one that is almost always predicted correctly in real use.

I think making % euclidean would be a worthwhile change. I'd almost suggest &% as a name for the current operator, but that might be difficult to read.

In any case, we'd probably want the current version of division and remainder to still be exposed as methods, because I'm sure there are some low level algorithms that rely on it.

As a sidenote, that C# article distinguishing modulo and remainder is describing a purely technical definition created to deal with the fact that little to no hardware has ever implemented a euclidean signed integer division instruction. Mathematically, they both give the euclidean remainder.

I think making % euclidean would be a worthwhile change.

Why? Be very specific. This would break existing code, and would move Swift away from ... basically every other semi-mainstream language. If you made this change only for the % operator and didn't also change the behavior of /, you'd be moving it even further away from common usage. Because of this the barrier to such a change is huge, so you need to be very precise to argue for it.

In particular:

  • Why is it justified to break all existing code that uses % instead of introducing a new function or operator?
  • Why should we choose euclidean division instead of flooring for the remainder?
  • Would / also change? If not, how would you document that / and % no longer form a matched pair?
  • Why not use an unambiguous and more mathematical name, like mod?
  • Show us code examples that the change would make easier to write.
  • Show us the worst-cases for how existing correct code would need to be re-written to account for such a change.
  • Show us how users would be guided to adapt their code across a change like this.

The bar for a change like this is so high that it's extraordinarily unlikely it would happen, but these are the types of questions that you need to answer if you want to push for such a thing.

3 Likes

While this is an important thing to consider, it is a bit of an exaggeration. I'm sure that this change wouldn't break all existing code that uses %. I'd bet a large portion of the code using % is designed to only be used with positive numbers and so they technically wouldn't be broken by this change.

Other than that though, I do agree that the current implementation of % will most likely never be changed, but that a .mod or .modulo function would be a worthwhile inclusion. I do like the %% spelling, but I'm not attached to needing an operator for it.

Very few people write a / or a % into there code with the intention of performing a truncated division, or even the understanding of what answer it will produce when given negative numbers. Euclidean division is division as a human would do it, and it gives what most people would expect the result to be if they actually considered negative numbers, which most people don't. Most people are only peripherally aware that negative numbers exist at all.

Obviously, / would have to change alongside %. Making the two inconsistent with each other would be awful to work with.

Floored division only produces regular remainders when the divisor is positive, which, admittedly, is usually easier to control than the dividend. When given a negative divisor it has the same problems as truncated division.

With positive divisor:

Truncating Floored Euclidean
-4 % 4 0 0 0
-3 % 4 -3 1 1
-2 % 4 -2 2 2
-1 % 4 -1 3 3
0 % 4 0 0 0
1 % 4 1 1 1
2 % 4 2 2 2
3 % 4 3 3 3
4 % 4 0 0 0

With neagative divisor:

Truncating Floored Euclidean
-4 % -4 0 0 0
-3 % -4 -3 -3 1
-2 % -4 -2 -2 2
-1 % -4 -1 -1 3
0 % -4 0 0 0
1 % -4 1 -3 1
2 % -4 2 -2 2
3 % -4 3 -1 3
4 % -4 0 0 0

The worst case is that the code that actually wanted a truncated division, would have to use either use "do it like C does" &% or &/ operators (assuming those names pass muster), or use named methods: truncatedDivision(by:), truncatedRemainder(dividingBy:), etc.

You could also have a property on a SignedInteger & BinaryInteger that converts its value into a wrapper that implements the kind of division you want; e.g. let x = y.truncated % 5, but that's probably too magical.

The people who do care what kind of division they use are also largely the kind of people that read documentation, so the only hard part of the transition would be letting them know that the documentation had changed. We wouldn't really want to put warnings everywhere, because most people don't need truncated division.

Having said that, it may well be too source breaking to actually replace the default division operators, but I personally feel that making division truncated by default was a mistake even when previous programming languages did it, and merely considering using euclidean division would be a huge improvement when most languages pretend that floored and truncated are the only possible options.