Proposal: New operator %% for canonical Modulus operations

[CyrusNajmabadi]

Discussed in https://github.com/dotnet/csharplang/discussions/4744

^{Originally posted by **aaronfranke** March 22, 2018} *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.

Design Meetings

• https://github.com/dotnet/csharplang/blob/main/meetings/2023/LDM-2023-10-16.md#new-operator--for-canonical-modulus-operations

[BenMcLean]

Info about this in other languages: https://en.wikipedia.org/wiki/Modulo#In_programming_languages

[rickbrew]

This would also be useful when working with HSV/HSL color values. The hue coordinate system loops back on itself, so you often need (hue %% 360.0), which is just a pain to deal with if you only have %. The value can definitely be negative for all sorts of reasons.

[hamarb123]

I, for one, really like this proposal and am looking forward to it being added. I can't even think of even a single instance where I've wanted the behaviour of % as opposed to that of %% (edit: what I mean by this is that I want the behaviour of %% in every instance I've thought of, but sometimes % can also statically be determined to give the same behaviour in which case it's also obviously fine, and there's performance reasons, etc.).

With the behaviour of floating point 0s, I assume we'd have: ±0.0 % +a == +0.0, ±0.0 % -a == -0.0, ±a % +a == +0.0, ±a % -a == -0.0, i.e., that the sign of the result is always the same as the sign of b (whenever it's not NaN).

[lskyum]

I love this proposal... use it all the time for stuff with geometry and other algorithms. If not as an operator then at least as a method on System.Math. Personally I call it "CircularModulus" to be explicit about the behavior, but I'm sure there is a more correct/descriptive name...

[tannergooding]

I think I made my general stance clear on the other thread. But just going to note that I'm still not a super fan of the %% operator.

That being said, if it is provided, then its corresponding division operator should be considered for parity -and- I strongly believe the BCL needs to define an equivalent API first.

There's also some general misinformation discussed about in a few places. The term modulus is essentially the boundary value at which the wraparound point happens in modular arithmetic. While modulo is the remainder of an operation following division and doesn't specifically describe the sign of the remainder.

Most computer hardware defines x / y as a truncating division, namely because it is cheaper to compute. It then stands to reason that the default remainder operation x % y represents its counterpart and is therefore, in terms of infinitely precise arithmetic, equivalent to x - (trunc(x / y) * y).

You then end up having what's being asked for in this proposal, which is the remainder of a floored division. Which is to say, in terms of infinitely precise arithmetic, equivalent to x - (floor(x / y) * y). That then leaves open the question of "where is the operator supporting floored division"? There then also ends up being a possible question about division/remainder for other rounding modes (ceil or away from zero, for example, as well), but these are less asked for.

Now, with all that, the common terminology passed around for x / y is div, x % y is rem, and what's being asked for here as x %% y is mod. We're likely never going to have a "good" IL name for %% and there are various open questions as to the correct result of an operation named DivMod. For example, is that truncating division + remainder of floored division; or is it floored division + remainder of floored division? So we need to come up with reasonable and unconfusing terminology in the face of this and existing APIs like DivRem and % in IL being op_Modulus.

[charlesroddie]

Modular arithmetic does not "wrap around" at a particular "point" called the modulus. Modular arithmetic modulo n deals with equivalence classes of the form x mod n = { x + kn : k ∈ Z}, so every point is already infinitely "wrapped around".

There is wraparound at particular points in the representation of these equivalence classes, where a number (one element of the equivalence class) is selected to represent the class.

The current x % n is not a good representation of the equivalence class x mod n since it doesn't preserve basic equality, i.e. 1 mod 2 = -1 mod 2 but 1 % 2 != -1 % 2. This is such a basic problem that the word mod or modulo should not be applied to %. The proposed %% is a good representation of mod since it does not have this problem.

[tannergooding]

Modular arithmetic does not "wrap around" at a particular "point" called the modulus

Your wiki link starts it with the exact sentence

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus.

If we are giving wiki links, then there is also Modulo, which goes into details on how there isn't an exact meaning and how there are at least 5 variant definitions depending on which exact type of division you're performing. It touches on how there is the more common meaning from Mathematics, but how programming and other domains have their own definitions which follow the same original theme/intent on the perspective and which conditions those satisfy. -- Computers math is, after all, not the same as real mathematics. Real mathematics operates in what is functionally an infinite domain without many bounds. We have increasingly more involved forms that allow us to rationalize these infinite domains and how to represent them. Computers on the other hand strictly work in the concrete world and where we must represent data using finite storage and process the results given a finite amount of time. Thus, there are many shortcuts, estimates, and additional considerations that come into play and modify the mathematical meaning into something that can fit more practical needs and scenarios.

