Proposal: New operator %% for canonical Modulus operations

[aaronfranke]

Note: The title may be slightly confusing without a definition of canonical Modulus. The idea is for a %% b to be on the range [0, b), so a %% 3 would be on the range [0, 3), and a %% -3 would be on the range [0, -3). As usual, the pattern holds that as a increases, so does the output. The behavior is identical to % when both numbers are positive.

Currently, C# has the operator % for the Remainder operation. This is different from the canonical Modulus when it comes to negative numbers (like the % operator in Python). For example, -5 % 8 is -5 with the Remainder operation but it is 3 with the Modulus operation (proposed syntax: -5 %% 8 returns 3).

• Modulus always returns between 0 (inclusive) and the second argument (exclusive). Yes, this means that it should keep the sign of the second argument. a %% 8 is on range [0, 8)

• By contrast, Remainder can return between the negative second argument (exclusive) and the second argument (again, exclusive). a % 8 is on range (-8, 8)

With a % b the current behavior is like this:

Input a                        -5  -4  -3  -2  -1   0   1   2   3   4   5
Output for b = 3 or b = -3     -2  -1   0  -2  -1   0   1   2   0   1   2

What should ideally be a consistent pattern is broken at 0, so it isn't very useful if you need both positive and negative numbers.

With a %% b the proposed behavior would be like this:

Input a                        -5  -4  -3  -2  -1   0   1   2   3   4   5
Output for b = 3                1   2   0   1   2   0   1   2   0   1   2
Output for b = -3              -2  -1   0  -2  -1   0  -2  -1   0  -2  -1

Currently, I implement Modulus on top of Remainder in my program like this:

public static float Mod(float a, float b)
{
    float c = a % b;
    if ((c < 0 && b > 0) || (c > 0 && b < 0))
    {
        c += b;
    }
    return c;
}

A new operator, %%, would serve the following purposes:

• Easily allow the writing of true canonical Modulus operations, rather than Remainder operations. I can imagine more use cases for this.

• As @quinmars noted, the compiler itself performs optimizations to change % to bitwise when it is passed uint types. Therefore, the compiler could also improve the performance of the %% true Modulus operation, when given int types rather than uint (int is much more common than uint), and the second argument is a power-of-two, by making it bitwise.

• Make developers aware of the issue and endorse the correct usage. To quote @vladd:

Having only the wrong operator in the language means that the people will tend to choose it over some cryptic library function for their implementation, and will have bugs in their code. Having both operators will make people aware of the problem. So the advantage in bringing the alternate operator to the language is to promote better coding without sacrificing the C legacy.

A few use cases from the replies below:

• Indexes in arrays, tables, bucket hash tables, circular buffers, and ring buffers.

• Finding sub-positions in a grid coordinate system.

• Working with angles.

• Working with dates and times.

[TheUnlocked]

I like the idea of a true modulo operator. I'm not sure %% is the right operator for this task (the doubled remainder symbol could imply that it's a logical operator, like with & and && or | and ||), but some operator should be made to do this.

[Joe4evr]

The title of this proposal doesn't make any sense. The entire point of the modulo operation is to get the remainder that is produced from long-dividing two numbers, so there is no such thing as "true modulo" that isn't obtaining that remainder.

This is different from the Modulus when it comes to negative numbers.

According to Wikipedia, there is no rigid mathematical specification of how modulo should work with negative numbers.

When either a or n is negative, the naive definition breaks down and programming languages differ in how these values are defined.

[aaronfranke]

Let me be specific then: I want a Modulus operator which returns between 0 (incl) and divisor (excl).

Also, Microsoft's own definition of the % is "Remainder" not "Modulus" in their C# docs.

[Joe4evr]

I want a Modulus operator which returns between 0 (incl) and divisor (excl).

Then call Math.Abs() on the result. If you look at the table on the Wikipedia article, the result in C# is defined as having the same sign as the Dividend (left-hand argument).

[mikedn]

I want a Modulus operator which returns between 0 (incl) and divisor (excl).

