'Double modulo' operator

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.

The “Floored” column in your "With negative divisor:" table seems to be wrong, those remainders should be zero or have the same sign as the divisor. Has been fixed.

1 Like

I generated the results using gforth, it's possible that the Forth standard uses a different definition of "floored" integer division than everyone else is using. I'll double check the definitions and try again. Ah, I made a copy paste error. Fixed.

1 Like

This is highly non-obvious at best. By focusing on the remainder, you are sweeping considerable weirdness in the quotient under the rug. For example, "most people" expect that:

  1. (-a)/b == a/(-b) == -(a/b)
  2. (-a)/(-b) == a/b

and perform algebraic simplifications under the belief that these properties hold. Property (1) is satisfied only by unbiased rounding rules for the quotient. So nearest and truncating division satisfy it, but floor, ceiling, and Euclidean division do not. Property (2) is satisfied by any quotient-dominant rule, so everything except for Euclidean division meets it.

All of which is to say that there's no obviously right choice. There are perfectly reasonable arguments in favor of multiple options. Personally, I come down with Knuth (in favor of flooring division), but only very weakly. I can stomach the relatively stable status quo around / and % implementing truncating division, so long as other options are made available.

4 Likes

I agree (that it was a mistake not to include all three variants, and that it's too source breaking to change the semantics of %).

Also, note that changing the behavior of % would also break code for people (like me) who needed the floored or euclidean definition, and rolled their own, perhaps based on Swift's %.


Regarding how people (mis)use Swift's %. The following are some results of a quick search I did to see if I could find any examples of the common pitfall mentioned in the wikipedia article:

1:

let isOdd : (Int) -> Bool = { $0 % 2 == 1 }

This will return false for every negative number.

Found here: Transducers & Reducers in Swift 2 · GitHub


2:

func isOdd(number: Int) -> Bool {
    if number % 2 == 1 {
        return true
    } else {
        return false
    }
}

Same thing but more verbose.

Found here: Chapter 7: Functions - We ❤ Swift


3:

For example, imagine you wanted to compute a sum similar to that of triangle numbers, but only for odd numbers:

let count = 10
var sum = 0
for i in 1...count where i % 2 == 1 {
    sum += i
}

Not strictly wrong since i is in the range 1 ... count, but it must be considered bad practice to not write i % 2 != 0 instead, and it makes it seem like they misunderstand Swift's %.

Found here: Swift Tutorial Part 3: Flow Control | Kodeco


4:

The remainder operator is most useful when checking the parity, or “evenness,” of a number. If we wanted to know if a number x is even, we can use the remainder operator and check if the result is 0 or 1: x % 2 . If that result is 0, then we know that the number is even; if the result is 1, then we know the number is odd.

They recommend a method to check for odd numbers that will not work for negative numbers. If they had known how % worked, they would have wrote: "if the result is not 0, then we know the number is odd".

Found here: https://swiftludus.org/how-to-use-operators-in-swift/


My guess is that the % operator is widely misunderstood and misused (not just in Swift).

Including methods for all three (truncated, floored, euclidean) in the standard library would not only provide us with frequently needed functionality, but also help increase the awareness of their existence and differences.

10 Likes

Why would normal people expect that? Normal people tend to treat algebra as, at best, a chore to start with, and second neither of those hold when you do long division by hand.

No one on a discussion forum for the evolution of a programming language is likely to be a normal person, btw. We're all mad weirdos here.

They both hold for long division as taught in most US public schools. E.g.:

Take note of the signs of the two numbers. If both signs are positive or both are negative, the resulting figure will be positive. If only one of the signs is negative, you will end up with a negative number. As an example, 78 divided by -5 would give you a negative quotient. You can safely ignore the negative sign, as long as you remember the final outcome will be negative.

I'm not familiar with how it's taught outside of the US.

Well, I was homeschooled, so I suppose my understanding of long division is also abnormal.

1 Like

The even odd proposal would really benefit by adding this to its correctness argument I imagine. There's a couple of very popular sources listed here.

1 Like

I made the same mistake for isOdd in the initial version of that post :blush:

5 Likes