3

Euclidean definition says,

Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b.

Based on below observation,

>>> -3 % -2   # Ideally it should be (-2 * 2) + 1
-1
>>> -3 % 2    # this looks fine, (-2 * 2) + 1 
1
>>> 2 % -3    # Ideally it should be (-3 * 0) + 2
-1

looks like the % operator is running with different rules.

  • link1 was not helpful,
  • link2 gives recursive answer, because, as I do not understand how % works, it is difficult to understand How (a // b) * b + (a % b) == a works

My question:

How do I understand the behavior of modulo operator in python? Am not aware of any other language with respect to the working of % operator.

Community
  • 1
  • 1
overexchange
  • 15,768
  • 30
  • 152
  • 347
  • to know whats going on, look at the `divmod` function. That gives you the devision and modulo of two numbers at the same time. integer division in python is always the division rounded to the next smaller integer. So -3 / -2 is 1.5 rounded to 1, with -1 left as modulo. – Daniel Jul 20 '14 at 08:54
  • @jonrsharpe [link1](http://stackoverflow.com/questions/3883004/negative-numbers-modulo-in-python) was not helpful, [link2](http://stackoverflow.com/questions/10063546/modulo-for-negative-dividends-in-python?rq=1) gives recursive answer, Because, As i do not understand How % works, How can i understand `(a // b) * b + (a % b) == a` works? despite this is in format of bq+r? – overexchange Jul 20 '14 at 09:57
  • I'm not sure this is a duplicate: the linked questions are mostly about negative *dividends*, not negative *divisors*. The OP seems to be already happy with the behaviour for negative dividends. – Mark Dickinson Jul 20 '14 at 10:43
  • 2
    Just for the record, Python is closer to the definition you quoted than most other common programming languages. For positive _b_, it follows this defintion, whereas e.g. C++ and Java don't when _a_ is negative. – Sven Marnach Jul 20 '14 at 11:58

1 Answers1

5

The behaviour of integer division and modulo operations are explained in an article of The History of Python, namely: Why Python's Integer Division Floors . I'll quote the relevant parts:

if one of the operands is negative, the result is floored, i.e., rounded away from zero (towards negative infinity):

>>> -5//2
-3
>>> 5//-2
-3

This disturbs some people, but there is a good mathematical reason. The integer division operation (//) and its sibling, the modulo operation (%), go together and satisfy a nice mathematical relationship (all variables are integers):

a/b = q with remainder r

such that

b*q + r = a and 0 <= r < b

(assuming a and b are >= 0).

If you want the relationship to extend for negative a (keeping b positive), you have two choices: if you truncate q towards zero, r will become negative, so that the invariant changes to 0 <= abs(r) otherwise, you can floor q towards negative infinity, and the invariant remains 0 <= r < b.

In mathematical number theory, mathematicians always prefer the latter choice (see e.g. Wikipedia). For Python, I made the same choice because there are some interesting applications of the modulo operation where the sign of a is uninteresting. [...] For negative b, by the way, everything just flips, and the invariant becomes:

0 >= r > b.

In other words python decided to break the euclidean definition in certain circumstances to obtain a better behaviour in the interesting cases. In particular negative a was considered interesting while negative b was not considered as such. This is a completely arbitrary choice, which is not shared between languages.

Note that many common programming languages (C,C++,Java,...) do not satisfy the euclidean invariant, often in more cases than python (e.g. even when b is positive). some of them don't even provide any guarantee about the sign of the remainder, leaving that detail as implementation defined.

As a side note: Haskell provides both kind of moduluses and divisions. The standard euclidean modulus and division are called rem and quot, while the floored division and "python style" modulus are called mod and div.

Bakuriu
  • 98,325
  • 22
  • 197
  • 231
  • 1
    Note that for positive `b`, Python's behaviour *is* perfectly consistent with the Euclidean division theorem as stated in the question, regardless of the sign of `a`. The OP's question appears to be about the behaviour for negative *divisors*, rather than the more usual question about negative *dividends*. – Mark Dickinson Jul 20 '14 at 11:55
  • 1
    @MarkDickinson This is addressed in the last paragraph: "For negative `b` everything just flips and the invariant becomes `0 >= r > b`". – Bakuriu Jul 20 '14 at 11:57
  • Yep. But your comment about Python breaking the Euclidean definition is misleading, IMO: it actually *agrees* with the Euclidean definition, in a situation where *many* other common languages (C99, Java, ...) don't. – Mark Dickinson Jul 20 '14 at 12:06
  • @MarkDickinson Yes but allowing `r < 0` makes the euclidean invariant false, even though only in a particular case. I'll add a remark about other languages. – Bakuriu Jul 20 '14 at 12:08
  • 1
    There's no particular canonical statement for the Euclidean algorithm for negative b, though. Out of three elementary number theory books I just checked, two restricted the statement to positive b and arbitrary a, while the third stated the theorem in the form "... 0 >= r > b for negative b". So allowing `r < 0` does not make the euclidean invariant false; it just doesn't agree with the *particular* choice of statement the OP made. – Mark Dickinson Jul 20 '14 at 12:19
  • 1
    @MarkDickinson The OP is probably quoting the definition from wikipedia. In particular the page about [Euclidean division](http://en.wikipedia.org/wiki/Euclidean_division). Note that in the page they *do* take into account negative `b`s and the algorithm provided *does* maintain the invariant (`r >= 0`) in all cases. – Bakuriu Jul 20 '14 at 12:33
  • 1
    Yep. Like I said, there's no canonical statement. Python *does not* break the Euclidean Algorithm definition. – Mark Dickinson Jul 20 '14 at 14:01
  • @MarkDickinson I agree with you. Also from Guido's word, apparently he doesn't think it breaks the Euclidean definition, he said *"... you can floor q towards negative infinity, and the invariant remains 0 <= r < b."* – Rick Jun 06 '23 at 01:54