Addition of a correct modulus operator

[Happypig375]

Addition of a correct modulus operator

The current remainder operator % can be surprising in that the sign of the result follows the sign of the dividend, so does not output periodic results for a fixed divisor. Changing the current behavior of % has been declined in https://github.com/fsharp/fslang-suggestions/issues/417, so another way forward would be to add a new operator, which, like a true modulus operator, would output positive results regardless of its inputs. By always outputting positive results, we would achieve predictability and ease of use for periodic computations.

From F#'s OCaml roots, mod is keyword for an infix operator already, and is currently undefined in FSharp.Core:

let inline (mod) D d =
    let r = D % d
    if r >= LanguagePrimitives.GenericZero then r
    elif d >= LanguagePrimitives.GenericZero then r + d
    else r - d
// Usage: -5 mod 3

The existing way of approaching this problem in F# is to include such a definition everytime we use the operator, or bite ourselves when trying to use % on negative dividends.

Pros and Cons

The advantages of making this adjustment to F# are

1. Raise awareness of the true modulus operator
2. Less duplicated code across projects
3. Assigning novel uses to existing available operators

The disadvantages of making this adjustment to F# are that the presence of both % and mod can be confusing. However, upon realisation that % stands for the remainder operation instead of modulus, and recognising the difference between the two operations, this can be solved.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): XS

Related suggestions:

• https://github.com/fsharp/fslang-suggestions/issues/417

Affidavit (please submit!)

Please tick this by placing a cross in the box:

• [x] This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
• [x] I have searched both open and closed suggestions on this site and believe this is not a duplicate
• [x] This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

• [x] This is not a breaking change to the F# language design
• [x] I or my company would be willing to help implement and/or test this

For Readers

If you would like to see this issue implemented, please click the :+1: emoji on this issue. These counts are used to generally order the suggestions by engagement.

[TysonMN]

[...] a new operator, which, like a true modulus operator, would output positive results regardless of its inputs.

I think you should be more precise here. "The true modulus operator" returns a quotient group, not an integer (and certainly not a finite percussion int). In a congruence like

3 mod 2 \equiv 1

the symbol 1 does not represent the integer 1 but the set of all odd numbers. It would also be correct to replace it with 3, because it is also an odd number. Using the symbol 1 there instead of something else like 3 is merely convention because it is the canonical representation of the set of odd numbers.

[charlesroddie]

Two uses for integer division (n div m, n mod m):

• Division with remainder. Here the conventional definition in mathematics, for m > 0, is n = mq + r, where 0 ≤ r <m.
• Finding quotient equivalence classes.

The definitions are intentionally compatible: the remainder found in the conventional definition, when applied to different n differing by a multiple of m, gives the same output.

In each case dotnet % is incorrect, for n < 0 and m > 0. E.g. -3 mod 2 should give 1 but gives -1. This contradicts the conventional definition in mathematics, since -1 < 0, and it also doesn't find a quotient equivalence class, since -3 mod 2 = 3 mod 2 evaluates to false instead of true.

[dsyme]

This is reasonable I guess. Marking as approved-in-principle.

[charlesroddie]

Correction in C#: https://github.com/dotnet/csharplang/issues/7599

The disadvantages of making this adjustment to F# are that the presence of both % and mod can be confusing.

We should have an on-by-default warning on the use of %.

[tannergooding]

Correction in C#: https://github.com/dotnet/csharplang/issues/7599

Noting that championed doesn't necessarily mean will happen. It just means the underlying issue garnered enough interest that it's worth taking to the language design team for a preliminary check and may be further considered if it's not outright rejected.

We should have an on-by-default warning on the use of %.

Remainder is still very valid for a number of scenarios, particularly as it comes to performance and foundational algorithms.

Warning for either is likely not correct, you ultimately have cases where each is equally valid to use.

---

