10 ms·
Python, unlike C, has the mod operator always return a positive number
- dlbucci 5y agoActually, I vaguely recall that if the divisor (or whatever the right number is) is negative, the result will be negative. But that's still consistent with math modulus, as is the Python approach. I always miss Python mod when I go to other languages, honestly...
- musicale 5y agoI've noticed this when switching contexts between Python and C. As Carmack notes it's great for array/buffer indices - and bites you if you expect it in C!
- waynecochran 5y agoDoesn’t C just do whatever the underlying hardware does for modulo w negative numbers? I have always worked around this by adding N to numerator: r = (i + N) % N which handles cases where i >= -N which is mostly what I run into when i is negative. I remember Ada having two different operators REM and MOD which I think is the best language choice.
- Someone 5y agoIn C this used to be “implementation defined”. That changed in C99 and C++11 (https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages https://en.wikipedia.org/wiki/Modulo_operation#In_programmin..., note c) 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.
- beervirus 5y ago
- gmiller123456 5y agoYou make a good point, but I think he was more generalizing to actual implementations of C compilers. And that does align with my experience.
- alerighi 5y agoIn C there are ton of things that are hardware dependent. For example the size of every data type is not specified, or the fact that char is signed or unsigned, the representation of signed integers (tough I don't think there still exist a platform that doesn't use 2's complement), ad a ton of other things.
- deleted 5y ago[deleted]
- quietbritishjim 5y agoI think there parent comment just meant that implementation dependent is technically not the same as hardware dependent. 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.
- kevin_thibedeau 5y ago> I remember Ada having two different operators REM and MOD Taken from Modula-2.
- scotty79 5y agoNot if i is less than -N. Modulo operator that wraps -1 to N-1 would be waay better.
- deleted 5y ago[deleted]
- MobiusHorizons 5y agoBtw that code won’t work in the general case (where i could be less than -N). For that case you should probably do r = ((i % N) + N) % N There may be faster ways, but that should at least be correct for all inputs.
- klodolph 5y agoIncorrect for N > INT_MAX/2.
- MobiusHorizons 5y agoI'm not sure I follow. 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)
- klodolph 5y agoLet i=INT_MAX-1, N=INT_MAX. 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.
- MobiusHorizons 5y agoI chose int16 just to make it easier to write an exhaustive search. That is where my assertion that the code works correctly comes from. 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.
- masklinn 5y ago> I remember Ada having two different operators REM and MOD which I think is the best language choice. 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.
- pyjarrett 5y agoAda mod takes the sign of the second operand. 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; Then make that type the index into my circular buffer and then I never need to worry about it. type Circular_Buffer is array (Nibble) of Integer; Buffer : Circular_Buffer;
- strenholme 5y agoIn C99, the modulo operator is defined thusly: “If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a” Source: The draft C99 standard http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf 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.
- __s 5y agoMeanwhile, C89: https://port70.net/~nsz/c/c89/c89-draft.html#3.3.5 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 .
- strenholme 5y agoBetween C89 and C99, the standard was updated to require integer division to truncate towards 0. C99 draft standard: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf 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.
- Lt_Riza_Hawkeye 5y agoMy understanding from college was that C doesn't have a modulo operator, if you look at the spec (according to my professor (according to my memory)) it's called the "remainder operator". Modulo and remainder are not the same operation, so both python and C are correct
- masklinn 5y agoFWIW there's an entire paper on the subject of these operations: https://core.ac.uk/download/pdf/187613369.pdf https://core.ac.uk/download/pdf/187613369.pdf (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) The C version is the "truncating" division, meaning the quotient is truncated (rounded towards 0).
- aix1 5y agoAlso this TR: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/divmodnote-letter.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- cormacrelf 5y agoThis one is very concise, great as a reference, you can remind yourself of which negatives go where in an instant.
- saurik 5y agoI kind of get what you are saying syntactically, but the semantics are weird to me as the C version is only defined for integers in the first place so saying that the operator is truncating something is an awkward mental model.
- lalaithion 5y agoHaskell provides two functions for integer division, div and quot, and two functions for modulus, mod and rem. quot rounds towards 0, and div rounds towards negative infinity. rem is quot's modulus, and mod is div's modulus. mod is Python's %, rem is C's %.
- tialaramex 5y agoIn Rust, the integer types [even the unsigned ones where it makes no difference] provide rem_euclid() that gives you a non-negative answer, whereas % is defined to have the same sign as your dividend if it isn't zero. 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.
- bjoli 5y agoScheme is the same, since at least r4rs, which came out in 1991. Not having it is, I would argue, bad taste.
- yakubin 5y agoIt's a bit different: 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 Haskell: 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 So in Scheme mod is the Euclidean modulus (always >= 0) and remainder takes the sign of the dividend (comes from truncated division, same as C's %). In Haskell mod takes the sign of the divisor (floored division, same as Python), while rem behaves the same way as Scheme's remainder or C's %. 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) -1
- superjan 5y agoCareful what you wish for. What should -7 / 2 return? -3 kind of makes sense, because 7/2 is 3. 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.
- masklinn 5y ago> Careful what you wish for. What should -7 / 2 return? -3 kind of makes sense, because 7/2 is 3. -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) -7 = -4 * 2 + 1
- naniwaduni 5y agoIt's highly desirable for -7/2 to equal -4, since this lets integer division by powers of two be exactly equivalent to a two's complement arithmetic right shift. In a C mindset, rounding toward zero is pretty much an objectively wrong holdover from before we knew better.
- Laremere 5y agoMoving past the intuition for how division and remainders work for real numbers, there are other ways to look at "obvious" answers that suggests -7/2=4. 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 One of these has a consistent pattern, the other doesn't. All of this is a fairly moot point: The answer is it should do what the algorithm using it needs it to do.
- superjan 5y agoIt is not so much my intuition but the intuition of the language designers. I would prefer euclidian division personally.
- tialaramex 5y agoNote that, of course, zero is not "a positive number" since we're operating on the integers here and "signed" zero isn't a thing for either C or Python integers, but I think we all know what Carmack meant here.
- ufo 5y agoWhat other languages also do this? I know Lua is one.
- okl 5y agoWikipedia has got a list: https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages https://en.wikipedia.org/wiki/Modulo_operation#In_programmin...
- masklinn 5y agoTo explain the key for those who don't want to read the article: "truncated" is C's behaviour, "floored" is Python's.
- mfashby 5y agogolang unfortunately also produces negative results from the mod operator It was quite confusing trying to port this diff algorithm https://blog.robertelder.org/diff-algorithm/ https://blog.robertelder.org/diff-algorithm/
- the_mitsuhiko 5y agoSo when Rust implemented this they chose to leave the % operator like in C and hide the one that is more useful for humans behind `rem_euclid`. This is unfortunate but at least it exists. The RFC that introduced rem_euclid: https://github.com/rust-lang/rfcs/blob/master/text/2169-euclidean-modulo.md https://github.com/rust-lang/rfcs/blob/master/text/2169-eucl...
- masklinn 5y ago> So when Rust implemented this 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.
- the_mitsuhiko 5y agoThe difference between flooring and euclidean modulo is quite irrelevant in practice for the most part. Either way resolve the main issue with truncating modulo that is the issue outlined in the tweet.
- masklinn 5y ago> The difference between flooring and euclidean modulo is quite irrelevant in practice for the most part. 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.
- the_mitsuhiko 5y agoThe tweet we're discussing: > 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&edition=2021&gist=59080e23e6c7dcf60e5ef766b52e1d20 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- tyingq 5y agoPerl can do both ways: $ perl -E 'say(4 % -3)' -2 $ perl -E 'use integer;say(4 % -3)' 1
- floatboth 5y agoInterpreter state ("what's been `use`d") completely changing the meaning of that expression sounds like the worst possible way to do it.
- tyingq 5y agoIt is lexically scoped, so you can wall it off with a {} block. And there's 'no integer;' to turn it off as well. It's a pattern in Perl, like "use strict;" for example, which is also lexically scoped and has a "no strict;" counterpart.
- gpvos 5y agoMaybe it amounts to the same thing, but the example you give is not what the original post is about, which is -4 % 3 . It is true that "use integer" affects both calculations.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- jinwoo68 5y agoCommon Lisp has both `mod` and `rem` together with their matching operation `floor` and `truncate` respectively. http://clhs.lisp.se/Body/f_mod_r.htm http://clhs.lisp.se/Body/f_mod_r.htm
- bodhiandpysics1 5y agoWhen trying to understand C, it's always useful to look at what the pdp-11 did. the pdp-11 didn't have a mod instruction; but its div instruction can be used instead. Div can only take an even numbered register as its dest. That register holds the quotient. The odd numbered register numbered one greater then dest holds the remainder, which for a negative number will naturally be negative. so div easilly be used to calculate a mod-just ignore the quotient, but you'll get a negative value.
- olliej 5y agoThe IEEE754 remainder function even beats C in that it can return a negative value even if both inputs are positive. IIRC the logic that leads to this is: remainder(a, b) n = round(a/b) return a - n * b Because it rounds to get n, n * b can be greater than a :D 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
- mattbee 5y agoThis bit me the other way in JavaScript a couple of weeks back! I'd been used to Ruby which never returned negative numbers, but JavaScript follows C and it messed me up for 20 minutes.
- strenholme 5y agoLet’s look at the free draft version of C99 ( http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf ). On PDF page 94 (physical page number 82), we cover integers: 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); The reason is because, as per PDF page 55 (page 43) of that draft C99 standard: 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;
- ineedasername 5y agoSide question: what is the common behavior for mod on floating point? I have used it on integers plenty of times of course but not come across a situation where I would need similar behavior for floats. Is there something that's part of typical language's standard libraries or do you roll your own if you need it?
- MauranKilom 5y agoSee std::fmod and std::remainer: https://en.cppreference.com/w/cpp/numeric/math/fmod https://en.cppreference.com/w/cpp/numeric/math/fmod https://en.cppreference.com/w/cpp/numeric/math/remainder 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).
- foxes 5y agoYou would think modding a negative number -x by m should really mean taking the mod of the inverse of x in Z_m. Additive modular inverse. Eg -2 mod 3 = 1. In Z_3 we have 1 + 2 = 3 = 0, so -2 -> 1.
- Lamad123 5y agoI was reading Crafting Interpreters about a month ago and thought of writing a fizzbuzz in the language taught in the book. The language doesn't have a mod operator so I wrote function for that. I tried testing it against python's mod, but it didn't match where different signs were involved. I thought operands should be treated as absolute values and the resulted be negated when two different signs are involved. Then I found that python did it differently from something like C.
- nitrogen 5y agoRuby's % operator behaves the same way, for both integer and float values. A positive-only modulus function is useful for wrapping angles. This bit me a week or two ago when I was porting audio algorithms from Ruby to C, and had to implement a positive modulus function[0]. [0] https://github.com/mike-bourgeous/mb-sound/blob/a8eb1232ae35e501948004bca3e798cfa727898c/ext/mb/fast_sound/fast_sound.c#L192 https://github.com/mike-bourgeous/mb-sound/blob/a8eb1232ae35...
- valbaca 5y ago% has always been remainder operator and mistakenly referred to as the 'mod' operator: "The expression x % y produces the remainder when x is divided by y" K&R C p37
- saila 5y agoModulo, in this context, is defined as the remainder when dividing two numbers, and mod is just short for modulo. Is your objection that the term modulo didn't originally have this meaning? That aside, perhaps the % operator should be pronounced "rem(ainder)" too avoid unnecessary jargon.
- DonHopkins 5y agoThe FORTH-83 standard adopted floored division. https://wiki.forth-ev.de/doku.php/projects:signed_integer_division https://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_programming_languages 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-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. [...]
- MaxBarraclough 5y agoInteresting article, thanks. I've created a thread for it: https://news.ycombinator.com/item?id=29751749 https://news.ycombinator.com/item?id=29751749
- analog31 5y agoAn amusing memory from grade school is that we stopped using remainders before we started using negative numbers. So if you were to ask me how a remainder operator should behave on negative numbers, I'd be at a loss. I don't think it was ever defined in any of my math classes, through grad school.
- williamkuszmaul 5y agoIt's even worse than most people seem to realize. For many years the ISO standard for C included the line: "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.
- tinus_hn 5y agoAcross all implementations that fully support C99, which is not all implementations.
- niccl 5y agoFun fact: SQL does the same as C, but calls it modulo (at least in postgres, and I assume it's the standard)
- laserbeam 5y agoWhich is why newer languages just give you both :p. Zig (for example) has @mod and @rem for modulo and remainder and will complain when you use % on signed integers because it could be ambiguous and asks you to type in specifically which variant you intended to use.
- throwaway984393 5y ago"Famous person has tweeted something" mouse cursor moves toward up-arrow
- mmis1000 5y agoI know why it implements that way. But what baffle me the most is "What is it actually useful for?". I never encounter a situation that I want % to return a negative number. And I didn't see anyone do it either. Situations I encountered are either "they are always positive so it doesn't matter" or "I want a positive one". Do anyone have example about when will it be useful?
- Veedrac 5y agoC's version is a byproduct of this being easier for hardware to calculate, stemming back from the time, long ago, where that was actually a relevant concern. 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.
- tzs 5y agoThe submission is a tweet which doesn't really have a title, so the submitter was forced to make up one. Unfortunately the assertion in the chosen title is not correct. In Python the mod operator returns a number with the same sign as the second argument: >>> 10%3 1 >>> (-10)%3 2 >>> 10%(-3) -2 >>> (-10)%(-3) -1
- tosh 5y agoThank you for highlighting this.
- 0xdeadb00f 5y agoI was going to mention this, having literally just run into this behavior yesterday.
- keymone 5y agomod and rem are not the same.
- lngnmn2 5y agoA negative remainder is nonsense, isn't it?
- yfzhou 5y agoThey should have used “non-negative” instead of “positive.” At first glance of the title I thought “What? The Python mod operator never return a 0?”
- deleted 5y ago[deleted]