[HN Gopher] Python, unlike C, has the mod operator always return...
___________________________________________________________________
Python, unlike C, has the mod operator always return a positive
number
Author : tosh
Score : 56 points
Date : 2021-12-29 20:54 UTC (2 hours ago)
(HTM) web link (twitter.com)
(TXT) w3m dump (twitter.com)
| the_mitsuhiko wrote:
| So 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-eucl...
| masklinn wrote:
| > 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 wrote:
| The 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 wrote:
| > 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 wrote:
| The 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&editio...
| bodhiandpysics1 wrote:
| When 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.
| lalaithion wrote:
| Haskell 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 wrote:
| In 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.
| jinwoo68 wrote:
| Common Lisp has both `mod` and `rem` together with their matching
| operation `floor` and `truncate` respectively.
|
| http://clhs.lisp.se/Body/f_mod_r.htm
| tyingq wrote:
| Perl can do both ways: $ perl -E 'say(4 % -3)'
| -2 $ perl -E 'use integer;say(4 % -3)' 1
| olliej wrote:
| The 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 wrote:
| This 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.
| Lt_Riza_Hawkeye wrote:
| My 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 wrote:
| FWIW there's an entire paper on the subject of these
| operations: 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).
| saurik wrote:
| I 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.
| masklinn wrote:
| > I kind of get what you are saying syntactically, but the
| semantics are weird to me as the C version is only defined
| for integers
|
| 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).
| dragonwriter wrote:
| > Mathematically, dividing two integers yields a real
|
| Rational, more specifically.
| desio wrote:
| > Mathematically, dividing two integers yields a real
|
| 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.
| desio wrote:
| sorry, rational, not real.
| saurik wrote:
| Oh, I'm dumb. Sorry. (I got the terms for quotient,
| dividend, and divisor mixed up.)
| masklinn wrote:
| > Oh, I'm dumb.
|
| We both know that's not true.
|
| > Sorry. (I got the terms for quotient, dividend, and
| divisor mixed up.)
|
| No big, brainfarts happen.
| StefanKarpinski wrote:
| Good paper. Julia implements all versions and overloads `div`
| and `rem` to take a rounding mode argument. It also gives
| special names to a few of them and they come in pairs: `div`
| & `rem`, `fld` & `mod` (`fld` stands for "floored divide" as
| opposed to `div` which rounds towards zero). The `%` operator
| does remainder like C, which was a tough call, but we figured
| being compatible with C was worthwhile for people porting
| code. It's also less useful in Julia due to default 1-based
| indexing of arrays; for that there is a `mod1` function that
| returns a value between 1 and n.
| bee_rider wrote:
| Somewhere out there in the universe, there's an nightmare
| that starts with "Well, zero is kind of an unusual number, so
| for safety sake we've defined our division to always round
| away from zero. This resulted in an interesting mod
| operation..."
| aix1 wrote:
| Also this TR: https://www.microsoft.com/en-us/research/wp-
| content/uploads/...
| [deleted]
| ollien wrote:
| Yep. I remember that for my first C assignment in college we
| had to write a calendar, and leap year calculations needed
| modulos. I remember distinctly that I tore my hair out trying
| to figure this out, especially because I was prototyping my
| math in Python. I eventually resolved that I needed to
| constantly ensure my sum was > 0 (by adding my modulo base).
| Normal_gaussian wrote:
| That will only work for cases where a >= -b. For the more
| general case:
|
| > 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)
| eesmith wrote:
| K&R "The C Programming Language" (1978), p.37:
|
| > 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.
| klodolph wrote:
| You'll only find that terminology in K&R. The C specification
| only uses "modulo" to refer to the behavior of unsigned
| numbers, and uses "remainder" to refer to the behavior of %.
| This is true of at least several versions of the C standard
| dating back to 1999, I don't have the C90 spec handy.
| eesmith wrote:
| Indeed!
|
| 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!
| somerando7 wrote:
| People generally watch tutorials, read programming books,
| blogs, stackoverflow to learn programming, not the standard
| of a programming language.
|
| You will find "modulus operator" to refer to % in C in all
| of the above (other than the standard).
| charcircuit wrote:
| I think there is the same problem with the conditional
| operator "?" which a ton of resources name as the ternary
| operator.
|
| edit: tertiary -> ternary
| eesmith wrote:
| I know it as "the ternary operator" (used that way in K&R
| at https://archive.org/details/TheCProgrammingLanguageFir
| stEdit...), and until about 2 minutes ago had never heard
| it as "the conditional operator" - even though that's how
| the spec describes it!
| klodolph wrote:
| That is what most people do... which is why those of us
| who write tutorials, write programming books, write blog
| posts, and write Stack Overflow answers have a
| responsibility to go to the source.
|
| 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.
| xboxnolifes wrote:
| The fact that tutorials teach incorrect knowledge does
| not make the knowledge correct.
| tialaramex wrote:
| This is also exactly what the ANSI ("Second edition") K&R
| book I have in front of me says.
|
| 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".
| kazinator wrote:
| C only pinned this down in C99. In C90, the sign of the
| remainder was implementation-defined in those cases in
| question.
| [deleted]
| superjan wrote:
| Careful 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.
| naniwaduni wrote:
| It'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.
| masklinn wrote:
| > 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
| tialaramex wrote:
| Note 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 wrote:
| What other languages also do this? I know Lua is one.
| okl wrote:
| Wikipedia has got a list:
| https://en.wikipedia.org/wiki/Modulo_operation#In_programmin...
| masklinn wrote:
| To explain the key for those who don't want to read the
| article: "truncated" is C's behaviour, "floored" is Python's.
| mfashby wrote:
| golang 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/
| waynecochran wrote:
| Doesn'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.
| [deleted]
| masklinn wrote:
| > 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 wrote:
| Ada 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;
| Someone wrote:
| In C this used to be "implementation defined". That changed in
| C99 and C++11 (https://en.wikipedia.org/wiki/Modulo_operation#I
| n_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.
| gmiller123456 wrote:
| You 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 wrote:
| In 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.
| beervirus wrote:
| kevin_thibedeau wrote:
| > I remember Ada having two different operators REM and MOD
|
| Taken from Modula-2.
| MobiusHorizons wrote:
| Btw 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 wrote:
| Incorrect for N > INT_MAX/2.
| scotty79 wrote:
| Not if i is less than -N. Modulo operator that wraps -1 to N-1
| would be waay better.
___________________________________________________________________
(page generated 2021-12-29 23:00 UTC)