But, anyways, I was namely intending to give a simplified view without getting into the nitty gritty and largely unimportant details. Throwing around the mathematical formulas and terminology just makes it so that more people can't follow along, particularly if they don't have a background in mathematics, and so I try to avoid it.

C#'s % is a modulo operation which returns the remainder of a truncated division.

What's being asked for in %% is an alternative modulo operation which returns the remainder of a floored division.

People may also need or ask for other types of modulo operations, such as the remainder of a ceiling division or Euclidean division.

[charlesroddie]

The mathematics is not complicated and the average person can understand understands the n=2 case perfectly: namely that there are two possible parities, odd and even, not 3. Anyone who works with modulo arithmetic in any form will know that there are n possible cases: equal to 0 mod n up to n-1 mod n. Not 2n-1 cases.

The link you give on modulo arithmetic, while it does give several definitions, quotes "Division and Modulus for Computer Scientists" as "truncated division is shown to be inferior to the other definitions", exactly what I and others are arguing here, and it gives the desired property I mentioned of picking a representative of an equivalence class, which this definition is the only definition of those given to fail to meet. With the result it is the only definition where you cannot compare the parity of x and y with x % 2 = y % 2, an extremely practical thing to do.

[CyrusNajmabadi]

All this complexity is making me much more wary about taking this into the language itself.

[Richiban]

@CyrusNajmabadi Don't let these people diving into the theory dissuade you, Cyrus. There is a well-defined need for a proper modulo operator that behaves as people would expect for negative operands.

[CyrusNajmabadi]

@Richiban it seems like a library function would be fine here though. Then all the different areas can be covered uniformly and consistently.

[rickbrew]

All this complexity is making me much more wary about taking this into the language itself.

@Richiban it seems like a library function would be fine here though

In a language like C, C++, and C#, I'd expect -- roughly at least -- an operator on a primitive type should map closely to what's supported natively by the CPU. So on x86, / maps to idiv for an int, etc. %% would be many instructions, and might lead people to think it's "not expensive" (at least no more expensive than / or %).

I think a library function makes more sense from that angle.

[BenMcLean]

Is it really true that %% would have to be many instructions? There isn't a CPU instruction for it in any common architectures?

(later edit) I guess that ? isn't a CPU instruction and I'm sure that was loudly opposed by people who like ugly, unnecessarily padded over-verbose code everywhere.

[nuiva]

In a language like C, C++, and C#, I'd expect -- roughly at least -- an operator on a primitive type should map closely to what's supported natively by the CPU. So on x86, / maps to idiv for an int, etc. %% would be many instructions, and might lead people to think it's "not expensive" (at least no more expensive than / or %).

I think a library function makes more sense from that angle.

It should be noted that idiv is an expensive operation despite being native.

A staple compiler optimization is to replace idiv with faster instructions whenever the compiler can prove it's equivalent. This turns out to be faster even if a single operation has to be replaced with multiple. For example, Clang optimizes the C function int f(int x) {return x % 3;} as follows (Godbolt,l:'5',n:'0',o:'C+source+%231',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cclang_trunk,deviceViewOpen:'1',filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'0',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'-O3',overrides:!(),selection:(endColumn:12,endLineNumber:10,positionColumn:1,positionLineNumber:2,selectionStartColumn:12,selectionStartLineNumber:10,startColumn:1,startLineNumber:2),source:1),l:'5',n:'0',o:'+x86-64+clang+(trunk)+(Editor+%231)',t:'0')),k:33.333333333333336,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(compilerName:'x86-64+gcc+13.1',editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+clang+(trunk)+(Compiler+%231)',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)):

        movsxd  rax, edi
        imul    rcx, rax, 1431655766
        mov     rdx, rcx
        shr     rdx, 63
        shr     rcx, 32
        add     ecx, edx
        lea     ecx, [rcx + 2*rcx]
        sub     eax, ecx
        ret

OP suggests that %% could better enable similar optimizations:

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.

In other words, %% could be faster than % in some cases. Whether that's true in practice is beyond me.

[tannergooding]

Is it really true that %% would have to be many instructions?

They basically boil down to the below examples, if you want a branch free implementation. It's not "terribly" more expensive, but it is around 3 additional for floored division and 4 additional for floored remainder, representing about a 25-33% increase compared to the base cost on a modern CPU (it is less of an increase, percentage wise, on older CPUs due to div being significantly more expensive on older processors, sometimes being 10-15x slower than modern CPUs or more).

There are then some optimizations possible if you know that x and y have the same sign or that one input is always positive/negative.

Floored Division

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));

Remainder of Floored Division

// 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;

There isn't a CPU instruction for it in any common architectures?

Not really, no. Remainder isn't exactly a common CPU operation either, with x86/x64 being one of the few architectures that provide a combined instruction. Most platforms expect the compiler to emit the alternative sequence to compute the remainder (x - ((x/ y) * y)).

