A modulo operator consistent with euclidean division.
Howdy python gang, First time posting here ~ I've recently encountered that python does not have an OOTB operator for modulo that is consistent with Euclidean division. Although it should be easy for anyone who wants this to create it themselves, it struck me as odd that it was not an already included feature. I was even more shocked to see a list indicating that most languages don't include one consister with Euclidean division (disheartening to realise that the number theory way of doing things is not the default). I was so shocked at it's lack from python that it motivated me to post this, I suppose! I guess I'm posting to check how open anyone would be to the idea? I'm not sure if '%%' is defined anywhere, but it seemed like an intuitive suggestion if not already used as an operator, parallel to the syntax of the '**' operator. Keen to know how open y'all're to it!
Can you give some examples of how it would be used differently than the current modulo operator and what value it would bring? For those who have not taken number theory courses in a long time (or never!) it's not clear how this would be useful for Python. Damian (he/him) On Fri, Mar 18, 2022 at 11:10 AM Nathan Levett <nathan.levett.93@gmail.com> wrote:
On Fri, Mar 18, 2022 at 12:09 PM Nathan Levett <nathan.levett.93@gmail.com> wrote:
Are you referring to something different than the divmod builtin?
help(divmod) Help on built-in function divmod in module builtins:
divmod(x, y, /) Return the tuple (x//y, x%y). Invariant: div*y + mod == x. André
Are you speaking of how to generalize modulo to negative numbers (about which programming languages vary)? The bar for adding new syntax to Python is VERY high. Probably easier is getting a function in the `math` module. But even there, you'll need to explain what behavior you want AND why that behavior is sufficiently commonly wanted to warrant inclusion in the stdlib. What are the use cases you have in mind? On Fri, Mar 18, 2022, 11:10 AM Nathan Levett <nathan.levett.93@gmail.com> wrote:
On Sat, 19 Mar 2022 at 02:09, Nathan Levett <nathan.levett.93@gmail.com> wrote:
Given that you're clearly not talking about the default division operator, nor the divmod function (which I believe performs the precise same operation, I'm guessing you're talking about the way this behaves with negative numbers? As far as I know, there's only one sane way to interpret a//b, a%b where a and b are both positive integers, so either negative numbers or non-integers must be involved here. In general, if the divisor is a positive integer, you will always get a remainder that is in range(divisor), which is a very useful feature. Not all languages behave the same way here; for instance, -7%3 is 2 in Python, but -1 in JavaScript. I'm not sure which one you'd prefer, but my understanding of Wikipedia on the subject is that it agrees with Python and not JavaScript. If the divisor is negative, Python (and many languages) will give a negative remainder, thus ensuring that the remainder is between zero and the divisor. Is this the part you're disputing? Honestly, it's not something that I've ever had any reason to question, but I could well imagine it'd be useful both ways. To get the opposite behaviour, all you'd have to do is, when the divisor is negative, flip its sign, then flip the sign of its quotient: def divmod_the_other_way(x, y): if y < 0: return -(x // -y), x % y return x // y, x % y As David Mertz points out, it would be VERY difficult to add this as a syntactic feature (especially since it doesn't really extend to other data types), but a variant divmod function in the math module would be doable if there's enough justification for it. ChrisA
On Sat, 19 Mar 2022 at 07:16, Ben Rudiak-Gould <benrudiak@gmail.com> wrote:
Hmm. According to Wikipedia [1] the result of divmod(7,-3) should be (-2, 1) and divmod(-7, -3) should be (3, 2). So yes, looks like I messed it up. In any case, it would need some proper unit tests to make sure it's mathematically correct, but it'll be this simple whichever way it is. ChrisA [1] https://en.wikipedia.org/wiki/Euclidean_division#Examples
[Nathan Levett <nathan.levett.93@gmail.com>]
You need to be very explicit about what you intend - my best guess about what you intend isn't supported directly by any programming language I'm aware of. Most languages have notions of "integer division" (intdiv) and "integer modulus" (intmod) connected by this identity when the divisor (`b`) isn't 0: a = intdiv(a, b) * b + intmod(a,, b) That's so in Python too. Pick what you want intdiv to do, and the meaning of intmod is forced to match. Likewise you can pick what intmod should do, and that forces the meaning of intdiv. Most languages pick "I want intdiv(a, b) to return the infinitely precise value a/b, truncated to the integer closest to 0". While "classic C" didn't ;require that, the current C standards do. As a result, "a % b" in current C has the same sign as `a`. Python much wanted instead for intmod(a, b) to be >= 0 whenever b > 0. IOW, for intmod(a, b) to have the same sign as `b`. That corresponds to intdiv(a,b) returning the floor of the infinitely precise a/b. Another choice is made by math.remainder:
That's required by some standards, and corresponds to rounding the infinitely precise a/b to the closest integer (which in turn corresponds to intmod returning the element of a's modular equivalence class with minimum absolute value). What I'm _guessing_ you mean by "Euclidean division" is that 0 <= divmod(a,b) < abs(b) That is, the modulus is always non-negative, regardless of the inputs' signs. I expect no languages implement that because: (a) there's no particularly compelling use for it ;-) ; and, (b) it leads to a strained definition of intdiv ("return the floor of a/b if b > 0, but return the ceiling of a/b if b < 0).
..;. Keen to know how open y'all're to it!
I'm not. I've done a fair amount of number-theory-ish stuff in Python, and can't recall ever having a use for it. I've VERY often relied on that a%b is non-negative when b > 0, but have almost never had a real use for a negative modulus (`b`).
On Fri, Mar 18, 2022 at 04:26:54PM -0500, Tim Peters wrote:
Alas, math.remainder goes through float:
It would be nice if remainder() worked properly for exact values, without overflow or rounding errors.
I don't know whether this counts as compelling or not, but I have a divmod variant which returns an always positive modulus for use in base conversion. It is only used in one place in a module I haven't touched in a decade, so it is quite possible that if I were writing that code again today, I wouldn't do it that way. -- Steve
[Steven D'Aprano <steve@pearwood.info>[\
You mean -1 here: remainder() returns a member of the equivalence class with least absolute value, and abs(-1) < abs(2).
It would be nice if remainder() worked properly for exact values, without overflow or rounding errors.
I don't think so, It's required by 754-like standards explicitly for floating-point values. In that way, it's much too like math.fmod:
That's intended. And, of course, so is this:
math.remainder(10**300, 100) -40.0
It's far more important that remainder() work similarly to fmod() than that remainder() implement some bigint function nobody wants ;-) Seriously, modulus for floating point is overwhelmingly used as part of argument-reduction steps. Indeed, almost the entire actual point to it is that 0 <= remainder(x, y) <= abs(y) / 2.0 so that it leaves behind "a remainder" of magnitude as small as possible, which in floating point algorithms can greatly speed convergence of following approximations.
Insufficient information to guess from here. If; you're mucking around with negative bases, no, I expect that's too exceedingly niche to count as compelling. But if you're doing % with a positive base, the % result Python returns right now is already always non-negative.
On Fri, Mar 18, 2022 at 11:16:47PM -0500, Tim Peters wrote:
Correction noted. You said that before, and I skimmed over it. Sorry.
Sure, for floats. I certainly wouldn't want to change the behaviour for floats. We could change the behaviour for ints (or at least we could if not constrained by backwards compatibility) or add a new function. I was thinking more of Julia's rem(), which uses the sign of the dividend rather than the divisor. Speaking of which, Julia gives the correct result with no rounding error, but you have to declare your intermediate results as BigInts: julia> rem(big"3"^500, 3) 0
"Intended" is a little strong. I don't think that anyone set out to design a numeric system where an exact multiple of 100 gives a remainder of 60 when divided by 100 :-) Its more of an unavoidable consequence of other decisions, such as the use of base-2 rather than decimal, and limiting floats to 64 bits.
Have you been spying on me again??? :-) -- Steve
[Steven D'Aprano <steve@pearwood.info>]
We could - but why would we? Just because a thing _can_ be done is no argument in fa\vor of doing so.
I was thinking more of Julia's rem(), which uses the sign of the dividend rather than the divisor.
Which is what most languages do (like also the current standards for C, C++, and Fortran; also what math.fmod() does). It's the natural result when using truncating division, and the latter is what _really_ drives it in most languages. They want integer division to truncate. "% (however spelled) returns the sign of the dividend" then _follows_ from preserving the identity: a = intdiv(a, b) * b + intmod(a, b) as already covered. (math.fmod() has a different motivation: so that x % y is always exact.) In Python, it's the opposite: the desire for intmod(a, b) to be positive when b is positive drove that integer division returns floor. As usual, if you want :"everything", install gmpy2 instead. mpz has 27(!) functions devoted to computing integer divisions and mods: https://gmplib.org/manual/Integer-Division The ones for unsigned ints aren't wrapped by gmpy2, since Python has no such distinct data type. The rest support your choice of truncating, floor, or ceiling division. However, not even mpz supports what the OP here appeared to want (non-negative mod regardless of inputs' signs). And neither does it support rounding division (which remainder() re\lies on). If something didn't even make it into mpz, it's a pretty safe bet that there's no compelling use case for it. Note that there are strong use cases for remainder() in the float world, but floats aren't ints.
On Sat, Mar 19, 2022 at 03:49:28PM -0500, Tim Peters wrote:
You answer your own question:
Exactly. The fact is, that about half the time I use Python's mod with negative values, I get the result I don't want. That tells me that sometimes I want `%` and sometimes I want something else. Truth be told, I'm not absolutely sure that what I want is Julia's rem(), if this discussion got serious enough to write a PEP I would investigate more closely. But I doubt it will get that far. More likely I will just mine this discussion thread for good ideas, and write my own remainder function(s) once I decide precisely what I need. [...]
However, not even mpz supports what the OP here appeared to want (non-negative mod regardless of inputs' signs).
The OP hasn't told us what he actually wants, he's just dropped hints and left us to infer what he wants and hope that we got it right. -- Steve
Hi Nathan, and welcome! On Fri, Mar 18, 2022 at 05:13:16AM -0000, Nathan Levett wrote:
Your post would be more persuasive if you: * explained how Python's modulo is not consistent with Euclidean division; * defined what definition of modulo is "the number theory way of doing things"; * told us what languages you have found that do include this version of modulo. I'm not sure what part of number theory you are referring to. You should explain, since its not obvious. I've just grabbed one of my text books, and it doesn't even define a modulo operator. It only defines modulo arithmetic, as in: a is congruent to b mod m if m∣(a-b) with a, b, m ∈ ℤ and m non-negative. where ∣ is "divides". Although both a and b may be negative, not one of the examples or exercises include examples where they are negative. Wolfram language (Mathematica) define their Mod[a, b] function: a mod b = a - b*floor(a/b) which for real-valued a, b gives the result with the same sign as b. https://functions.wolfram.com/IntegerFunctions/Mod/ That, I believe, makes it the same as Python's % operator. Ada has two functions, mod() and rem(). I believe that mod(a, b) is the same as Python's a%b, while rem(a, b) takes the sign of a rather than the sign of b. http://archive.adaic.com/standards/83lrm/html/lrm-04-05.html#4.5.5 Julia has the same: https://docs.julialang.org/en/v1/manual/mathematical-operations/#Division-fu... -- Steve
On Fri, Mar 18, 2022 at 8:30 PM MRAB <python@mrabarnett.plus.com> wrote:
That convention in the Wikipedia article dates back to a 2004 edit by an anonymous (IP) editor. The only reference in that version was to a course handout that only considered positive denominators. There's nothing wrong with the convention, but I'm suspicious of the idea that it's a widespread standard of some sort. I've never heard of it before.
Has anyone in this thread linked this blog post yet? http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floo... Much is a rehash of this thread but for completeness it might be useful to read Guido van Rossum's thoughts and the subsequent discussion in the comments section. @Tim I believe you are mentioned at the bottom of the post. Om ---- On Sun, 20 Mar 2022 01:53:51 -0500 Ben Rudiak-Gould <benrudiak@gmail.com> wrote ----
We feel like this may make sense to bring up, too: https://rust-lang.github.io/rfcs/2169-euclidean-modulo.html On 2022-03-20 04:06, Om Joshi wrote:
Can you give some examples of how it would be used differently than the current modulo operator and what value it would bring? For those who have not taken number theory courses in a long time (or never!) it's not clear how this would be useful for Python. Damian (he/him) On Fri, Mar 18, 2022 at 11:10 AM Nathan Levett <nathan.levett.93@gmail.com> wrote:
On Fri, Mar 18, 2022 at 12:09 PM Nathan Levett <nathan.levett.93@gmail.com> wrote:
Are you referring to something different than the divmod builtin?
help(divmod) Help on built-in function divmod in module builtins:
divmod(x, y, /) Return the tuple (x//y, x%y). Invariant: div*y + mod == x. André
Are you speaking of how to generalize modulo to negative numbers (about which programming languages vary)? The bar for adding new syntax to Python is VERY high. Probably easier is getting a function in the `math` module. But even there, you'll need to explain what behavior you want AND why that behavior is sufficiently commonly wanted to warrant inclusion in the stdlib. What are the use cases you have in mind? On Fri, Mar 18, 2022, 11:10 AM Nathan Levett <nathan.levett.93@gmail.com> wrote:
On Sat, 19 Mar 2022 at 02:09, Nathan Levett <nathan.levett.93@gmail.com> wrote:
Given that you're clearly not talking about the default division operator, nor the divmod function (which I believe performs the precise same operation, I'm guessing you're talking about the way this behaves with negative numbers? As far as I know, there's only one sane way to interpret a//b, a%b where a and b are both positive integers, so either negative numbers or non-integers must be involved here. In general, if the divisor is a positive integer, you will always get a remainder that is in range(divisor), which is a very useful feature. Not all languages behave the same way here; for instance, -7%3 is 2 in Python, but -1 in JavaScript. I'm not sure which one you'd prefer, but my understanding of Wikipedia on the subject is that it agrees with Python and not JavaScript. If the divisor is negative, Python (and many languages) will give a negative remainder, thus ensuring that the remainder is between zero and the divisor. Is this the part you're disputing? Honestly, it's not something that I've ever had any reason to question, but I could well imagine it'd be useful both ways. To get the opposite behaviour, all you'd have to do is, when the divisor is negative, flip its sign, then flip the sign of its quotient: def divmod_the_other_way(x, y): if y < 0: return -(x // -y), x % y return x // y, x % y As David Mertz points out, it would be VERY difficult to add this as a syntactic feature (especially since it doesn't really extend to other data types), but a variant divmod function in the math module would be doable if there's enough justification for it. ChrisA
On Sat, 19 Mar 2022 at 07:16, Ben Rudiak-Gould <benrudiak@gmail.com> wrote:
Hmm. According to Wikipedia [1] the result of divmod(7,-3) should be (-2, 1) and divmod(-7, -3) should be (3, 2). So yes, looks like I messed it up. In any case, it would need some proper unit tests to make sure it's mathematically correct, but it'll be this simple whichever way it is. ChrisA [1] https://en.wikipedia.org/wiki/Euclidean_division#Examples
[Nathan Levett <nathan.levett.93@gmail.com>]
You need to be very explicit about what you intend - my best guess about what you intend isn't supported directly by any programming language I'm aware of. Most languages have notions of "integer division" (intdiv) and "integer modulus" (intmod) connected by this identity when the divisor (`b`) isn't 0: a = intdiv(a, b) * b + intmod(a,, b) That's so in Python too. Pick what you want intdiv to do, and the meaning of intmod is forced to match. Likewise you can pick what intmod should do, and that forces the meaning of intdiv. Most languages pick "I want intdiv(a, b) to return the infinitely precise value a/b, truncated to the integer closest to 0". While "classic C" didn't ;require that, the current C standards do. As a result, "a % b" in current C has the same sign as `a`. Python much wanted instead for intmod(a, b) to be >= 0 whenever b > 0. IOW, for intmod(a, b) to have the same sign as `b`. That corresponds to intdiv(a,b) returning the floor of the infinitely precise a/b. Another choice is made by math.remainder:
That's required by some standards, and corresponds to rounding the infinitely precise a/b to the closest integer (which in turn corresponds to intmod returning the element of a's modular equivalence class with minimum absolute value). What I'm _guessing_ you mean by "Euclidean division" is that 0 <= divmod(a,b) < abs(b) That is, the modulus is always non-negative, regardless of the inputs' signs. I expect no languages implement that because: (a) there's no particularly compelling use for it ;-) ; and, (b) it leads to a strained definition of intdiv ("return the floor of a/b if b > 0, but return the ceiling of a/b if b < 0).
..;. Keen to know how open y'all're to it!
I'm not. I've done a fair amount of number-theory-ish stuff in Python, and can't recall ever having a use for it. I've VERY often relied on that a%b is non-negative when b > 0, but have almost never had a real use for a negative modulus (`b`).
On Fri, Mar 18, 2022 at 04:26:54PM -0500, Tim Peters wrote:
Alas, math.remainder goes through float:
It would be nice if remainder() worked properly for exact values, without overflow or rounding errors.
I don't know whether this counts as compelling or not, but I have a divmod variant which returns an always positive modulus for use in base conversion. It is only used in one place in a module I haven't touched in a decade, so it is quite possible that if I were writing that code again today, I wouldn't do it that way. -- Steve
[Steven D'Aprano <steve@pearwood.info>[\
You mean -1 here: remainder() returns a member of the equivalence class with least absolute value, and abs(-1) < abs(2).
It would be nice if remainder() worked properly for exact values, without overflow or rounding errors.
I don't think so, It's required by 754-like standards explicitly for floating-point values. In that way, it's much too like math.fmod:
That's intended. And, of course, so is this:
math.remainder(10**300, 100) -40.0
It's far more important that remainder() work similarly to fmod() than that remainder() implement some bigint function nobody wants ;-) Seriously, modulus for floating point is overwhelmingly used as part of argument-reduction steps. Indeed, almost the entire actual point to it is that 0 <= remainder(x, y) <= abs(y) / 2.0 so that it leaves behind "a remainder" of magnitude as small as possible, which in floating point algorithms can greatly speed convergence of following approximations.
Insufficient information to guess from here. If; you're mucking around with negative bases, no, I expect that's too exceedingly niche to count as compelling. But if you're doing % with a positive base, the % result Python returns right now is already always non-negative.
On Fri, Mar 18, 2022 at 11:16:47PM -0500, Tim Peters wrote:
Correction noted. You said that before, and I skimmed over it. Sorry.
Sure, for floats. I certainly wouldn't want to change the behaviour for floats. We could change the behaviour for ints (or at least we could if not constrained by backwards compatibility) or add a new function. I was thinking more of Julia's rem(), which uses the sign of the dividend rather than the divisor. Speaking of which, Julia gives the correct result with no rounding error, but you have to declare your intermediate results as BigInts: julia> rem(big"3"^500, 3) 0
"Intended" is a little strong. I don't think that anyone set out to design a numeric system where an exact multiple of 100 gives a remainder of 60 when divided by 100 :-) Its more of an unavoidable consequence of other decisions, such as the use of base-2 rather than decimal, and limiting floats to 64 bits.
Have you been spying on me again??? :-) -- Steve
[Steven D'Aprano <steve@pearwood.info>]
We could - but why would we? Just because a thing _can_ be done is no argument in fa\vor of doing so.
I was thinking more of Julia's rem(), which uses the sign of the dividend rather than the divisor.
Which is what most languages do (like also the current standards for C, C++, and Fortran; also what math.fmod() does). It's the natural result when using truncating division, and the latter is what _really_ drives it in most languages. They want integer division to truncate. "% (however spelled) returns the sign of the dividend" then _follows_ from preserving the identity: a = intdiv(a, b) * b + intmod(a, b) as already covered. (math.fmod() has a different motivation: so that x % y is always exact.) In Python, it's the opposite: the desire for intmod(a, b) to be positive when b is positive drove that integer division returns floor. As usual, if you want :"everything", install gmpy2 instead. mpz has 27(!) functions devoted to computing integer divisions and mods: https://gmplib.org/manual/Integer-Division The ones for unsigned ints aren't wrapped by gmpy2, since Python has no such distinct data type. The rest support your choice of truncating, floor, or ceiling division. However, not even mpz supports what the OP here appeared to want (non-negative mod regardless of inputs' signs). And neither does it support rounding division (which remainder() re\lies on). If something didn't even make it into mpz, it's a pretty safe bet that there's no compelling use case for it. Note that there are strong use cases for remainder() in the float world, but floats aren't ints.
On Sat, Mar 19, 2022 at 03:49:28PM -0500, Tim Peters wrote:
You answer your own question:
Exactly. The fact is, that about half the time I use Python's mod with negative values, I get the result I don't want. That tells me that sometimes I want `%` and sometimes I want something else. Truth be told, I'm not absolutely sure that what I want is Julia's rem(), if this discussion got serious enough to write a PEP I would investigate more closely. But I doubt it will get that far. More likely I will just mine this discussion thread for good ideas, and write my own remainder function(s) once I decide precisely what I need. [...]
However, not even mpz supports what the OP here appeared to want (non-negative mod regardless of inputs' signs).
The OP hasn't told us what he actually wants, he's just dropped hints and left us to infer what he wants and hope that we got it right. -- Steve
Hi Nathan, and welcome! On Fri, Mar 18, 2022 at 05:13:16AM -0000, Nathan Levett wrote:
Your post would be more persuasive if you: * explained how Python's modulo is not consistent with Euclidean division; * defined what definition of modulo is "the number theory way of doing things"; * told us what languages you have found that do include this version of modulo. I'm not sure what part of number theory you are referring to. You should explain, since its not obvious. I've just grabbed one of my text books, and it doesn't even define a modulo operator. It only defines modulo arithmetic, as in: a is congruent to b mod m if m∣(a-b) with a, b, m ∈ ℤ and m non-negative. where ∣ is "divides". Although both a and b may be negative, not one of the examples or exercises include examples where they are negative. Wolfram language (Mathematica) define their Mod[a, b] function: a mod b = a - b*floor(a/b) which for real-valued a, b gives the result with the same sign as b. https://functions.wolfram.com/IntegerFunctions/Mod/ That, I believe, makes it the same as Python's % operator. Ada has two functions, mod() and rem(). I believe that mod(a, b) is the same as Python's a%b, while rem(a, b) takes the sign of a rather than the sign of b. http://archive.adaic.com/standards/83lrm/html/lrm-04-05.html#4.5.5 Julia has the same: https://docs.julialang.org/en/v1/manual/mathematical-operations/#Division-fu... -- Steve
On Fri, Mar 18, 2022 at 8:30 PM MRAB <python@mrabarnett.plus.com> wrote:
That convention in the Wikipedia article dates back to a 2004 edit by an anonymous (IP) editor. The only reference in that version was to a course handout that only considered positive denominators. There's nothing wrong with the convention, but I'm suspicious of the idea that it's a widespread standard of some sort. I've never heard of it before.
Has anyone in this thread linked this blog post yet? http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floo... Much is a rehash of this thread but for completeness it might be useful to read Guido van Rossum's thoughts and the subsequent discussion in the comments section. @Tim I believe you are mentioned at the bottom of the post. Om ---- On Sun, 20 Mar 2022 01:53:51 -0500 Ben Rudiak-Gould <benrudiak@gmail.com> wrote ----
We feel like this may make sense to bring up, too: https://rust-lang.github.io/rfcs/2169-euclidean-modulo.html On 2022-03-20 04:06, Om Joshi wrote:
participants (11)
-
André Roberge -
Ben Rudiak-Gould -
Chris Angelico -
Damian Shaw -
David Mertz, Ph.D. -
MRAB -
Nathan Levett -
Om Joshi -
Soni L. -
Steven D'Aprano -
Tim Peters