Integer math question

Discussion in 'Python' started by Frank, Jan 3, 2004.

  1. Frank

    Frank Guest

    Hi,

    can anybody help with the following problem?

    In C++

    i = 5 / 10 and
    i = -5 / 10 both have the same result 0.

    In python

    i = 5 / 10 gives me 0 as expected, but
    i = -5 / 10 gives -1 as result.

    Is this a feature or a bug? I remember Delphi gave me the same result as
    C++.

    TIA,
    Frank
    Frank, Jan 3, 2004
    #1
    1. Advertising

  2. Frank

    John Roth Guest

    "Frank" <-bremen.de> wrote in message
    news:...
    > Hi,
    >
    > can anybody help with the following problem?
    >
    > In C++
    >
    > i = 5 / 10 and
    > i = -5 / 10 both have the same result 0.
    >
    > In python
    >
    > i = 5 / 10 gives me 0 as expected, but
    > i = -5 / 10 gives -1 as result.
    >
    > Is this a feature or a bug? I remember Delphi gave me the same result as
    > C++.


    That's a feature. Integer division is explicitly defined in
    Python to do exactly that.

    The basic thing to remember is that the *correct*
    mathematical result of dividing one integer by
    another integer is a rational. Python does not
    have a rational data type, so it has to pick one
    of the multitude of possible ways of rounding a
    non-integral result to an integer.

    There is no universally right answer to this process:
    the "right" answer to any rounding problem is
    what the customer wants it to be.

    John Roth

    >
    > TIA,
    > Frank
    John Roth, Jan 3, 2004
    #2
    1. Advertising

  3. Frank

    Sean Ross Guest

    "Frank" <-bremen.de> wrote in message
    news:...
    > Hi,
    >
    > can anybody help with the following problem?
    >
    > In C++
    >
    > i = 5 / 10 and
    > i = -5 / 10 both have the same result 0.
    >
    > In python
    >
    > i = 5 / 10 gives me 0 as expected, but
    > i = -5 / 10 gives -1 as result.
    >
    > Is this a feature or a bug? I remember Delphi gave me the same result as
    > C++.
    >
    > TIA,
    > Frank



    Using the division algorithm:

    Let a,b be integers with b>0. Then there exist unique integers q and r such
    that:

    a = bq + r and 0<=r<b [1]

    If we let a=5 and b=10, then a/b is represented by [1] as

    a = bq + r
    5 = (10) q + r

    .... skipping some steps, we find that q=0 and r=5
    5 = 10(0) + 5
    5 = 0 + 5
    5 = 5
    LHS = RHS

    so, 5/10 = 0 in integer division (with no remainder).

    Now, let a = -5 and b = 10

    -5 = (10)q + r

    If we have q = -1, then

    -5 = (10)(-1) + r
    -5 = -10 + r

    Recall [1] above, 0 <= r < b. r must be nonnegative.
    In this case r=5,

    -5 = -10 + 5
    -5 = -5
    LHS = RHS

    So, q = -1, and r=5, in which case -5/10 = -1 in integer division (without
    remainder).

    Suppose we let q=0 for the second problem above. Then

    -5 = (10)(0) + r
    -5 = 0 + r
    -5 = r
    or
    r = -5

    But, by [1], r must be nonnegative. So, we have a contradiction. In which
    case we can say that q cannot equal 0 in the algorithm above.

    So, I suppose the answer to your question would be,

    "This is a feature - Python does it properly, where the others do not."

    HTH
    Sean
    Sean Ross, Jan 3, 2004
    #3
  4. Frank

    Sean Ross Guest

    "Sean Ross" <> wrote in message
    news:11EJb.20461$...
    >then a/b is represented by [1] as


    'represented' is the wrong word here, but hopefully, you get the idea ...
    Sean Ross, Jan 3, 2004
    #4
  5. Frank

    Sean Ross Guest

    Here's an interactive Python example to help clarify the previous response:

    >>> a = 5
    >>> b = 10
    >>> q , r = divmod(a,b)
    >>> q

    0
    >>> r

    5
    >>> a = -a
    >>> a

    -5
    >>> q , r = divmod(a,b)
    >>> q

    -1
    >>> r

    5
    >>> b*q + r # division algorithm

    -5
    >>> -5 == a

    True
    >>>
    Sean Ross, Jan 3, 2004
    #5
  6. Frank

    Rainer Deyke Guest

    Sean Ross wrote:
    > a = bq + r and 0<=r<b [1]


    But 0 <= r < b is a contradiction when b < 0.

    --
    Rainer Deyke - - http://eldwood.com
    Rainer Deyke, Jan 3, 2004
    #6
  7. Frank

    Sean Ross Guest

    "Rainer Deyke" <> wrote in message
    news:kTEJb.724242$HS4.5376202@attbi_s01...
    > Sean Ross wrote:
    > > a = bq + r and 0<=r<b [1]

    >
    > But 0 <= r < b is a contradiction when b < 0.
    >


    Right. But, the division algorithm states "Let a,b be integers with b>0"
    (which I mentioned in that post).
    Sean Ross, Jan 3, 2004
    #7
  8. Frank

    Sean Ross Guest

    "Rainer Deyke" <> wrote in message
    news:kTEJb.724242$HS4.5376202@attbi_s01...
    > Sean Ross wrote:
    > > a = bq + r and 0<=r<b [1]

    >
    > But 0 <= r < b is a contradiction when b < 0.
    >
    > --
    > Rainer Deyke - - http://eldwood.com
    >
    >


    Hmm....

    >>> a = 5
    >>> b = -10
    >>> q,r = divmod(a,b)
    >>> q

    -1
    >>> r

    -5
    >>>


    Here, the division algorithm does not apply (b is a negative integer).
    Perhaps there's some other theorem for this case?
    b<r<=0, when b < 0? I don't know.
    Sean Ross, Jan 3, 2004
    #8
  9. Frank

    Sean Ross Guest

    "Sean Ross" <> wrote in message
    news:5sFJb.20923$...
    > "Rainer Deyke" <> wrote in message
    > news:kTEJb.724242$HS4.5376202@attbi_s01...
    > >>> a = 5
    > >>> b = -10
    > >>> q,r = divmod(a,b)
    > >>> q

    > -1
    > >>> r

    > -5
    > >>>

    >
    > Here, the division algorithm does not apply (b is a negative integer).
    > Perhaps there's some other theorem for this case?
    > b<r<=0, when b < 0? I don't know.
    >


    I think you're supposed to do something like this
    a = bq + r, 0<= r < |b|
    5 = (-10)q + r
    -5 = -(-10)q - r
    -5 = 10q - r

    But, then, q would be 0 and r would be 5. <shrug>
    Sean Ross, Jan 3, 2004
    #9
  10. C rounds toward the nearest integer and Python rounds down. The behavior is
    consistent in each case.

    "Frank" <-bremen.de> wrote in message
    news:...
    | Hi,
    |
    | can anybody help with the following problem?
    |
    | In C++
    |
    | i = 5 / 10 and
    | i = -5 / 10 both have the same result 0.
    |
    | In python
    |
    | i = 5 / 10 gives me 0 as expected, but
    | i = -5 / 10 gives -1 as result.
    |
    | Is this a feature or a bug? I remember Delphi gave me the same result as
    | C++.
    |
    | TIA,
    | Frank
    Elaine Jackson, Jan 4, 2004
    #10
  11. Sorry, I should have said "C rounds toward zero". In other words, the result of
    casting x to integer type is sgn(x)*floor(abs(x)).

    "Elaine Jackson" <> wrote in message
    news:uEOJb.933787$pl3.753391@pd7tw3no...
    | C rounds toward the nearest integer and Python rounds down. The behavior is
    | consistent in each case.
    |
    | "Frank" <-bremen.de> wrote in message
    | news:...
    | | Hi,
    | |
    | | can anybody help with the following problem?
    | |
    | | In C++
    | |
    | | i = 5 / 10 and
    | | i = -5 / 10 both have the same result 0.
    | |
    | | In python
    | |
    | | i = 5 / 10 gives me 0 as expected, but
    | | i = -5 / 10 gives -1 as result.
    | |
    | | Is this a feature or a bug? I remember Delphi gave me the same result as
    | | C++.
    | |
    | | TIA,
    | | Frank
    |
    |
    Elaine Jackson, Jan 4, 2004
    #11
  12. On Sat, 3 Jan 2004 8:32:07 -0800, Frank wrote
    (in message <>):

    > In C++
    >
    > i = 5 / 10 and
    > i = -5 / 10 both have the same result 0.


    Actually this is implementation defined in C89 and standard C++. Either
    -5/10 == 0 and -5%10 == -5, as in your implementation, or -5/10 == -1
    and -5%10 == 5, like Python. In C99, and possibly a future version of
    C++, it's always done the first way (rounding towards zero).

    --
    Derek Ledbetter


    Heavy boots of lead
    fills his victims full of dread
    Running as fast as they can
    Iron Man lives again!
    Derek Ledbetter, Jan 4, 2004
    #12
  13. Frank

    Dan Bishop Guest

    -bremen.de (Frank) wrote in message news:<>...
    > Hi,
    >
    > can anybody help with the following problem?

    ....
    > i = 5 / 10 gives me 0 as expected, but
    > i = -5 / 10 gives -1 as result.


    The problem is that you aren't using "from __future__ import division"
    ;-) (This causes the results to be 0.5 and -0.5, and will be the
    default division semantics in Python 3.0. If you want integer
    division, use the // operator.)

    > Is this a feature or a bug?


    It's a feature. The advantage of defining x // y as floor(x / y) is
    that x % y is always nonnegative.

    As as example of why this is useful, consider the
    datetime.date.weekday method. This could be implemented as

    def weekday(self):
    return (self.fromordinal() - 1) % 7

    If the datetime module was changed to allow BC(E) dates (which have
    nonpositive Rata Die numbers), the weekday method would still work.
    In C++, you'd have to treat such dates as a special case.
    Dan Bishop, Jan 5, 2004
    #13
  14. |Thus Spake Sean Ross On the now historical date of Sat, 03 Jan 2004
    16:31:17 -0500|
    > I think you're supposed to do something like this a = bq + r, 0<= r <
    > |b|

    It is, indeed, 0 <= r < abs(b)

    "If a and b are integers such that b != 0, then there exist unique
    integers r and q such that a = q*b + r and 0 <= r < abs(b)"

    For non-mathematical spectators, the divmod() function is defined so that
    q, r = divmod(a, b) by the definition above.

    Sam Walters

    --
    Never forget the halloween documents.
    http://www.opensource.org/halloween/
    """ Where will Microsoft try to drag you today?
    Do you really want to go there?"""
    Samuel Walters, Jan 5, 2004
    #14
  15. Frank

    Sean Ross Guest

    "Samuel Walters" <> wrote in message
    news:p...
    > "If a and b are integers such that b != 0, then there exist unique
    > integers r and q such that a = q*b + r and 0 <= r < abs(b)"
    >
    > For non-mathematical spectators, the divmod() function is defined so that
    > q, r = divmod(a, b) by the definition above.


    Right. The only thing that was still mildly interesting to me was why does
    divmod() return a negative remainder?

    >>> a = 5
    >>> b = -10
    >>> q,r = divmod(a,b)
    >>> q

    -1
    >>> r

    -5

    If divmod() where defined based on the definition above, then divmod(5, -10)
    should return (0, 5).
    Well ... that's too strong. The above is a theorem - it doesn't say
    remainders have to be nonnegative,
    it only says that there exist yada yada yada ... whatever, I'm not that
    interested.
    Sean Ross, Jan 6, 2004
    #15
  16. Frank

    Sean Ross Guest

    "Dan Bishop" <> wrote in message
    news:...
    > It's a feature. The advantage of defining x // y as floor(x / y) is
    > that x % y is always nonnegative.


    Sorry, but x%y can be negative in Python:

    >>> x, y = 5, -10
    >>> x%y

    -5
    Sean Ross, Jan 6, 2004
    #16
  17. On 3 Jan 2004 08:32:07 -0800, -bremen.de (Frank) wrote:

    >Hi,
    >
    >can anybody help with the following problem?
    >
    >In C++
    >
    >i = 5 / 10 and
    >i = -5 / 10 both have the same result 0.
    >
    >In python
    >
    >i = 5 / 10 gives me 0 as expected, but
    >i = -5 / 10 gives -1 as result.
    >
    >Is this a feature or a bug? I remember Delphi gave me the same result as
    >C++.

    It is a feature. Python does the more useful thing IMO.
    If you look on / (or now //) as a denominator-defined mapping
    of integer intervals to integers, it is clearer.

    I.e., the mappings that python implements are

    [denom*k, denom*k+denom) => k for denom >0
    and
    [denom*k+denom, denom*k) => k for denom <0


    The C version is ugly, because it maps a unique extra-sized interval
    around zero to zero, i.e., for denom>0

    [-denom+1, denom) => 0

    which contains 2*denom-1 source integers, and all the rest of the
    intervals go symmetrically in both directions from there, containing
    denom integers. Python's source intervals are all the same size.


    ====< showintdiv.cpp >=====================================
    #include <stdio.h>
    #include <stdlib.h>
    void main(int argc, char* argv[]){
    if(argc<4){ printf("Usage: %s xlo xhi den\n", argv[0]); return; }
    int xlo = atoi(argv[1]);
    int xhi = atoi(argv[2]);
    int den = atoi(argv[3]);
    int x;
    for(x=xlo; x<xhi; ++x) printf("%3d", x); printf("\n");
    for(x=xlo; x<xhi; ++x) printf("%3d", x/den); printf("\n");
    }
    ===========================================================

    We'll do a weird printf JFTHOI and to match program lines better:

    ====< showintdiv.py >======================================
    printf = (lambda wso, fmt, *args: wso(fmt%args)).__get__(
    __import__('sys').stdout.write)

    def main(argv):
    if len(argv)<4: printf("Usage: %s xlo xhi den\n" % argv[0]); return
    xlo = int(argv[1])
    xhi = int(argv[2])
    den = int(argv[3])
    for x in xrange(xlo, xhi): printf("%3d", x)
    printf("\n");
    for x in xrange(xlo, xhi): printf("%3d", x/den)
    printf("\n");

    if __name__== '__main__':
    import sys
    main(sys.argv)
    ===========================================================


    Python maps successive equal sized intervals to successive integers from -inf to +inf

    [10:38] C:\pywk\clp>showintdiv.py -15 16 5
    -15-14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    -3 -3 -3 -3 -3 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3

    But C maps symmetrically across zero, causing 2*denom-1 points to map to zero

    [10:38] C:\pywk\clp>showintdiv.exe -15 16 5
    -15-14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    -3 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3

    With a negative denominator, python still maps successive intervals, but going the other
    direction from (and including) zero.

    [10:38] C:\pywk\clp>showintdiv.py -15 16 -5
    -15-14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    3 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 -1 -1 -1 -1 -1 -2 -2 -2 -2 -2 -3 -3 -3 -3 -3

    Whereas C is still symmetric with the 2n-1 points going to zero:

    [10:38] C:\pywk\clp>showintdiv.exe -15 16 -5
    -15-14-13-12-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    3 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -2 -2 -2 -2 -2 -3

    The extra-sized interval across zero makes for a hiccup in the use of the mapping as a function.
    E.g., you can't translate the input by k*denom and get a uniformly translated (by k) output
    unless you stay away from the zero interval.

    Ok, back to the grind...

    Regards,
    Bengt Richter
    Bengt Richter, Jan 8, 2004
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?ISO-8859-1?Q?Thomas_Gagn=E9?=

    No Math.min(Integer, Integer)?

    =?ISO-8859-1?Q?Thomas_Gagn=E9?=, Jul 29, 2003, in forum: Java
    Replies:
    0
    Views:
    502
    =?ISO-8859-1?Q?Thomas_Gagn=E9?=
    Jul 29, 2003
  2. chirs
    Replies:
    18
    Views:
    763
    Chris Uppal
    Mar 2, 2004
  3. AciD_X
    Replies:
    4
    Views:
    8,097
    Jonathan Turkanis
    Apr 1, 2004
  4. Mark Healey
    Replies:
    7
    Views:
    1,479
    Tim Prince
    May 22, 2006
  5. VK
    Replies:
    15
    Views:
    1,160
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page