Python: Comparison of Float

Python中的floatint的大小比较相对于其他语言来说,实现上可能复杂一些。Python的float相当于C中的double,而Python的int实际上是由多个32位或64位整数拼接而成的高精度整数,其表示的精度和范围完全有可能比double类型更大。

显然,(1)将浮点数转换成整数进行比较是不可行的,那样会丢失精度;而(2)Python中的整数是高精度整数,在内存足够大的情况下可以非常大,远大于double所能表示的范围;并且(3)C的long有63位精度,而double仅有53位,因此也不能仅因转换后的比较结果相等就判定转换前的数值也相等。

因此,Python的floatint之间比较,主要有以下几个步骤(令vfloatwintop为比较运算符):

  1. 获取两数的符号(+-0),若符号不同可直接判断;
  2. 获取整数w的位数nbits
  3. 若整数的位数较小(<48),则转换为double再比较;
  4. 若整数为负数,则同时对整数和运算符取反,之后不再考虑符号问题;
  5. 获取浮点数的指数exp
  6. 比较二者的位数和指数,若不等则可直接判断,相等则继续往下;
  7. 将浮点数拆分为整数和小数部分,整数部分转换为int,小数部分若不为0.0,则向整数进1;
  8. 和整数类型间的比较一样。

下面分析源码。

static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
    double i, j;
    int r = 0;

    assert(PyFloat_Check(v));
    i = PyFloat_AS_DOUBLE(v);

    if (PyFloat_Check(w))
    {
        //...
    }
    else if (PyLong_Check(w)) {
        // 两数的符号
        int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
        int wsign = _PyLong_Sign(w);
        size_t nbits;
        int exponent;

        // 符号位不一致,可直接比较
        if (vsign != wsign) {
            i = (double)vsign;
            j = (double)wsign;
            goto Compare;
        }
        // 符号位一致时
        // 先尝试将PyLong转换为double
        // 获取PyLong的二进制位数
        nbits = _PyLong_NumBits(w);
        if (nbits == (size_t)-1 && PyErr_Occurred()) {
            // 获取位数时发生了溢出,表示PyLong太大,它必然大于有限的浮点数
            PyErr_Clear();
            i = (double)vsign;
            assert(wsign != 0);
            j = wsign * 2.0;
            goto Compare;
        }
        if (nbits <= 48) {
            // 位数小于48位时,可安全转换为double
            j = PyLong_AsDouble(w);
            assert(j != -1.0 || ! PyErr_Occurred());
            goto Compare;
        }

        // 以上处理完了符号位不一致或值较小的情况
        assert(wsign != 0); /* else nbits was 0 */
        assert(vsign != 0); /* if vsign were 0, then since wsign is
                             * not 0, we would have taken the
                             * vsign != wsign branch at the start */
        // 仅对正数操作
        if (vsign < 0) {
            // 对符号位取反,那么操作符也相应取反
            i = -i;
            op = _Py_SwappedOp[op];
        }
        assert(i > 0.0);
        // 获取v的指数位exponent
        // 并且这里w的位数>48
        (void) frexp(i, &exponent);

        // 以下的v和w符号位一致且不为0,不用再考虑符号的问题了
        if (exponent < 0 || (size_t)exponent < nbits) {
            // v指数<0,意味着v<1,即v<w必成立
            // 或v指数exponent < w指数nbits,v<w也必成立
            i = 1.0;
            j = 2.0;
            goto Compare;
        }
        if ((size_t)exponent > nbits) {
            // 反之亦然
            i = 2.0;
            j = 1.0;
            goto Compare;
        }

        // v和w具有相等的指数,将两者均转换为PyLong比较
        {
            double fracpart;
            double intpart;
            PyObject *result = NULL;
            PyObject *vv = NULL;
            PyObject *ww = w;

            // w取绝对值
            if (wsign < 0) {
                ww = PyNumber_Negative(w);
                if (ww == NULL)
                    goto Error;
            }
            else
                Py_INCREF(ww);

            // 拆分v的整数部分intpart和小数部分fracpart
            fracpart = modf(i, &intpart);
            vv = PyLong_FromDouble(intpart);
            if (vv == NULL)
                goto Error;

            // 如果有小数部分
            if (fracpart != 0.0) {
                // 两整数均左移一位,然后给v or 1表示损失精度

                PyObject *temp;

                temp = _PyLong_Lshift(ww, 1);
                if (temp == NULL)
                    goto Error;
                Py_DECREF(ww);
                ww = temp;

                temp = _PyLong_Lshift(vv, 1);
                if (temp == NULL)
                    goto Error;
                Py_DECREF(vv);
                vv = temp;

                temp = PyNumber_Or(vv, _PyLong_GetOne());
                if (temp == NULL)
                    goto Error;
                Py_DECREF(vv);
                vv = temp;
            }

            // 和整数的比较运算一样了
            r = PyObject_RichCompareBool(vv, ww, op);
            if (r < 0)
                goto Error;
            result = PyBool_FromLong(r);
         Error:
            Py_XDECREF(vv);
            Py_XDECREF(ww);
            return result;
        }
    } /* else if (PyLong_Check(w)) */

    else        /* w isn't float or int */
        goto Unimplemented;

 Compare:
    switch (op) {
    case Py_EQ:
        r = i == j;
        break;
    case Py_NE:
        r = i != j;
        break;
    case Py_LE:
        r = i <= j;
        break;
    case Py_GE:
        r = i >= j;
        break;
    case Py_LT:
        r = i < j;
        break;
    case Py_GT:
        r = i > j;
        break;
    }
    return PyBool_FromLong(r);

 Unimplemented:
    Py_RETURN_NOTIMPLEMENTED;
}

发表评论

您的电子邮箱地址不会被公开。