We should be a bit careful with what one means by "modulo arithmetic" here. If we are talking about arithmetic in Z/nZ (read "integers modulo n"), then the objects being acted upon are no longer integers, but equivalence classes of integers. That is, the set of all integers that satisfy the equivalence relation "~" where "a ~ b" means a - b = k*n for some integer k. For example, one of the equivalence classes in Z/3Z would be the set {..., -4, -1, 2, 5, ...}.
Since every element of the set is equivalent under that relation, we typically will choose a representative of that equivalence class, e.g., [2] for the previous class. If we view the "mod" or "modulo" operator to be a mapping from the integers to a particular representative of its equivalence class, there's no reason that negative values should be excluded. [-1] refers to the same equivalence class as [2], [32], and [-7]. The details of how integers are mapped to a chosen representative seem to vary from language to language, but modular arithmetic works all the same between them.
C generally does return negative numbers when you use the % operator.
You have to memorize the full definition. There's no mnemonic shortcut.
More precisely, regarding E1 << E2, it is written (in the April 2023 ISO C draft):
"If E1 has a signed type and nonnegative value, and E1 × 2ᴱ² is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined."
Thus if E1 is negative, or if the result overflows, UB.
i haven't read the rationale, but presumably the committee did this because it's what virtually all cpus do (because it's what fortran does), so it's the only thing that can be implemented efficiently on virtually any cpu with a division instruction, and so virtually all c implementations did it, and standardizing the behavior of virtually all c implementations is better than leaving it implementation-defined or standardizing a behavior that conflicts with virtually all existing implementations and can't be implemented efficiently on most high-end hardware
Too bad they made the wrong decision in not supporting the expected floating point behavior of division through zero (python throwing errors, rather than return inf or nan)
Division by the two almost zero numbers will also give "unexpected" results, if inf is unexpected.
people commonly opt out of python's behavior in this case by using numpy
python's decision is maybe suboptimal for efficient compilation, but it has a lot of decisions like that
edit: downthread https://news.ycombinator.com/item?id=39540416 pclmulqdq clarifies that in fact trapping on division by zero is not only ieee-754-compliant but (unlike flooring integer division!) efficiently implementable on common high-performance architectures
What hardware does with these exceptions is a separate question, though. Some CPUs will swallow them for performance.
No love for Euclidean division?
Granted, getting used to multiple value calls takes getting used to. I think I like it, but I also think I emphatically did not like it initially.
Basically, it seems as soon as you introduce a floating point number, it stays there. Which is roughly what I would expect.
In the floating-point case, you have to choose between negative remainders or potentially inexact results. And you definitely want integer division to work the same as float division.
>>> 1 / 0.1
10.0
>>> 1 // 0.1
9.0
I found out about this recently because in Polars I defined a // b for floats to be (a / b).floor(), which does return 10 for this computation. Since Python's correctly-rounded division is rather expensive, I chose to stick to this (more context: https://github.com/pola-rs/polars/issues/14596#issuecomment-...).
If you use it without considering rounding modes carefully and then round to integer, you can get some funny results.
That said, I don't really see why you would necessarily want float and integer division to behave the same. They're completely different types used for completely different things. Pick the one that is appropriate for your use case.
(It seems like abs(a % b) <= abs(b / 2) might be the right choice for floats which is pretty clearly not what you want for integers. I also just learned that integer division // can be applied to floats in Python, but the result is not an integer, for some reason?)
i also didn't know python supported // on floats
def div_floor(a, b):
return a // b
def div_ceil(a, b):
return (a + b - 1) // b
def div_trunc(a, b):
return a // b if (a < 0) == (b < 0) else -(-a // b)
def div_round(a, b):
return (2*a + b) // (2*b)Why Python's Integer Division Floors - https://news.ycombinator.com/item?id=1630394 - Aug 2010 (2 comments)
edit: -3//2 == -2 for instance, since it's strictly integer division
Basically, there's no free lunch. Personally, I prefer truncating integer division in combination with a pair of remainder operators.
>Python, unlike C, has the mod operator always return a positive number (twitter.com/id_aa_carmack):
https://news.ycombinator.com/item?id=29729890
https://twitter.com/ID_AA_Carmack/status/1476294133975240712
tzs on Dec 30, 2021 | next [–]
>The 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
DonHopkins on Dec 30, 2021 | parent | context | favorite | on: Python, unlike C, has the mod operator always retu...
The FORTH-83 standard adopted floored division.
Signed Integer Division, by Robert L. Smith. Originally appearing in Dr. Dobb's Journal September 1983:
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_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. [...]
3 not 4..
Not a hard question to answer.
- When using modulo to access an array cyclically. (You might get lucky that your language allows using negative numbers to index from the back. In that case, both conventions work.) - When lowering the resolution of integers. If you round to zero, you get strange artifacts around zero, because -b+1, ..., -1, 0, 1, ..., b-1 all go to zero when dividing by b. That's 2b-1 numbers. For every other integer k, there are only b numbers (namely bk, bk+1, ..., bk+b-1).
I have never seen a case where truncation was the right thing to do. (When dealing with integers. Floats are different, of course, but they are not what this is about.)
Splitting a quantity into units of differing orders of magnitude. For example, −144 minutes is −2 hours and −24 minutes, not −3 hours and 36 minutes. This is about the only case I know of, though.
[1] https://en.wikipedia.org/wiki/Modulo#In_programming_language...
On the contrary I can't imagine when and why anybody would want truncation. That's just a side effect of the used algorithm and not something that actually makes much (any?) sense.
- given a number t of seconds after the epoch, what time of day does it represent? using python's definition, (t + tz) % 86400
- given an offset d between two pixels in a pixel buffer organized into sequential lines, what is the x component of the offset? using python's definition, d % width is right when the answer is positive, width - (d % width) when the answer is negative, so you could write d % width - d > p0x ? d % width : width - d % width. this gets more complicated with the fortran definition, not simpler
edit: the correct expression is (d % width if p0x + d % width < width else d % width - width) or in c-like syntax (p0x + d % width < width ? d % width : d % width - width). see http://canonical.org/~kragen/sw/dev3/modpix.py
It especially needs to hold, given how often overlooked negative numbers are when reasoning about programs.