What's the underlying implimentation of integer division in python?

Question

I am running python 3.7.3

Regarding the integer division operator: "//" (double divide, double forward slash, double division operator? I'm not sure the exact name.)

It does not seem to give consistent results, and many of the explanations I've found don't fully explain its results.

Here[What is the reason for having '//' in Python? (and other places) it's said that the "//" operator gives the quotient without the remainder. As if a // b is the same as floor(a / b) (or rounding up if a / b is negative).

However, sometimes it does not give that answer. For example,1 // 0.2 evaluates to 4. However 1 / 0.2 returns 5, and math.floor(1 / 2) also returns 5. It's giving a number one less than what integer division should. The // operator returns a 5 if you divide 10 by 2, but 1 divided 0.2 does not work correctly.

This problem comes up other times I use the // operator to divide floating point numbers. Like 5 // 0.2 or 100 // 0.2. I don't know if this is some quirk of floating point arithmetic, but these problems seem to go away if you type math.floor(5 / 0.2) (or any other set of numbers giving issues). Except when you divide negative numbers, in which case you have to use math.ceil() instead of math.floor()

My current solution is this:

import math

def integerDivision(a,b):
    tmp = a / b 
    if tmp > 1:
        return(math.floor(tmp))
    else:
        return(math.ceil(tmp))

What is the implementation of the // operator that makes it not give the right result in some floating point cases? Is there a better way to get around this issue of the // operator, other than the above code?

Answer 1

This isn't about implementation. This is about the operator's semantics. Regardless of implementation, the // operator is required to give you the results you're seeing when applied to floats, and those results really are correct (for floats). If you don't want these results, floats are probably the wrong tool for what you're doing.

1 // 0.2 gives the floating-point number representing the floor of the exact value of the quotient of its arguments. However, the right-hand argument does not quite have the value you typed in. The right-hand argument's value is the closest value to 0.2 representable in 64-bit IEEE binary floating point, which is slightly higher than 0.2:

>>> import decimal
>>> decimal.Decimal(0.2)
Decimal('0.200000000000000011102230246251565404236316680908203125')

The exact value of the quotient is thus slightly less than 5, so 1 // 0.2 gives you 4.0.

1 / 0.2 gives you 5.0 because the exact value of the quotient isn't representable as a float. The result needs to be rounded, and it rounds to 5.0. // does not perform this rounding; it computes the floor of the exact value, not the floor of a rounded float. (The result of the // may need to be rounded, but that's a different rounding.)

With all that said, the implementation needs to be more complex than floor(x / y), because that would give the wrong result. CPython bases its // implementation for floats on fmod. You can see the implementation in Objects/floatobject.c in the CPython source repository.

static PyObject *
float_divmod(PyObject *v, PyObject *w)
{
    double vx, wx;
    double div, mod, floordiv;
    CONVERT_TO_DOUBLE(v, vx);
    CONVERT_TO_DOUBLE(w, wx);
    if (wx == 0.0) {
        PyErr_SetString(PyExc_ZeroDivisionError, "float divmod()");
        return NULL;
    }
    PyFPE_START_PROTECT("divmod", return 0)
    mod = fmod(vx, wx);
    /* fmod is typically exact, so vx-mod is *mathematically* an
       exact multiple of wx.  But this is fp arithmetic, and fp
       vx - mod is an approximation; the result is that div may
       not be an exact integral value after the division, although
       it will always be very close to one.
    */
    div = (vx - mod) / wx;
    if (mod) {
        /* ensure the remainder has the same sign as the denominator */
        if ((wx < 0) != (mod < 0)) {
            mod += wx;
            div -= 1.0;
        }
    }
    else {
        /* the remainder is zero, and in the presence of signed zeroes
           fmod returns different results across platforms; ensure
           it has the same sign as the denominator. */
        mod = copysign(0.0, wx);
    }
    /* snap quotient to nearest integral value */
    if (div) {
        floordiv = floor(div);
        if (div - floordiv > 0.5)
            floordiv += 1.0;
    }
    else {
        /* div is zero - get the same sign as the true quotient */
        floordiv = copysign(0.0, vx / wx); /* zero w/ sign of vx/wx */
    }
    PyFPE_END_PROTECT(floordiv)
    return Py_BuildValue("(dd)", floordiv, mod);
}

static PyObject *
float_floor_div(PyObject *v, PyObject *w)
{
    PyObject *t, *r;

    t = float_divmod(v, w);
    if (t == NULL || t == Py_NotImplemented)
        return t;
    assert(PyTuple_CheckExact(t));
    r = PyTuple_GET_ITEM(t, 0);
    Py_INCREF(r);
    Py_DECREF(t);
    return r;
}

Other argument types will use other implementations, depending on the types.