Integer dicision

[Mark Wooding]

bdsatish <bdsatish at gmail.com> wrote:
> How does (a/b) work when both 'a' and 'b' are pure integers ?
>
>>> (9/2)
> 4
>
>>> (-9/2)
> -5
>
> Why is it -5 ? I expect it to be -4 ? Because, in C/C++, 9/2 is 4 and
> so negative of it, (-9/2) is -4.

Some background on the situation:

Integer division and remainder operators have to satisfy two axioms:

  y * (x/y) + x%y = x

and

  |x%y| < |y|

(The former is just the definition of remainder, and the latter is
necessary to get Euclid's algorithm to work.)  When x and y are both
nonnegative it's easy to agree on the right behaviour.  When x or y is
negative then we get conflicting requirements.

On the one hand, you get people who expect that (-x)/y == -(x/y).

On the other hand, you get people who expect 0 <= x%y < y if y >= 0.

Unfortunately, you can't have both and still satisfy the integer-
division axioms.  C89 didn't specify which behaviour you got.  C99 is in
the first camp.  Python picked the second (long before C99 came out).

Which is right?  I don't think that's actually a well-posed question:
both have uses.  I certainly find myself using the latter behaviour
(floor, or round towards -infinity) almost exclusively, but then I'm
mainly doing number theory and cryptography, and I find the bounds on
the remainder very convenient.

Heedful of this mess, Common Lisp provides four (!) different integer
division functions (in addition to `/', which does exact rational
division on integers):

  * (floor X Y) -> Q R, where Q is the largest integer such that Q <=
    X/Y, and R = X - Q Y; R is also available as (mod X Y).

  * (ceiling X Y) -> Q R, where Q is the smallest integer such that Q >=
    X/Y, and R = X - Q Y.

  * (truncate X Y) -> Q R, where Q is the integer with the greatest
    magnitude such that Q has the same sign as X/Y (or is zero) and |Q|
    <= |X/Y|; again R = X - Q Y; R is also available as (rem X Y).

  * (round X Y) -> Q R, where Q is the nearest integer to X/Y (rounding
    ties towards even numbers), and R = X - Q Y.

Gluing all this into Python is tricky, partly because the plethora of
options seems somewhat unPythonic (at least to me), and partly because
it relies on Common Lisp's behaviour of throwing away unwanted
additional return values.

> What should I do to get C-like behavior ?

I would have said

  abs(x) / abs(y) * sgn(x) * sgn(y)

but Python doesn't seem to have a signum function. :-(

I'd recommend thinking carefully about your problem and seeing whether
the existing floor-divide behaviour can't be made to fit (or indeed if
it's not actually better anyway).  If that still doesn't help then
you'll have to solve the problem the hard way.

def trunc_divmod(x, y):
  """
  Return truncating quotient and remainder for X/Y.

  Assumes Y > 0.
  """
  q, r = divmod(x, y)
  if x < 0 and r != 0:
    r -= y
    q += 1
  return q, r

-- [mdw]