Why Python's integer division floors (2010)(python-history.blogspot.com) |
Why Python's integer division floors (2010)(python-history.blogspot.com) |
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.
Modulus doesn’t. I believe that algebraically equality module N can exist without division
"operator" is being used as a term of art in programming language design, to describe a symbol used to indicate that an operation should be performed on one or more operands.
https://en.wikipedia.org/wiki/Operator_(computer_programming...
So the "%" symbol is an operator in C and Python, and it is standard usage to describe the operator that performs a mathematical function "X" as the "X operator".
A triple equal sign is usually used for modular equations. That triple equal sign, together with the (mod N) out to the right, constitute an operator.
-1 ≡ 9 (mod 10)
Since it is written as part of the syntax of a formula or equation, and modifies its semantics, it is an operator. Just like d/dx, sigma notation and whatever not.
\1 samples have new coords relative to cell left edge and bottom edge.
We're interested in sample distance from "classic" first quadrant axis.
We're pooling, combining channel layers, making representative central 'blobs', we're interested in cell sample positions relative to the centre point of the cell.
This, of course, generalises to 3D and higher dimensions.
There are also CPUs that do "saturating arithmetic" where overflow results in INT_MAX instead of wrapping.
> PS. Note that I am using // instead of / -- this is Python 3 syntax
Edit: From what I can tell, standardised in Fortran 90, presumably older than that.
http://python-history.blogspot.com/2010/08/why-pythons-integ...
On a more serious note, there are quite reasonable properties that are satisfied by keeping the sign of the first argument as the chosen representative. In particular, for any two nonzero integers a and b, we have that:
a = (a / b) * b + (a mod b)
Where division should be interpreted as integer division that rounds towards zero. If a=-1 and b=3, then (a/b) would be zero which would require (a mod b) to be -1 if we want the above to hold. Also note that other rounding choices (e.g., rounding towards negative infinity) could impose (a mod b) = 2.
So choosing a particular representative comes down to choosing what properties you want your function to have in relation to other arithmetic.
... and that's exactly why the C modulo operator sucks.
The usual floating point behavior of having signed zero (+0 and -0) is not enough for this to be correct. You would also need a normal proper unsigned absolute 0 as well. Then you could give +inf for division with +0 and -inf for division with -0 and error or nan with division by the absolute (unsigned) 0. As far as I understand there is no unsigned 0 in IEEE 754, 0 is +0, so in reality it is always signed.
still, it would have real pitfalls if numerical algorithms that give right answers in every other programming language gave subtly wrong answers in python (raising a division-by-zero exception is less troublesome)
Like most surprising features in python, it would be terribly annoying if it didn't. Especially since you couldn't make sure the argument to the function you're writing wasn't a float. At that time, anyway.
With your change, you calculate 1 // 0 instead, which crashes.
That said, I think checking isinstance(x, float) was always possible. (And nowadays, you can put a type annotation.)
> When exceptional situations need attention, they can be examined immediately via traps or at a convenient time via status flags. Traps can be used to stop a program, but unrecoverable situations are extremely rare.
you know quite a bit about cpus. do you know of any ieee-754 cpus that trap on floating-point division by zero by default? is there a way to configure commonly-used cpus to do so?
Signaling NaNs (sNaN) are the only form of "signaling" that I am aware of, and sNaNs are just set up to trigger an "invalid operation" exception. I believe the idea is that an operation raises an sNaN when it creates a NaN, and a subsequent operation can catch it and issue the exception so you can figure out exactly where the calculation went wrong. If you ignore that exception, the sNaN becomes a quiet NaN (qNaN) and propagates.
The idea of traps have been written out of the standard in favor of exceptions. Traps had a defined behavior, which is what you would expect as an "exception" in most programming languages. A sibling comment indicated how to enable the FP exceptions as CPU interrupts, which become OS traps, and then become exceptions in Python/Java/C++ (any language with exceptions). Totally not confusing terminology at all.
I don't know off the top of my head of any architecture that treats all the exceptions in this way by default. One of the other exceptions is "inexact" which comes up on many calculations. I don't think you would want that to generally cause a CPU interrupt. Most implementations dump the exceptions as flags into a status register and let you see what happened if you care.
// Demonstrate C99/glibc 2.2+ feenableexcept
#define _GNU_SOURCE
#include <math.h>
#include <fenv.h>
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv)
{
if (argc != 3) {
fprintf(stderr, "Usage: %s a b # floating-point divide a by b\n", argv[0]);
return 1;
}
feenableexcept(FE_DIVBYZERO);
double a = atof(argv[1]), b = atof(argv[2]);
printf("%g ÷ %g = %g\n", a, b, a/b);
return 0;
}
- Some people really do want 1/(-x) to be negative infinity when a positive x reaches underflow. This helps with some kinds of numerical simulations since it can preserve the sign bit through underflow.
- Interval arithmetic implementations need to be able to disambiguate closed and open intervals at 0.
If you turn on fast math mode, you can also essentially disable the special treatment of the zeros.
1 / +0 == +inf
1 / -0 == -inf
1 / 0 == nan
abs(-0) == 0