Python, unlike C, has the mod operator always return a positive number
twitter.com
twitter.com
>>> 10%3
1
>>> (-10)%3
2
>>> 10%(-3)
-2
>>> (-10)%(-3)
-1(well a report in TOPLAS really, but that's pretty close)
There are technically 5 different versions of this operation, though only 2 (possibly 3) are in common use. Common Lisp seems to implement all of them except, somewhat oddly, the euclidean version (the "actual modulo"), its mod function is instead a flooring division.
edit: it looks like Python also follows flooring, not euclidean, meaning the quotient is rounded downwards, and per "a = nq + r" the remainder has the sign of the divisor:
>>> 5 % -2
-1
>>> divmod(5, -2)
(-3, -1)
Why? Mathematically, dividing two integers yields a real. If you want the result to be an integer, you need to define some rounding operation on the real result to produce an integer.
That is the source of the divergence between C and Python here, C rounds by truncation (towards 0), Python rounds by flooring (towards -inf).
We both know that's not true.
> Sorry. (I got the terms for quotient, dividend, and divisor mixed up.)
No big, brainfarts happen.
Rational, more specifically.
not true. if you define 'divide' as inverse multiplication over the reals then that is closer to being true (zero is an integer, dividing an integer by zero doesn't yield a real). in that case every real can be expressed as n = a/b where a and b are integers and b != 0 then yes n is a real.
But 'divide' could just as well be defined along the lines of divisibility in number theory (the study of integers) where every integer can be expressed as n = q*b + r, where n,q,b,r are all integers and r >= 0 > b. then you could say that n divide b = q, with r as remainder, and n mod b = r. These are my preferred definition of mod and integer division.
Of interesting mathematical consequence, each of my children converged on the same solution at different ages. Them: three cookies. Daddy: zero cookies.
After thinking about this, what I really want is a way to access an array with an unadjusted number and tell the array to do whatever modulizing is necessary. e.g. instead of
a[small]
a[mod1(big)]
a{small}
a[big]But I don't get how this would practically work. Would each array have a preferred n that is used for the mod operation? For most situations where that makes sense, using a 2d array seems more logical.
I assume the braces are there for "I want to skip doing the wrapping"
Now, having refined the type this way, when you try elsewhere in the code to read some unknown byte into n, WUFFS will reject that because who knows if it exceeds 40? To make the code compile, you need to actually write code that ensures n is always less than 40.
Of course you aren't going to write big general purpose software under this sort of constraint, it's like having a two year old following you everywhere insisting on a detailed explanation of why you are doing every single thing and asking the most irritating "But why?" questions after each explanation, exhausting. But if you're processing untrusted data it's exactly what you needed to stay safe.
https://stdlib.ponylang.io/builtin-Integer/#div_unsafe
and, in Ponylang, i/0 usually results in 0.
That said, I do feel that Pony should have added a 'panic' concept and then forced actors to handle panics, but that's me.
It's not completely untenable, but it's still kinda janky. I've never heard of any mathematical argument that justifies division by zero yielding 0; contrast 0^0, which at least has an argument for yielding 1: http://mathscitech.org/articles/zero-to-zero-power
0/x = 0 for all x except zero; defining 0/0=0 removes that exception.
(Caveat: I’m probably being slightly imprecise with my language here)
In the majority of these cases the most reasonable answer is 0.
> The binary arithmetic operators are +, -, *, /, and the modulus operator %.
https://archive.org/details/TheCProgrammingLanguageFirstEdit...
At least, that was the C reference I used in college.
It goes on to say: "x % y produces the remainder when x is divided by y" and that "the sign of the result for % are machine-dependent for negative operands, as is the action taken on overflow or underflow".
You will find "modulus operator" to refer to % in C in all of the above (other than the standard).
edit: tertiary -> ternary
Calling it "Ayers Rock" privileges some guy from the 19th century, calling it "Uluru" privileges a bunch of people who lived near it for longer than that, the rock itself has no opinion (and also doesn't believe anything about ritual magic, property law, gender based taboos, or the tourist industry)
Now, John Carmack is a little different because John is a person and it is rude to use names people don't like. But it isn't impossible, it's just rude. Calling the previous President of the United States of America "Tangerine Palpatine" works just fine - we both know who I meant. In fact it's a little weird that our culture has parents assign to their children full legal names, only kinda-sorta making it possible for them to choose for themselves later, the Culture's habit of allowing children to pick one of their names as part of growing up seems better.
The more something gets repeated from person to person, the higher chance that somewhere in that chain, somebody screwed up. That's why people like professors, people who run YouTube programming channels, people who answer C questions on Stack Overflow, etc. should generally strive to cut down the number of links in the chain.
The draft version "X3.???-1988" at https://web.archive.org/web/20161223125339/http://flash-gord... (linked-to from Wikipedia) has:
> % modulus operator: 3.3.5
which seems off to a good start for K&R, but then also has:
> remainder operator, %, 3.3.5
and 3.3.5 says "the result of the % operator is the remainder" -- not a whiff of a modulus present there.
Thanks!
The binary operator / indicates division. When positive integers are divided, truncation is toward 0, but the form of truncation is machine-dependent if either operand is negative. On all machines covered by this manual, the remainder has the same sign as the dividend. It is always true that (a/b)*b + a%b is equal to a (if b is not 0). The binary % operator yields the remainder from division of the first operand by the second.
> a mod b = ((a % b) + b) % b
The first remainder bounds it to -b < x < b. Then adding b goes to 0 < x < 2b. Then the second remainder gets th desired 0 <= x < b.
This will not work for b > max_int / 2 (solution in that case is much mkre language dependent)
Are C programmers still using C89 and C90?
The C compilers supplied by microcontroller vendors in particular are often, to put it charitably, not great at conforming with the latest standards.
EDIT: Fact checking myself, I found [1], so apparently they've decided to start adding C11 and C17. C99 support isn't entirely clear, though.
[1] https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
A parallel can be drawn to `export template` in C++98, which is a feature that was only ever implemented by a single compiler (whose engineers, when asked for recommendations to others attempting to implement, offered "don't"). As a result, it was dropped from later versions of the standard, and so almost every compiler doesn't actually support C++98 100%, but no one cares because the things that it doesn't implement doesn't matter. VLAs aren't quite as universally maligned as `export template`, but given that it's dropped to optional in later versions, it's not totally unreasonable to claim implementation of all of C99 that matters while not supporting VLAs.
Answering my own question: by doing a binary search on the online GCC documentation, I discovered that it's not documented up to 4.2.4. The next version up for which online documentation is hosted is 4.3.6, and that has -Wvla.
Naturally removing them from ISO C was the saner option.
VLA's crept in to the kernel, which is what this thread is about.
With -Wvla, you can learn about where all the VLA's are being declared in the code base.
Also, don't forget that VLA's are a GCC extension which existed before C99. They are available in the -stdc=gnu89 mode, and -ansi (without -pedantic).
They are available in -ansi mode (diagnosed if you use -pedantic).
They were not "removed" from ISO C; they are optional. If you implement VLA's, there is an ISO-C-conforming way to do that.
$ cat vla.c
int fun(int x, int a[x]) { return 0; }
int main(void) { return 0; }
$ gcc -ansi vla.c
$ gcc -std=gnu89 vla.c
$ gcc -ansi -pedantic vla.c
vla.c:1:1: warning: ISO C90 forbids variable length array ‘a’ [-Wvla]
int fun(int x, int a[x]) { return 0; }
^~~
$ gcc -std=gnu89 -pedantic vla.c
vla.c:1:1: warning: ISO C90 forbids variable length array ‘a’ [-Wvla]
int fun(int x, int a[x]) { return 0; }
^~~
$ gcc -std=gnu89 -pedantic -Wno-vla vla.c
$ gcc -ansi -pedantic -Wno-vla vla.c
Dynamic allocation from the stack is something that is quite essential in some situations, and a more efficient approach compared to other alternatives in some other situations.
alloca never goes away, and VLA's are better than alloca in many ways.
You can discuss your point of view with the folks that cleaned the kernel.
https://lore.kernel.org/all/CA+55aFzCG-zNmZwX4A2FQpadafLfEzK...
Notice that they are fully aware of that warning.
I don't know what point of view you're talking about; what the are discussing in the mailing list are silly uses of VLA that can be replaced by small arrays of fixed length sized to the worst case. These perform better, too.
This is not always practical in every situation.
C itself dynamically allocates from the stack. When a function is called, the increment in stack usage depends on which function. (If recursion is going on, it may not be easy to know the worst-case stack size, even if every function has a static frame size.)
Anyway, similarly, suppose we have used C to write a virtual machine. Suppose the virtual machine allocates function locals and temporaries on the native stack. When a VM function call is processed, the VM (a C program) has to allocate a frame for that. a VLA or alloca can provide that easily, with minimal waste.
> Anyway, some of these are definitely easy to just fix, and using VLA's is actively bad not just for security worries, but simply because VLA's are a really horribly bad idea in general in the kernel.
Code running in the kernel has a limited stack space. I think it's tiny, something like just a few pages.
Interrupts (which can nest) run in that stack space, not just the mainline code in syscall context. I think that might have changed though (there are interrupt specific stacks), which might also depend on the specific arch port of Linux. Still, those stacks are small and all the caveats apply to interrupt context. Don't be searching a linked list with linear recursion or using crazy VLA's.
If I had to put virtual machine execution into the kernel, though, I would definitely use VLA's or alloca to get the space required for each function to be as tight as possible to its actual requirements, the same way that the C compiler emits code for each function to allocate its frame size to exactly the needed size. Right tool for the right job.
Postgres only updated to C99 with PG12
https://www.postgresql.org/docs/11/source-conventions.html https://www.postgresql.org/docs/12/source-conventions.html
Some blame to be had by MSVC, which is called out in PEP7: https://www.python.org/dev/peps/pep-0007/#c-dialect
Why insist on MSVC when it's not one of them?
(Genuine question. I remember python was c89 for similar reasons).
Incidentally, that’s around the same time MSVC started getting updates and became bearable.
Why is a drop in replacement for MSVC needed?
There were c99 compilers for windows before clang IIRC correctly. So why weren't they used, MSVC be damned?
Full disclaimer, I've only ever used C in linux systems.
It seems that only GCC 4.3 added the -Wvla option to unbundle the diagnosis of the presence of VLA's from -pedantic.
Now you can write in gnu89, while banishing VLA's from your code base, if you're so inclined.
That just makes C look worse. Remainders are always nonnegative, as specified in the Division Algorithm [note that the Division Algorithm is the name of a theorem, not an algorithm].
https://en.wikipedia.org/wiki/Euclidean_division
Also, I'm not aware of a definition of "modulo" other than "remainder". Where are you getting the idea that they're different?
For example, https://en.wikipedia.org/wiki/Modulo_operation explicitly defines "modulo" as "remainder".
mod is Python's %, rem is C's %.
Having this for unsigned types allows you to write rem_euclid() if that's definitely what you meant even when you aren't sure if the type you'll be using here will be signed (and thus it matters) or not.
Unfortunately Rust's std::ops::Rem trait (the trait which provides the overloadable % operator) does not offer this alternative, so if all you know about a type is that you can apply the modulus operator to it, you only get that operator and there's no uniform way to get a Euclidean remainder instead.
Scheme:
> (mod 5 2)
1
> (mod 5 -2)
1
> (mod -5 2)
1
> (mod -5 -2)
1
> (remainder 5 2)
1
> (remainder 5 -2)
1
> (remainder -5 2)
-1
> (remainder -5 -2)
-1
Prelude> a = 5 :: Integer
Prelude> b = 2 :: Integer
Prelude> mod a b
1
Prelude> mod a (-b)
-1
Prelude> mod (-a) b
1
Prelude> mod (-a) (-b)
-1
Prelude> rem a b
1
Prelude> rem a (-b)
1
Prelude> rem (-a) b
-1
Prelude> rem (-a) (-b)
-1
I prefer Scheme's way, because it was what we always used in classes when I studied maths. mod returning a negative number is just too weird.
EDIT: It appears that Scheme also has modulo, which comes from floored division:
> (modulo 5 2)
1
> (modulo 5 -2)
-1
> (modulo -5 2)
1
> (modulo -5 -2)
-1https://wiki.forth-ev.de/doku.php/projects:signed_integer_di...
Lots of other languages got it wrong:
https://en.wikipedia.org/wiki/Modulo_operation#In_programmin...
Symmetric division is the kind of thing that causes rockets ships to explode unexpectedly.
Symmetric division considered harmful:
https://www.nimblemachines.com/symmetric-division-considered...
>Since its 1983 standard (Forth-83), Forth has implemented floored division as standard. Interestingly, almost all processor architectures natively implement symmetric division.
>What is the difference between the two types? In floored division, the quotient is truncated toward minus infinity (remember, this is integer division we’re talking about). In symmetric division, the quotient is truncated toward zero, which means that depending on the sign of the dividend, the quotient can be truncated in different directions. This is the source of its evil.
>I’ve thought about this a lot and have come to the conclusion that symmetric division should be considered harmful.
>There are two reasons that I think this: symmetric division yields results different from arithmetic right shifts (which floor), and both the quotient and remainder have singularities around zero.
>If you’re interested in the (gory) details, read on. [...]
"The expression x % y produces the remainder when x is divided by y" K&R C p37
r = (i + N) % N
I remember Ada having two different operators REM and MOD which I think is the best language choice.
Nitpick: it never was “just do whatever the underlying hardware does”. C standards try hard to avoid mentioning hardware at all (and, as far as I know, succeed at that), and there’s plenty of hardware that doesn’t do mod in hardware, yet supports it in C.
For example, the size of int is not specified by the standard, as you said. But it can still be different from the natural word size of the underlying hardware, if the compiler vendor chooses to make it so. Case in point is int on 64-bit platforms is usually 32-bit in practice. In Microsoft's compiler, even long int is 32-bit even on 64-bit hardware.
Taken from Modula-2.
r = ((i % N) + N) % N
There may be faster ways, but that should at least be correct for all inputs.
If defined as
```
int16_t mod(int16_t i, int16_t N) {
return ((i % N) + N) % N;
```
There do not seem to be any issues all the way up to INT16_MAX. Even with negative values of N, it produces the same value as python does (although I am not certain I understand what modulus means with a negative N)
i%N is just i, and then (i%N)+N overflows. The result is undefined. Even on systems where it is defined, the typical result would be incorrect.
It’s a bit weird that you chose int16_t for your example… it’s the kind of thing you might do if you were trying to make some point about different integer types, but you didn’t give a reason for using int16_t, so the point is lost. I can’t read your mind.
The case you suppose makes sense, but for some reason does not produce incorrect results when I run it, for instance:
N = INT16_MAX - 2:
mod(32762, 32765) = 32762
mod(32763, 32765) = 32763
mod(32764, 32765) = 32764
mod(32765, 32765) = 0
mod(32766, 32765) = 1
mod(32767, 32765) = 2
> I wonder if the compiler just used the full register. I'll have to check the disassembly.
No need, you'd figure this out just by knowing what the C spec says and by knowing what the value of INT_MAX is. When you compute the remainder in C, the operands first undergo "integer promotion" and then go through the "usual arithmetic conversions". The result is that you end up with two values of the same type, no narrower than int.
So in C, the following function:
short broken_modulo(short x, short y) {
return ((x % y) + y) % y;
}
short broken_modulo(short x, short y) {
int ix = (int)x;
int iy = (int)y;
// All int, no short.
int result = ((ix % iy) + iy) % iy;
return (short)result;
}
// Possible.
typedef int int16_t;
According to Boute 1992,
> The Ada Reference Manual complements integer division (/) with two functions mod and rem. The first of these violates the division rule
so it doesn't so much have two different operators as one operator and one broken mess, and its one operator is the truncating division (C-style).
Also a quick check of the Hyperspec (or, again, Boute 1992) shows there are not two but 4 definitions based on rounding quotients, I think none of which "always returns a positive number" (which Python also does not do, incidentally).
There is a 5th definition, which Boute 1992 champions, for which the property asserted in the title holds.
I wouldn't even bother with this, I'd just use a modular type (i.e. unsigned).
with Ada.Text_IO;
procedure Main is
-- Modular type (unsigned) which can take values of [0, 15].
type Nibble is mod 16;
Value : Nibble := 0;
begin
-- Prints 0 3 6 9 12 15 2 5 8 11 14 1 4 7 10 13 ...
for I in 0 .. 63 loop
Ada.Text_IO.Put_Line (Value'Image);
Value := Value + 3;
end loop;
end Main;
type Circular_Buffer is array (Nibble) of Integer;
Buffer : Circular_Buffer;Source: The draft C99 standard http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94, physical page 82.
Yes, as someone who both gets open source bug reports and has sent out open source bug reports, what determines whether a behavior being looked at is a bug depends on what the relevant standards say.
https://port70.net/~nsz/c/c89/c89-draft.html#3.3.5
> When integers are divided and the division is inexact, if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than the algebraic quotient or the smallest integer greater than the algebraic quotient is implementation-defined, as is the sign of the result of the % operator. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a .
C99 draft standard: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94, physical page 82, “When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.” with a footnote: “This is often called ‘‘truncation toward zero’’”
I wish % was a modulo instead of a remainder operation; this bug has bitten me more than once.
The RFC that introduced rem_euclid: https://github.com/rust-lang/rfcs/blob/master/text/2169-eucl...
For what it's worth, Python does not implement euclidean modulo (it implements flooring division aka "F-definition", proposed by Knuth), so Rust did not implement "this" it implemented an operation which, as far as I can tell, Python doesn't have.
It seems quite relevant as it diverges significantly from the assertion put forth in the tweet: Python's remainder takes the sign of the divisor. So flooring division fixes the more common issue but leaves an other one present.
> python, unlike C, had the mod operator always return a positive number, even if the first argument is negative
That is true for Rust's rem_euclid as well: https://play.rust-lang.org/?version=stable&mode=debug&editio...
remainder(a, b)
n = round(a/b)
return a - n * b
Even more fun as the original x87 implementation preceded IEEE754 its remainder operation (fprem, because it's technically a partial remainder) used truncation rather than rounding as that's the obvious behaviour. To support the IEEE754 specification they had to add fprem1 which performs a rounding operation instead. Hurrah! :D
Even better, because it's defined in terms of rounding, it changes according to rounding mode :D
[0] https://github.com/mike-bourgeous/mb-sound/blob/a8eb1232ae35...
If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a
For division:
The result of the / operator is the quotient from the division of the first operand by the second
Which is remarkably vague. Presumably, they are doing the kind of third grade math where we get a quotient and a remainder (Euclidean division). So, 1/3 is 0, 2/3 is 0, 3/3 is 1, 4/3 is 1, 5/3 is 1, 6/3 is 2, etc.
That in mind, let’s look at -1 % 3 (is 2 when doing a proper modulo operation)
With integers:
(-1 / 3) is 0 (1 / 3 is “0 remainder 1” and multiplied by -1 still gives us 0)
This in mind, the modulo (-1 % 3) needs to give us -1:
(0 * 3) + -1 = -1
So a%b is negative here.
There are some ways to work around this and get a proper modulo.
One common case is to get something modulo a power of 2. This will give us a modulo, 20 in this case, as per the C standard:
#include <stdint.h>
uint32_t foo = 12;
printf("%d\n",-foo % 32);
if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
So, since foo is unsigned, and a 32-bit int, -foo is -12 + 4294967296, or 4294967284. 4294967284 % 32 as per the spec above is 20, i.e. -12 mod 32.
This trick only works if we modulo a number by a power of 2.
Yes, I have used this trick when writing “golfed” C code which needs to do a circular rotate:
uint32_t r=12,g=1;g=g>>r|g<<-r%32;Unfortunately hardware never fixed this issue, and C is never going to expose an operator that doesn't map primitively to the hardware, so it became the established default.
It also desirable to have the remainder consistent with the result of division, such that x = d*r + mod, where r is the result of division. Combine that with the above requires negative mods.
-4 also makes sense.
> It also desirable to have the remainder consistent with the result of division, such that x = d*r + mod, where r is the result of division. Combine that with the above requires negative mods.
Python's behaviour is consistent with that definition:
>>> divmod(-7, 2)
(-4, 1)
Consider x/3=y. For real numbers, it's trivial to manipulate this equation into (x-3)/3=y-1. However, this only works when integer division rounds down.
5/3 = 1 rem 2 or 1 rem 2
4/3 = 1 rem 1 or 1 rem 1
3/3 = 1 rem 0 or 1 rem 0
2/3 = 0 rem 2 or 0 rem 2
1/3 = 0 rem 1 or 0 rem 1
0/3 = 0 rem 0 or 0 rem 0
-1/3 = -1 rem 2 or 0 rem -1
-2/3 = -1 rem 1 or 0 rem -2
-3/3 = -1 rem 0 or -1 rem 0
All of this is a fairly moot point: The answer is it should do what the algorithm using it needs it to do.
[1] e.g. http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf PDF page 94/physical page 82
From PDF page 94 (physical page 82) of the draft C99 standard: [1] The result of the / operator is the quotient from the division of the first operand by the second
This is a little vague; it would be better if they called it the “quotient from Euclidean division” (EDIT: This was incorrect. Actually, it’s the quotient from algebraic division, with the fraction truncated, also called “truncation towards zero”. See discussion below.), which is well defined as being -3 in the above example; see https://en.wikipedia.org/wiki/Euclidean_division (EDIT: Euclidean is -4; truncation towards 0 is -3)
[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
main() { printf("%d\n",-7/2);}
PDF page 110, physical page 92: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. with a footnote: This is often called ‘‘truncation toward zero’’
-7/2 is -3.5, so discarding the fractional part gives us -3
In practice, this offloads the problem to your programmer in at least every other case (i.e. when % doesn’t what they need out of box), who then miscalculates or mistests their solution and now the problem is yours.
It doesn’t matter what the standard says, there should be many functions, each for a combination of signs (or roundings) you want in the results. Because your library doesn’t suck and your programmer has things to do instead of fiddling with off by ones and other primitive but highly error-prone-under-stress bs.
"If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined"
Fortunately, this was changed at some point between C '99 and C '11, so that now the remainder is consistently defined across all implementations.
$ perl -E 'say(4 % -3)'
-2
$ perl -E 'use integer;say(4 % -3)'
1It's a pattern in Perl, like "use strict;" for example, which is also lexically scoped and has a "no strict;" counterpart.
https://en.cppreference.com/w/cpp/numeric/math/fmod
https://en.cppreference.com/w/cpp/numeric/math/remainder
A valid use may be when approximating a periodic function via a polynomial (e.g. sin/cos), where you will want to first perform range reduction like std::fmod(x, 2 * pi).
As Carmack notes it's great for array/buffer indices - and bites you if you expect it in C!
It was quite confusing trying to port this diff algorithm https://blog.robertelder.org/diff-algorithm/
mouse cursor moves toward up-arrow