Truncated Division is the default namely because it is cheaper for CPU hardware to compute, making it the more foundational instruction on which the others can be built.

I guess that ? isn't a CPU instruction and I'm sure that was loudly opposed by people who like ugly, unnecessarily padded over-verbose code everywhere.

If you're referring to cond ? x : y, then it actually is a commonly supported CPU instruction, known as cmov. It's often used to assist in writing branch free algorithms where both x and y are already evaluated and you're simply picking which is the correct -- CPU hardware often implement cmov internally via bit twiddling tricks, as it is functionally (x & cond) | (y & ~cond), assuming that cond is either 0 or ~0 (which represents AllBitsSet).

Some people of course use ternary expressions for other scenarios as well, but that's basically a historical consideration of why it exists and is useful. switch (...) { } likewise historically exists as a way to represent a jump table. And it likewise sometimes gets used for other scenarios as well, because it happens to be a useful way to represent state and data.

---

Rust is notably looking at adding support via APIs as well: div_ceil, div_floor, and div_euclid.

APIs make it easy to see the intent, to provide parity, and many other considerations.

Operators "can" can help with precedence considerations and can provide some additional sense of clarity or conciseness, but the more rare an operator is, the less likely the latter benefits are to exist.

[333fred]

The LDM discussed this today, and has decided to reject this proposal. We think there are too many possible combinations of requests here (other remainder operations, other division operations) to be handled with specific operator syntax. However, @tannergooding has indicated that they will be working on a libraries proposal to add dedicated functions that cover the breadth of the different requests here to the BCL itself, which we believe will better address this proposal and natural follow-on proposals.

[tannergooding]

https://github.com/dotnet/runtime/issues/93568 is the API proposal. It isn't necessarily the "best" way to expose the API surface, but it is the simplest that covers all the various rounding modes that may be interesting.

We can always discuss whether or not explicitly named methods are more desirable in API review and whether we want to support floating-point from the start or not.

[rickbrew]

We can always discuss whether or not explicitly named methods are more desirable in API review and whether we want to support floating-point from the start or not.

I would definitely make use of floating-point support.

[crozone]

So 6 years later, if all goes well in https://github.com/dotnet/runtime/issues/93568, we may be able to call Remainder(left, right, DivisionRounding.Euclidean) in order to get the euclidean modulo?

If Remainder(left, right, DivisionRounding.Euclidean) then starts replacing the % operator everywhere (because again, % behavior is almost always undesired), will the %% operator be back on the table? Maybe 5 years from now I'll be able to write code using euclidean modulo that's actually clean and concise.

[CyrusNajmabadi]

will the %% operator be back on the table?

Probably not. This is in the likely-never milestone. This is just too esoteric to warrant this. If you want an easy infix operator, just define an extension method for this.

[vladd]

@crozone I wonder if there is a single usage in the wild where % couldn’t be replaced by %% because %%’s semantics would be wrong (modulo implementing % operator itself in a calculator or the like). I tried to find it but failed.

[tannergooding]

I wonder if there is a single usage in the wild where % couldn’t be replaced by %% because %%’s semantics would be wrong (modulo implementing % operator itself in a calculator or the like). I tried to find it but failed.

% is the fundamental computation primitive and is what things like %% are fundamentally built on top of, as I detailed in other comments above.

Even with Remainder(left, right, DivisionRounding.Euclidean) a lot of the places users have called out above are scenarios where it's often significantly better to write a minimal constrained algorithm instead that allows the computation to be done much more trivially and which cannot be done implicitly for a general purpose euclidean remainder.

Division (and operations built off of division, such as remainder operations) is one of the most expensive operations computers perform and its one that often needs specialized considerations when being used.

[crozone]

% is the fundamental computation primitive and is what things like %% are fundamentally built on top of, as I detailed in other comments above.

But Remainder is the fundamental computation primitive, % just happens to be remainder because C# copied C. Fundamentally remainder and modulo really are different operations. It certainly seems like when most C# programmers reach for % they are expecting modulo, and are surprised to find remainder, as evidenced by all the stack overflow questions about the differences between remainder and modulo and how different languages implement % as one vs the other. This certainly implies that modulo is an expected fundamental operation.

Even with Remainder(left, right, DivisionRounding.Euclidean) a lot of the places users have called out above are scenarios where it's often significantly better to write a minimal constrained algorithm instead that allows the computation to be done much more trivially and which cannot be done implicitly for a general purpose euclidean remainder.

Isn't this true in general? There are very often ways to optimize any given algorithm. It doesn't change the reality that many programmers are writing algorithms today using % where they expect modulo and get remainder. They expect one behaviour (which is standard in many other languages like Python) and get a different, confusing behaviour, leading to code like this:

// Normalize hue angle
hue %= 360;
if (hue < 0)
{
    // C# % is remainder! Oh the huemanity!
    hue += 360;
}