"remainder" (% in C#) is the more foundational operator and often has direct hardware support. mod (proposed to be %%) is a higher level concept that is quite a bit more expensive and often does more than required.

Broken apart, remainder x % y is x - (truncate(x / y) * y). While x %% y is functionally ((x % y) + y) % y, or rather x - (floor(x / y) * y).

That being said, regardless of how you want to try to simplify it, the most efficient implementations of %% functionally require "more work". On hardware with a combined DivRem, you'll want to use % as part of the computation. On hardware without, you can skip the subtraction step rather than computing the "true" remainder, but are still stuck functionally having done the division + remainder calculation and then using a couple bit-twiddling tricks to avoid the branch.

[charlesroddie]

I would suggest the following warning: Use of % does not represent the mathematical modulus operator and may return negative numbers for positive divisors. If your intention is to use modulus, usemod, and if your intention is to use the remainder result given by %, then use System.Math.Divrem.

"If your intention is to model modulus" would be a little more accurate but users might not understand that.

On reflection off by default would be better:

• There is already an off-by-default warning approved for integer division (largely unrelated to modulus).
• An off by default warning would be easier to get approved and add to F#.
• Since the % symbol is obscure, new users won't naturally think about using it without looking it up, and we can put the dangers of using this in documentation (both xml and a webpage).
• We could also improve the list of off by default warnings and on by default warnings by adding reasons why one might turn them on or off. That would make it more likely that users select a sensible combination of warnings. I could have a go at that.

Remainder is still very valid for a number of scenarios, particularly as it comes to performance and foundational algorithms.

This is true but this these scenarios are very limited and require extra understanding and care (e.g. of the signs of the inputs), so this functionality should be available but not as a single-character operator whose xml documentation describes it as modulo. Users would not use access to this and the niche where this is correct and useful would still be served and can even be included in the warning message as above (or with some other renamed function). Code that uses it intentionally should be more explicit and unintentional use should be minimized.

[tannergooding]

This is true but this these scenarios are very limited and require extra understanding and care (e.g. of the signs of the inputs), so this functionality should be available but not as a single-character operator whose xml documentation describes it as modulo.

I think this really depends. Technically speaking the terms modulo and modulus don't specifically mean the behavior being described here.

The modulus is simply the boundary value at which the wraparound point happens in modular arithmetic. Where-as Modulo is the remainder of an operation following division and does not specifically describe the sign of that remainder.

The remainder then depends on which rounding direction is chosen by default. Computer hardware defaults to a truncating division, which is to say x / y will is equivalent in real math to trunc(x / y). Thus, it's equivalent remainder x % y is equivalent in real math to x - (trunc(x / y) * y). This exists because truncating division is significantly cheaper to compute.

Where-as what's being asked for here is the remainder of a floored division, which is equivalent in real math to x - (floor(x / y) * y). That then leaves an open question of, "where is the operator representing floored division"?

From my view, a language can rightfully decide that either "floored" or "truncating" division is correct for them. However, the default remainder operation should then provide the logical parity of that operation. A language can then decide to also expose the other division operation, but likewise should then provide the an equivalent remainder operation for parity. The same would be true if a ceiling based division were to be provided.

I believe that mixing things such that x / y is truncating division, but x % y is floored remainder, is ultimately worse.

[charlesroddie]

"modular arithmetic" is equivalence-class based and as such, modulo 2, [1] = [-1]. This is correctly described in https://en.wikipedia.org/wiki/Modular_arithmetic . In order to represent this in computer arithmetic we need to choose consistently to maintain equality. You cannot represent the equivalence class [1] as 1 sometimes and as -1 sometimes, since 1 != -1. That's the (huge) problem with "truncating remainder": 1 mod 2 != -1 mod 2 when using that representation.

"Remaindered division" is a minor aspect of this. There is no discussion of remaindered division in this issue and there doesn't need to be, as long as users can choose the right one when they need to. There is an issue about division of integers but that issue is about / not representing true division when applied to integers (multiplication by multiplicative inverse) and therefore being dangerous and this issue is about % not conforming to modular equivalence and therefore being dangerous.

[tannergooding]

That's why there are multiple terms, including modular, modulus, and modulo.

The remainder of floored division is what's being asked for here and meets the needs for modular arithmetic regardless of the signs of the numerator/denominator. Where-as the remainder of truncated division only meets the needs for modular arithmetic when the signs of the numerator/denominator match.

modulus itself is effectively the point at which the values wrap around. Or rather, to quote the page you linked

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

https://en.wikipedia.org/wiki/Modulo gets into what the modulo operation is, what it means for mathematics, and how in the computer programming world it has several variable but all equally valid definitions, one of which is the remainder of truncated division and matches what % does.

None of this makes it dangerous or incorrect. It simply makes it the pair to the default division operation that most hardware and most computer programming languages provide by default.

That may be incorrect for some usage scenarios, but the same would be true for if the default was floored division and its remainder.