11
votes

I'm wondering where I find the source to show how the operator ** is implemented in Python. Can someone point me in the right direction?

4

4 Answers

26
votes

The python grammar definition (from which the parser is generated using pgen), look for 'power': Gramar/Gramar

The python ast, look for 'ast_for_power': Python/ast.c

The python eval loop, look for 'BINARY_POWER': Python/ceval.c

Which calls PyNumber_Power (implemented in Objects/abstract.c):

PyObject *
PyNumber_Power(PyObject *v, PyObject *w, PyObject *z)
{
    return ternary_op(v, w, z, NB_SLOT(nb_power), "** or pow()");
}

Essentially, invoke the pow slot. For long objects (the only default integer type in 3.0) this is implemented in the long_pow function Objects/longobject.c, for int objects (in the 2.x branches) it is implemented in the int_pow function Object/intobject.c

If you dig into long_pow, you can see that after vetting the arguments and doing a bit of set up, the heart of the exponentiation can be see here:

if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
    /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
    /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
    for (i = Py_SIZE(b) - 1; i >= 0; --i) {
        digit bi = b->ob_digit[i];

        for (j = 1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
            MULT(z, z, z)
            if (bi & j)
                MULT(z, a, z)
        }
    }
}
else {
    /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
    Py_INCREF(z);   /* still holds 1L */
    table[0] = z;
    for (i = 1; i < 32; ++i)
        MULT(table[i-1], a, table[i])

    for (i = Py_SIZE(b) - 1; i >= 0; --i) {
        const digit bi = b->ob_digit[i];

        for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
            const int index = (bi >> j) & 0x1f;
            for (k = 0; k < 5; ++k)
                MULT(z, z, z)
            if (index)
                MULT(z, table[index], z)
        }
    }
}

Which uses algorithms discussed in Chapter 14.6 of the Handbook of Applied Cryptography which describes efficient exponentiation algorithms for arbitrary precision arithmetic.

2
votes

There are two different implementations one for int (long in 3.0) objects and another one for float objects.

The float pow is the float_pow(PyObject *v, PyObject *w, PyObject *z) function defined in Objects/floatobject.c file of the Python source code. This functions calls pow() from C stdlib's math.h

The int pow has its own implementation, is the function int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z) defined in Objects/intobject.c (longobject.c for 3.0) of the Python source code.

1
votes

I think caseysrandomthoughts are asking about asterisks at functions definition.

You could find answer at this Python doc page: http://docs.python.org/tutorial/controlflow.html#more-on-defining-functions

When a final formal parameter of the form **name is present, it receives a dictionary containing all keyword arguments except for those corresponding to a formal parameter.

I've sow description of this stuff somewhere else at python doc but I can't to remember.

0
votes

It's the power to operator

python.org doc - Power operator

Edit: Oh, dang, the code, right. Hope the link still helps. Sloppy read from my part