Or implementing their own mod:

int Mod(int x, int m) {
    int r = x%m;
    return r<0 ? r+m : r;
}

Division (and operations built off of division, such as remainder operations) is one of the most expensive operations computers perform and its one that often needs specialized considerations when being used.

Sure, but / is an operator, % is an operator, I don't see how %% is fundamentally different in terms of considering computational cost. Ultimately if you need a modulo, you have to pay for the modulo, that's true whether it's an operator or not.

In many cases %% often wouldn't need to do division, a significant usecase is simply wrapping around constant powers of two, which is already optimised for % with unsigned ints:

public uint M(uint input) {
   // modulo power of two
    return input % 8;
}

L0000: mov eax, edx
L0002: and eax, 7
L0005: ret

However when using an int input, the compiler needs to output significantly more instructions to satisfy the behaviour of %:

public int M(int input) {
    // modulo of signed value, power of two
    return input % 8;
}

L0000: mov eax, edx
L0002: sar eax, 0x1f
L0005: and eax, 7
L0008: add eax, edx
L000a: and eax, 0xfffffff8
L000d: sub edx, eax
L000f: mov eax, edx
L0011: ret

This is unfortunate because for reasons int is the standard for indicies. Being able to write these with a simple modulo operator is easier and expresses the intent much more clearly than having to generate a bitmask and then bitwise AND the values manually.

In the floating point case, the operation is going to be expensive no matter what, modulo would just save extra mucking about. At least in these cases, Remainder(left, right, DivisionRounding.Euclidean) will certainly be an invaluable improvement over the current status quo.

[CyrusNajmabadi]

Just want to reming people this is:

1. likely never
2. already rejected
3. closed

:)

We've looked at this situation. We do not think a new operator is worth it. If you'd like an infix operator, you cna use an extension method here.

If the runtime changes their minds here, we might consider it. but it doesn't look like they think differently about this either.

[tannergooding]

edit: missed that the conversation was locked while I had been writing up a response, sorry about that

But Remainder is the fundamental computation primitive, % just happens to be remainder because C# copied C.

Which itself copied hardware, which itself considered what the actual fundamental building block on which other kinds of remainder are built on top of to achieve needed perf, simplicity, and other design goals.

Standard division is truncating division as it is the most trivial to implement. Its counterpart is then remainder of truncated division. Thus, languages have historically provided / and % as a logical pair where / means floored division and % means floored remainder. You explicitly want to pair them to ensure overall logical consistency in your algorithms, expected performance, etc.

Some languages opted to deviate, for various reasons, but they also tend to have different goals, domains, perf, and other considerations and in turn have their own problems due to deviating from the far more standard expectations based on hardware and C (the foundations on which everything else is built).

There are very often ways to optimize any given algorithm. It doesn't change the reality that many programmers are writing algorithms today using % where they expect modulo and get remainder. They expect one behaviour (which is standard in many other languages like Python) and get a different, confusing behaviour, leading to code like this:

The inverse is equally arguable. The default in many languages is remainder of truncated division and is prevalent in many just as common if not more common languages (including Bash, C, C++, C#, F#, Go, Java, Javascript, Julia, Kotlin, Objective-C, Php, Swift, Verilog, Zig, etc).

Python itself is one of the outliers being both popular and using a different default from many other ecosystems. Even of other languages that provide support for remainder of floored division, python is an outlier in that its using % for that. Many languages instead explicitly use % to mean what it does in C# and then provide a different operator such as %%, //, or mod to mean remainder of floored division. Some then use rem or mod to mean what it does in C#, but those themselves are fewer and the most prevalent across all languages is that % means remainder of truncated division.

Then you have the case that even in this thread people are confusing the different operations. Some people are claiming they want what Python has and are stating that's remainder of Euclidean division, for example, when Python exposes remainder of floored division instead.

Given that, it's very hard for to understand what people actually want. I can agree that sometimes people have negative values and they expect them to wrap around like positive values do, but how that wrap around happens among other considerations often deviates wildly especially in edge cases (and many people have suggested incorrect optimizations that don't actually do what they want in all edge cases). Additionally, given that many input domains are themselves restricted to positive inputs, % is doing what they actually wanted regardless.

However when using an int input, the compiler needs to output significantly more instructions to satisfy the behaviour of %:

That's not exactly a representative case. When used for things like indexing where negative values are explicitly disallowed, you typically need to do validation that the index is positive. After you've done that validation, the JIT understands the value is restricted to the positive input domain and will just emit and as expected.

---

We could ultimately go around all day back and forth providing arguments and counter arguments.

As Cyrus indicated, this is likely never for the language. I've opted to put forth and get the proposal approved to provide a wider range of options in the BCL and that will provide more utility to places users want different behavior and that will be the direction forward for .NET