And you want this operation for what exactly? What is this is the mathematical meaning of this operation? What code is a %% b supposed to generate?

[aaronfranke]

@Joe4evr That does not do what I want, at all. The output value should loop around the bounds. -1 % 5 is 4 with a true Modulus, -1 with Remainder, and 1 with Remainder + Math.Abs().

As I've already stated the work-around is to add the second value if the result is negative. But this is not trivial (well, not as trivial as an operator), and there are compiler optimizations only possible with a true Modulus operation.

[aaronfranke]

Example use case: Let's say you divide a coordinate system into pieces of 100. If you are at position 5, you are at subposition 5 of piece 0. If you are at 230, you are at subposition 30 of piece 2. If you are at position -20, you are at subposition 80 of piece -1.

The reason you're not at subposition -20 or 20 is because the subpositions should always be positive AND increasing when position is increasing. If we were at subposition -20 of piece 0 then piece 0 would be two times as large as any other piece.

I am sure there are many, many more uses for Modulus, but this is what I have in mind.

[mikedn]

I am sure there are many, many more uses for Modulus, but this is what I have in mind.

Are there really so many uses do justify adding a new operator? What's wrong with adding a Mod method to System.Math?

[aaronfranke]

Of course that's up for debate, but I would argue that a new operator is a good idea.

I would also support adding a Mod method to System.Math (if we can't get the operator for whatever reason).

[aaronfranke]

I changed the title to better reflect the issue, but technically it's wrong.

• If the divisor (2nd arg) is positive, the result of my definition of "true Modulus" should be non-negative.

• If the divisor (2nd arg) is negative, the result of my definition of "true Modulus" should be non-positive (as it should loop the other way around).

I couldn't fit all this into a short title, but hopefully it gets the point across.

[mikedn]

A programmer may write a % b but someone reviewing the code may not be sure if they wanted a Modulus and never tested negative numbers, or if they did indeed want a Remainder. A method such as Math.Rem would be unambiguous. So too would be Math.Mod and%% (hard to write two % by accident)

It probably makes more sense to do what Java does - add FloorDiv and FloorRem to System.Math, especially if you consider your own example with the coordinate system.

[jnm2]

@aaronfranke I'm afraid the terminology you're using doesn't seem to be ideal. If people search the term ‘modulus,’ they'll discover that it's a synonym for ‘absolute value.’
Since we're talking about modular arithmetic, the term I've always heard is ‘modulo.’ It seems like the less ambiguous term would be better. (FloorRem is also quite a communicative name.)

Also, specifically, you're looking for the Euclidean variant of the modulo operation. (Or possibly the floored division variant? Can't tell.) C# already has the truncated division variant.

[Joe4evr]

It turns out Eric Lippert blogged about this exact thing back in 2011.

[aaronfranke]

@jnm2 I want what Eric Lippert calls "Canonical Modulus". I don't care if Modulus has conflicting definitions in the mathematical world (nobody in programming calls absolute value as "modulus"). I just want a math operator.

[CyrusNajmabadi]

I don't care if Modulus has conflicting definitions in the mathematical world. I just want a math operator.

Can you not just provide that operator in a library? Why does hte language need first class support for it?

[quinmars]

I find it unfortunately that % means remainder. % canonically means modulus and this leads to confusion.

Actually, % used to mean "divide by 100". Many programming languages use it, however, for the remainder operation and very few for modulus.

[cheong00]

Yup. And when seeing %% I tend to interpret it as "thousandth". % is common in programming languages so I have little problem to see it as "reminder" operator, but %% is not.

Agreed it's nice to have canonical modulus operator, but not quite sure whether %% is the right choice.

[aaronfranke]

@quinmars % is not ÷ EDIT: Sorry, completely missed the "by 100" part.

[quinmars]

@aaronfranke, correct. % is the "per cent" sign.

[JansthcirlU]

