Integer math question

[Bengt Richter]

On 3 Jan 2004 08:32:07 -0800, mersmann at szut.uni-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