Why Ruby and Python long division differs from GMP and Java BigInteger?

Question

I'm developing a Big Integer class(didactic purpose) and I have been using Ruby to generate test cases. My class fails in the following test:

a = -48197174570431531987668852939807674377435188974148779416366905274642031729688518691
b = 4322669160730708444058642850762359547515258361061655693150034467061
a / b = -11149864303351921    # Ruby answer

I could not find the bug in my code so I tried to verify the result with other tools and surprise :o.

GMP, Java BigInteger and my class coincides with this results:

11149864303351920
-11149864303351920

But Ruby and Python coincides with this:

-11149864303351921
11149864303351920

Can somebody explain why this behavior?, Please.

Answer 1

When the arguments to integer division are not both positive, a decision must be made for rounding of the quotient and sign of the remainder. GMP supports floor division (f_div...), ceiling division (c_div...), and truncating division (t_div...).

Using gmpy2 to access GMP via Python,

>>> import gmpy2
>>> a = -48197174570431531987668852939807674377435188974148779416366905274642031729688518691
>>> b = 4322669160730708444058642850762359547515258361061655693150034467061
>>> gmpy2.f_divmod(a,b)
(mpz(-11149864303351921), mpz(1542354793066875276328139562907995977816446564586050094773477055490))
>>> gmpy2.c_divmod(a,b)
(mpz(-11149864303351920), mpz(-2780314367663833167730503287854363569698811796475605598376557411571))
>>> gmpy2.t_divmod(a,b)
(mpz(-11149864303351920), mpz(-2780314367663833167730503287854363569698811796475605598376557411571))
>>> help(gmpy2.f_divmod)
f_divmod(x, y) -> (quotient, remainder)

Return the quotient and remainder of x divided by y. The quotient
is rounded towards -Inf (floor rounding) and the remainder will
have the same sign as y. x and y must be integers.

>>> help(gmpy2.c_divmod)
c_divmod(x, y) -> (quotient, remainder)

Return the quotient and remainder of x divided by y. The quotient
is rounded towards +Inf (ceiling rounding) and the remainder will
have the opposite sign of y. x and y must be integers.

>>> help(gmpy2.t_divmod)
t_divmod(x, y) -> (quotient, remainder)

Return the quotient and remainder of x divided by y. The quotient
is rounded towards zero (truncation) and the remainder will have
the same sign as x. x and y must be integers.

Answer 2

the issue is with integer division. python 2.x (and, I assume, ruby, though I'm not an expert there) do integer division by default. if you do this in python:

from __future__ import division

a = -48197174570431531987668852939807674377435188974148779416366905274642031729688518691
b = 4322669160730708444058642850762359547515258361061655693150034467061

print int(a/b)

you'll see the answer you're expecting.

note that this behaviour is default in python 3+, and that the from __future__ import is only available in python 2.2+.

Here's some more info. on integer division, courtesy of Wikipedia :)

edit:

As Steve Rumbalski points out, the significant difference is the way in which the rounding takes place. Python's integer division rounds towards negative infinity, instead of towards zero (such that -0.2 becomes -1). Forcing floating point ("true") division and then casting to int at the end, as I have done above, means that the rounding is done differently, and that's why my example above gets the "correct" answer.