I think @aaronfranke and @kshetline have both articulated the issues with the existing implementation of % very clearly. In this very thread, I pretty much only see people commenting use cases where the proposed %% would be superior to %, but I yet have to see a single concrete use case where the inferior implementation of % is remotely better than the proposed %%.

%% does what % does, and more

As Eric Lippert explains in his blog post, both % and the canonical modulo as he calls it serve the same mathematical purpose, which is to filter integers into equivalence classes that satisfy divisibility by some non-zero number. And they both accomplish this goal, as you will find that both schools of thought yield the same equivalence classes.

However, while you can use both % and %% to the same end, the result produced by % is utterly useless half the time but the result produced by %% would never be useless. Again, plenty of people are presenting use cases where %% would save them a lot of trouble, but I yet have to see anyone provide a use case where a negative remainder is more useful than a positive remainder. It wouldn't make a difference to devs who never work with negative numbers, but it would save a lot of trouble for anyone who does.

%% is more intuitive than %

On another note, I personally disagree with one of Eric Lippert's comments in his blog. He argues that the magnitude of A / B should be the same as the magnitude of -A / B because it would be "bizarre" otherwise, in other words the integral part of a division should be symmetric around 0. But there's no real justification for why integer division should be symmetric around 0, it's perfectly okay if it isn't.

Although defining the remainder to be positive, as is the case for Euclidean division, is just as arbitrary a choice as making integer division symmetric around 0, the implications are different. And I would argue that the constraints proposed for Euclidean division are actually more intuitive and realistic than the ones described by Eric, even when using negative numbers.

The constraints for Euclidean division when dividing some integer a by some non-zero integer b:

• The quotient q is an integer such that q × b <= a and a - q × b < b
• The remainder r is the amount that q × b is short of a

