In algebra, mod is not an operator. We say 17 mod 4 is 1, but what we write is something like
17 = 1 (mod 4)
To say that 17 and 1 have the same remainder when divided by 4. If you do all of your operations and comparisons mod 4, it doesn't matter if we call the number 1 or -3.
In real life, we often need the remainder function, and we usually need it with positive numbers (how many eggs will I have left if I put these into boxes of 12). We sometimes call this the modulo function, which is a slight abuse of notation from the algebraic meaning of modulo. For positive numbers, it works completely intuitively. There are a couple of natural ways to extend this to negative numbers - an extension which would be meaningless or irrelevant in algebra - and computer language authors have (usually) called one rem and one mod.
The standard way of constructing modular arithmetic in "upper level" [0] is to define it over equivalence classes. For instance, let a ~ b mod 4 be the expected equivalence relationship for mod-4 arithmetic.
Then, define [x] = {a | a~x} to be the set of all numbers which are congruent to x mod 4.
At this point, we define [x]+[y] = [x+y] (along with the other arithmetic operations which are defined similarly). Then, there is just a bit of work to prove that the above definition is actually well defined (since the representative element we pick from both of the [x] and [y] sets is arbitrary, we must show that [x+y] is the same set regardless of which x and y we choose).
This means that, when we write 17 = 1 (mod 4), we are really saying [17]_4 = [1]_4; where [x]_n is the mod-n equivalence class containing x. The equal sign is literal, the numbers are not.
This type of implicit injection is actually fairly common in algebra. It is how we can view, for example, 17 as a natural number, real number, complex number, and polynomial without explicitly mapping it each time.
[0] Eg. an introductory undergrad course in abstract algebra.
I don't think that is quite true. Yes, for normal intergers 17 and 4, you can say the above. But mod can also be used as an operation on (and into) the equivalence classes of Z mod 4.
For this reason, Zig requires the programmer to specify which is intended when the operator is used on signed integers:
var x: i32 = -17 % 12; //compile error: remainder division with '(integer literal)' and '(integer literal)': signed integers and floats must use @rem or @mod
var y: i32 = @mod(-17, 12); //7
var z: i32 = @rem(-17, 12); //-5
Correct me if I'm wrong, but this is also attractive because it can be applied even to an "actual modulo" operator. That is, because "(x mod n + n) mod n" has the same behavior as the above, one need not even know which way a particular language's "%" operator behaves if one just always uses this filter.
a = b ( mod n) is defined as
n | a - b
That is n is a divisor of a -b
( a, b, n integers n non zero)
Obviously if p is prime and p | n
Then also a = b ( mod p)
I know. But programming languages usually don’t have the modulo relation but a modulo operator that sends each number to a special representative of its equivalence class. For positive numbers, everyone agrees that this should be the smallest nonnegative number (i.e. the representative between 0 and n – 1). However, there are two conventions for the representative of a negative number: Some programming languages return the largest nonpositive number (the article calls this the remainder), others return the smallest nonnegative number in this case as well (the article calls this the modulus). I chose to write mod and rem instead of % to be able to make this distinction.
I recalling seeing these referred to as modp (positive) and mods (symmetric) back in University. This seems to be the clearest way to distinguish them. I didn't realize different popular programming languages used different versions for the % operator...
The case of a negative denominator doesn't seem to make sense when talking about modulo in an algebraic sense. I don't think you can have a Ring with a negative dimension. So I've never even thought about what % would do with a negative denominator (RHS). If I was using % with an unknown denominator as input, I could just as easily end up with it being 0 which would be a bad thing, so I think it's fair to say I always require it to be positive.
No, the symmetric version is yet a third variant. What people are calling “rem” is what you get with division that rounds toward zero, whereas what they are calling “mod” is what you get with division that always rounds down. A symmetric version is what you get with division that rounds to the nearest integer, and I have not seen any language with a built-in operator for it.
To the grandparent:
> sends each number to a special representative of its equivalence class
The problem is that many programming languages have a “remainder” type % operator which does not do this in the case where the dividend is negative. For instance,
-1 % 3 == -1
2 % 3 == 2
Instead, folks who want mathematically reasonable behavior need to implement their own. For instance in Javascript we can define
Grandparent here: I know, that’s what I tried to explain (poorly) with the next sentences. Programming languages with a remainder operator choose two representatives for every equivalence class except [0] and return the one that has the same sign as the dividend.
I tend to define
mod = (a, b) => (a % b + b) % b
because it works without going through floats – in languages that have integer types. I don’t know if there are actual advantages though.
Well, algebraically, Z/nZ and Z/(–n)Z are the same. However, you have again some choice of canonical representative (and you might choose differently for n and –n). But I agree that this is a rather rare case.
I don't think there is a formal universal distinction in programming between a "modulo operator" and a "remainder operator" in terms of behaviour. Wikipedia says that the result of a modulo operation varies between languages [0]. Furthermore, by mathematical convention as seen in the Euclidean division theorem, the remainder is always in [0, n).
The key to this is in how you do integer division. Here is what happens in Python2:
>>> 19 % -12
-5
>>> 19 / -12
-2
That is because Python2 integer division is something called "floored division". This can be seen as always rounding toward negative infinity. This is arguably the correct way to do integer division and in fact there has been a lot of argument about this over the years.
One very nice feature of floored division is that it does not have a weird discontinuity around 0 as "round toward 0" does. This discontinuity can sometimes cause problems in embedded applications involving physical motion.
So mod and remainder are the same. You just have to do the division right...
Oh yes, 100%, but someone had to point it out :) One of my biggest fears is that some of my public stuff has obvious mistakes but nobody tells me out of politeness!
There are actually FOUR possible binary operations, all of which agree when both arguments are positive (e.g. f(13,5)=3 for all of them), and all of which satisfy the property that if f(n,d) = r, then r ≡ n (mod d). Namely:
• The first one always returns a positive number: for this f, when f(n,d) = r, it's true that 0 ≤ r < |d|. For example, f(13,-5)=3, and f(-13,-5)=2. Some programming languages that obey this: ALGOL, Dart, Maple, Pascal, Z3.
• The second one always takes the sign of the divisor (i.e. the denominator, if you write the division as a fraction n/d): for this f, when f(n,d) = r, it's true that |r| < |d|, and that r and d both have the same sign. For example, f(13,-5)=-2, and f(-13,-5)=-3. Some programming languages that follow this: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl.
• The third one always takes the sign of the dividend (i.e. the numerator, if you write the division as a fraction n/d): for this f, when f(n, d) = r, it's true that |r| < |d|, and that r and n both have the same sign. For example f(13,-5)=3, and f(-13,-5)=-3. Some programming languages that follow this: AWK, bash, bc, C99, C++11, C#, D, Eiffel, Erlang, Go, Java, OCaml, PHP, Rust, Scala, Swift, VB, x86 assembly.
• The fourth one takes the sign of the product, i.e. it's positive if both the dividend and divisor have the same sign, and negative otherwise: for this f, when f(n, d) = r, it's true that |r| < |d|, and that r and n*d have the same sign. For example, f(13,-5)=-2, and f(-13,-5)=2. I'm not aware of a programming language that does this, though I've seen some ad-hoc hand-rolled big-integer libraries that used to do this.
Of course in mathematics (number theory) we usually don't care, as, for example, modulo 5 (or -5 for that matter), we would say -13 ≡ -8 ≡ -3 ≡ 2 ≡ 7 ≡ 12... (mod 5), and so we can pick any of them and it doesn't affect the mathematics.
Same here, only in Rust. Felt really rather stupid having managed to write code for 20 years without actually knowing this. Tons of knowledge is built on faulty assumptions.
In Swift % is the remainder operator [0][1] and there's also the `.truncatingRemainder(dividingBy:)` and `.remainder(dividingBy:)` methods on floating-point types [2].
In many programming languages, a % b is simply a - b*(a/b), where '/' is integer (truncated toward 0) division. I'm alright with this because:
1. this computation is typically more efficient on silicon optimized for arithmetic,
2. this computation is unambiguous and more straightforward to people who are unfamiliar with modular arithmetic, especially when negative a and b are involved, and
3. in contexts where the mathematical remainder 0 <= r < abs(b) is needed, b is typically always known. It is easy to see that knowing a % b and b it is easy to recover r, but knowing b and r, one may not recover a % b (we don't know if it was positive or negative).
I would argue that mod is more intuitive. I imagine the integers being partitioned into contiguous bins of size b, and computing a % b means counting which index in the bin it is. This can be done visually too!
Funny, just a couple of weeks ago I faced a similar problem at work. I ended up changing slightly the code and adding a comment that read something like "We do it this way because the operation we want is the modulus, not the remainder".
> Another question you could answer would be “if I start on a road trip at 6PM, what time would it be when I get to my destination 16 hours later?”. That would be 6 + 16 mod 12 which is 10.
So many things wrong here. Why would you represent 6PM as "6"? And then you mod 12, which will only give the correct response between 12AM and 11AM. If you'd said 18 hours later you'd think you were arriving at midnight. It's a bad example anyway; why would you care what hour you arrive but not which day?
Well, that's why I always define RED(x) (for reduce modulo) as ((((x) % MOD) + MOD) % MOD). Quite useful in algorithmic competitions, which often ask you for answer modulo some prime.
I've regularly been annoyed by -1 % n being negative but I've never seen a case where the negative number is on the right.
Has anyone seen this before in real code?
> situations where you have a negative divisor and need the remainder/mod are not common.
yep. But sometimes, when you have numbers that come from some external system, and you didn't check them or expect that the % operator will make it positive, you end up with this sort of problem. Such as having negative positions with CSS, or a game where you end up with negative values for coordinates.
So: 5 mod 2 would be 1 because 5 divided by 2 is 4 with one left over.
I do not like this explanation and just don't understand what the author is getting at with this example. The answer of 1 is correct, but the explanation is just plain wrong and that makes it tough to agree with the author's thought process through the rest of the article.
17 = 1 (mod 4)
To say that 17 and 1 have the same remainder when divided by 4. If you do all of your operations and comparisons mod 4, it doesn't matter if we call the number 1 or -3.
In real life, we often need the remainder function, and we usually need it with positive numbers (how many eggs will I have left if I put these into boxes of 12). We sometimes call this the modulo function, which is a slight abuse of notation from the algebraic meaning of modulo. For positive numbers, it works completely intuitively. There are a couple of natural ways to extend this to negative numbers - an extension which would be meaningless or irrelevant in algebra - and computer language authors have (usually) called one rem and one mod.