Let's say I own 257 USD and I want my money in 10 USD bank notes. I could go to an ATM and withdraw 10 USD at a time until I can't withdraw 10 USD anymore (or until I'm out of money). For a total of 257 USD, I will be able to withdraw 25 notes until the ATM tells me I can't withdraw another 10 USD note because I only have 7 USD left. Therefore, q = 25 and r = 7 USD.

What about negative numbers? Let's say I owe you 257 USD and I pay you back using 10 USD bank notes. I could give you 25 notes, but I wouldn't have paid off my debt. Instead, I would have to give you 26 notes and you would pay me back the 3 USD that I didn't owe you. Therefore, q = -26 and r = 3 USD.

Positive remainders all the way.

Final thoughts

The proposed %% is superior to % in every conceivable way, so it should have a proper operator. It would just be a huge game changer for anyone who works with numbers on a regular basis. I also understand that the archaic % cannot and will not be removed, but clearly that's not what this thread is about. It's about adding an actually useful operator to the language, not about changing an existing one.

[tannergooding]

Regardless of the argument around whether Remainder or Modulus is better, many languages support Remainder because that is what the hardware supports and what is most easily implemented in software for hardware that doesn't.

Adding new features to the language is not "trivial" and comes with a cost. Generally proposals start at -100 points and need significant proof that such functionality is worth investing in and maintaining: https://docs.microsoft.com/en-us/archive/blogs/ericgu/minus-100-points

An easy way to show proof that this is worth the cost is to start by adding the functionality to the core libraries. This will require someone to open an API proposal (https://github.com/dotnet/runtime/issues/new?assignees=&labels=api-suggestion&template=02_api_proposal.md) at which point it will get tagged as area-System.Numerics and I'll be responsible for taking it to API review and getting it approved.

This, or even a 3rd party library, would allow telemetry to be gathered on "how many users actually need this" and if it gets enough usage that can be used as an argument for why the language should directly support it as well.

[tannergooding]

@cheong00, the framework team doesn't explicitly follow the -100 points concept.

Instead, the framework is split into areas and each area is owned by ~2 people. For example, I am one of the owners for System.Buffers, System.Numerics (which includes System.Math and types like System.Single), System.Numerics.Tensors, System.Runtime, System.Runtime.Intrinsics, and System.Text.RegularExpressions

The area owners are responsible for reviewing any proposals to their area and deciding if they are worth taking to API review. Those that do go to API review typically get approved, often with some feedback/adjustments.

As one of the System.Numerics area owners, I've indicated I am willing to "champion" a framework API for the Modulo operation as is being discussed here. My only request is that someone else take the time to fill in the API proposal template.

It likely won't get reviewed for .NET 6 given our current backlog of issues, but this is something that should get reviewed for the .NET 7 timeframe (based on how we frequently empty the backlog of issues to review between releases), at which point it would be marked up-for-grabs and anyone can implement it (which should be relatively easy given its a standalone API).

[cheong00]

@tannergooding Thank you for clarifying the process.

[aaronfranke]

With the "-100 points" concept. It's easy to show that the problem is very common, there are StackOverflow posts with hundreds of upvotes (this one has 100k views). Do you specifically want this proposal to get 100 👍 on it to show that it's desired? Note that I see you have given other things that we can do such as filling out the API proposal template (the link seems to be dead though, it just leads to a blank issue), but I am not sure if this can be done without first getting past the -100 points bar.

[CyrusNajmabadi]

Basically, we're at the same place this started at. No one currently thinks of this as important enough to need in the language. A library approach seems great to me. I recommend potentially following the path that Tanner laid out here: #4744 (reply in thread)

[theunrepentantgeek]

@aaronfranke, I can't tell if you're being sarcastic or not. In case you're being literal, it's worth noting the -100 points idea is a metaphor to illustrate that any change must have a great deal of benefit just to be considered. It's nothing to do with counting upvotes, whether here on GitHub or on StackOverflow, or anywhere else.

[michaelcheers]

To me it seems like this should be added as a method like int.Modulo instead of a %% operator which could be confusing.

But yes, I definitely think we need an int.Modulo method.

[mattwar]

% operator is inherited from C. C's % operator is also remainder, because it is the natural side effect of the division operation in the CPU. Maybe C# should have been ground breaking and fixed this in version 1.0. But then again, enums.

Still a Modulo function would be nice.

[aaronfranke]

That doesn't look like two usages, it looks like two methods where projects have to implement their own version. Unless each of those methods is only used once, that would be a lot more than two usages. There are also cases where % is used that could be optimized if %% was used instead (such as changing %% 16 into & 15) although this is more difficult to quantify how common it is. Plus it would be fairly commonly used outside of the BCL. So it's really not esoteric.

[tannergooding]

So it's really not esoteric.

Its still overall esoteric and not exactly standard compared to what most languages (or even standard libraries) expose/support.

That doesn't mean we couldn't expose something or expose some BCL method if there is enough ask. But I do think it adds weight to why the language shouldn't add "first class support".

[aaronfranke]

https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages

CoffeeScript and R already have %% with the behavior proposed here (Floored). Python, Lua, Crystal, Perl, Raku, Ruby, and Solidity have % with the proposed %% behavior. There are 50 other languages on that list with methods for this behavior. There is also Dart with % and 10 others with methods having the similar Euclidean behavior.

However, most languages not having a feature shouldn't be a reason for C# to not add the feature. As evidenced by the reactions and replies to this post, this is very much desired by users to have in C#. The features in C# should cater to C# users. For example, the %% behavior is commonly needed in video games, and C# is often used for video games.

Plus the hundreds of thousands of views on StackOverflow questions on this topic show this is an extremely common problem throughout computing. It's not "overall esoteric".

[BenMcLean]

Two usages in the whole of the BCL isn't really an argument for adding it, my opinion is that it helps shows practically the opposite.

No, the fact that some guy easily found two doesn't imply that there are only two to find. It just means some guy easily found two.

[CyrusNajmabadi]

I don't even see why this is relevant. there are likely lots of patterns found around the place. That argues for a lib function to be provided potentially (either in BCL or some nuget). I'm not seeing the case for this being in the lang. I'd actually rather have this be a lib function that clearly specifies what it does and calls out why you're calling it since it has subtle esoteria you need to be aware of.

[BenMcLean]

Also I want to second the idea that just because other languages aren't doing something doesn't mean C# shouldn't. C# has the decimal type which other languages don't and that's a good idea which makes C# better.

[CyrusNajmabadi]

I don't see why this isn't just easily provided and comprehensible with a simple lib method. It feels like a natural fit (along with all the other math ops). And it feels for a niche op that this is ok.

[squeakyneb]

+1 to this

As a developer who's done graphics programming in GLSL and is now porting some LED strip animation code from Python, it's really quite frustrating that not only does my maths no longer work (and hey, % being different is what it is, that ship has sailed) but there's no replacement on-hand. C++ also appears to define % like C#, but at least it brings along std::fmod and std::remainder (ironically, fmod does what C# calls remainder, and remainder does what is being asked for here).

There's a whole bundle of maths that just breaks halfway down the number line when modulo ("remainder") is defined like this, and there's still no standard alternative.

For every other lost soul who ends up in this thread: double positivemod(double x, double y) => ((x % y) + y) % y;

[JansthcirlU]

I've opened an API proposal for this functionality here: dotnet/runtime#65408

All feedback is welcome.

[aaronfranke]

Bump. I still strongly believe this should be a thing. I continue to believe that:

• It's important to have the correct functionality available, so that people don't use % and end up with bugs.
• This functionality is widely used and worth including in .NET in the core C# language.
• This functionality should be included for feature parity with other languages including Python, CoffeeScript, Lua, Crystal, Perl, Ruby, Solidity, and more.
• Having this functionality in .NET allows the compiler to optimize some cases (like replacing %% 16 with & 15).
• An operator is much better than a method since it endorses the correct usage.
• Having "only the wrong operator" (%) in the language is not good.
• The proposed operator (%%) is purposefully similar to % to help with readability and discoverability.

See also the discussion in dotnet/runtime#65408 which proposes a method - but I think this should be an operator.

[CyrusNajmabadi]

I'll champion this.

[CyrusNajmabadi]

Championed issue: #7599

[CyrusNajmabadi]

Closing this out to keep things there.

[kshetline]

Once there were a %% operator, delinters could flag % for replacement by %%, just as they now flag == for replacement by ===, as the current % functionality is seldom what people really want.

…

Having "only the wrong operator" (%) in the language is not good. The proposed operator (%%) is purposefully similar to % to help with readability and discoverability.

[tannergooding]

Which is correct depends on scenario and behavior. Today, % is the logical counterpart to /, which is to say / is truncating division and % is the remainder of truncating division. This works out to wrapping around when the signs of x and y are the same (whether both positive or both negative).

What's being proposed as x %% y here is the remainder of floored division, which works out to wrapping around (modular arithmetic) regardless of whether the signs are the same or they differ.

There then is missing the ability to trivially compute the floored division, which can often be desirable to have alongside %% and for which other subtle bugs can be introduced if you pair remainder of floored division with truncation division.

[CyrusNajmabadi]

this makes me want a language feature less. and would prefer a pair of runtime methods.

[aaronfranke]

A floor division operator would be interesting too. The symbol that comes to mind is // but that is already taken by comments. However, in my opinion that is a separate discussion. I don't think the lack of a floor division operator should impede %%. The %% operator is more commonly needed than floor division, and already has a dedicated operator in many languages.

If anything, the parity of / and % is a great reason to justify why those existing operators should be kept the same, and why %% is the one that's different with it having more characters.

[tannergooding]

The %% operator is more commonly needed than floor division

This statement doesn't make sense to me. Functionally speaking, in order to compute %% you need to compute the floored division. There are some simplifications possible, but it's still ultimately computing the floored division.

Floored division itself is (branch free):

int quo = x / y;

// If the signs of x and y are the same, we get `quo + 0`, otherwise we get `quo - 1`
return quo - (((x ^ y) >>> 31));

The remainder of floored division is then x - (FlooredDivision(x, y) * y), which can be simplified to (branch free):

// Some platforms don't have combined DivRem and so do `x - ((x / y) * y)`, upon which a different simplification is possible
int rem = x % y;

// If the signs of x and y are the same, we get `rem + 0`, otherwise we get `rem + y`
return rem + (((x ^ y)  >>> 31)) * y;

[BenMcLean]

This statement doesn't make sense to me.

I believe the point was that the result of %% is more commonly needed by userland programmers than the result of floored division is, which I believe was an accurate assessment.

[iam3yal]

I don't want to steer the discussion and I know this topic was discussed multiple times but something like infix functions would have been great addition to the language for Math and DSLs then asks for specific operators might have been less common. Sometimes you just want to work with a cleaner syntax like a mod b or b pow n as opposed to a.Mod(b) or Math.Pow(b, n). It might be possible to introduce infix functions into the language on top of the upcoming extensions feature, dunno. :)

[kezzyhko]

This use is really common, considering that issue had to be moved to discussion, and many comments this discussion got. This issue discussed not only here, but it multiple stackoverflow questions, and other forums. It spans multiple areas, as specified in the first post (angles, dates, etc). This feature is being discussed for more than a decade. Each comment against it meets multiple comments for it.

Now for a personal story. In the past few years, I had the same bug due to unexpected behaviour of % operator. I keep coming to this page, remembering the whole conversation here, and writing the same function over and over again. I visited this page at least 3 times (that I remember of), and had to write the same function many more times. I can not comprehend why it is still not added.

[BenMcLean]

The impression I get is that while this proposal has overwhelming (but not unanimous) support from end users, it has no advocates inside Microsoft nor among the actual maintainers of C#: not even to add a function for it to System.Math.

[kezzyhko]

Yep, same here. Also, great point about "overwhelming (but not unanimous) support". Even if 49% would argue for this feature, and 51% would argue that it is not that common, there are still 49% of users that encounter it frequently enough.

[tannergooding]

Its not really "overwhelming" in the scheme of things. There are some vocal users that are passionate about it, but that is not the same thing as being overwhelming support.

System.Math is effectively soft-deprecated and has been for a few years now, since the introduction of Generic Math and the move of existing math APIs onto their respective types. Since that switch, all new math APIs have been exposed on the respective types rather than on Math, so you do things like int.DivRem or int.LeadingZeroCount now (same with float.Sin, Half, byte, long, ulong, nint, Int128, etc).

For the BCL, I had championed and got approved adding the full set of common division and remainder modes: dotnet/runtime#93568. That has an open PR, but it is lower priority and hasn't been completed/merged yet.

As per the discussion above, adding it to the language has a lot of cons and there is a lot of downsides and other confusion as part of it. Other languages, including new ones like Rust, have typically opted to only expose 1 division/remainder operator and to expose named methods for other functionality, so C#/.NET is really no different with that regard.

Likewise as per the discussion above, there is a lot of general misinformation around what "modulus" means, what "remainder" means, what the general behaviors are, and what users actually expect. Just like % (remainder of truncated division) behaves as they expect for positive % positive but not for negative % positive. There are many cases where the requested operator "remainder of floored division" behaves as expected for positive op positive and negative op positive, but not necessarily for positive op negative or negative op negative and where they actually (but not always) want remainder of Euclidean division instead (which is why Euclidean division is also common in various languages). This confusion and need for other modes further pushes against the language building in some new operator.

[BenMcLean]

OK, for me personally the thing I'd be passionate about is not having to roll my own method to get the desired behavior and being able to express it in a standardized, non-confusing, easy-to-read and computationally efficient way. It looks like your proposal would do that, so even though I still think having it be an actual operator would make the code look nicer, at least the underlying need is going to be addressed if your proposal gets implemented.

[kezzyhko]

@tannergooding Thanks for extensive answer. I think it does a better job explaining your position why it should not be added. It is not "two options and one is missing". Now I agree that adding a whole new operatior for this might be an overkill. The changes you proposed would cover more use cases, including mine. Thanks!