为什么对一个数进行平方比将其乘以自身要慢？

Question

我很好奇，决定在Python中运行这段代码：

import time

def timeit(function):
    strt = time.time()
    for _ in range(100_000_000):
        function()
    end = time.time()
    print(end-strt)

@timeit
def function1():
    return 1 * 1

@timeit
def function2():
    return 1_000_000_000_000_000_000_000_000_000_000 * 1_000_000_000_000_000_000_000_000_000_000

@timeit 
def function3():
    return 1_000_000_000_000_000_000_000_000_000_000 ** 2

这是我的结果：

4.712368965148926
9.684480905532837
11.74640703201294

为什么第三个函数（平方）比第二个函数（乘以自身）慢？计算机里面发生了什么，我原本以为进行指数运算只是直接将一个数乘以自己？

- vs07

Answer 1

这是 int.__pow__ 的 实现，仅列出执行此操作的代码片段：

/* pow(v, w, x) */
static PyObject *
long_pow(PyObject *v, PyObject *w, PyObject *x)
{
    PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
    int negativeOutput = 0;  /* if x<0 return negative output */

    PyLongObject *z = NULL;  /* accumulated result */
    Py_ssize_t i, j;             /* counters */
    PyLongObject *temp = NULL;
    PyLongObject *a2 = NULL; /* may temporarily hold a**2 % c */

    PyLongObject *table[EXP_TABLE_LEN];
    Py_ssize_t num_table_entries = 0;

    /* a, b, c = v, w, x */
    CHECK_BINOP(v, w);
    a = (PyLongObject*)v; Py_INCREF(a);
    b = (PyLongObject*)w; Py_INCREF(b);
    if (PyLong_Check(x)) {
        /* Not executed */
    }
    else if (x == Py_None)
        c = NULL;
    else {
        /* Not executed */
    }

    if (Py_SIZE(b) < 0 && c == NULL) {
        /* Not executed */
    }

    if (c) {
        /* Not executed */
    }

    /* At this point a, b, and c are guaranteed non-negative UNLESS
       c is NULL, in which case a may be negative. */

    z = (PyLongObject *)PyLong_FromLong(1L);
    if (z == NULL)
        ; /* Not executed */

    /* Perform a modular reduction, X = X % c, but leave X alone if c
     * is NULL.
     */
#define REDUCE(X)                                       \
    do {                                                \
        if (c != NULL) {                                \
            /* Not executed */                          \
        }                                               \
    } while(0)

    /* Multiply two values, then reduce the result:
       result = X*Y % c.  If c is NULL, skip the mod. */
#define MULT(X, Y, result)                      \
    do {                                        \
        temp = (PyLongObject *)long_mul(X, Y);  \
        if (temp == NULL)                       \
            goto Error;                         \
        Py_XDECREF(result);                     \
        result = temp;                          \
        temp = NULL;                            \
        REDUCE(result);                         \
    } while(0)

    i = Py_SIZE(b);
    digit bi = i ? b->ob_digit[i-1] : 0;
    digit bit;
    if (i <= 1 && bi <= 3) {
        /* aim for minimal overhead */
        if (bi >= 2) {
            MULT(a, a, z);
            if (bi == 3) {
                /* Not executed */
            }
        }
        else if (bi == 1) {
            /* Not executed */
        }
        /* else bi is 0, and z==1 is correct */
    }
    else if (i <= HUGE_EXP_CUTOFF / PyLong_SHIFT ) {
        /* Not executed */
    }
    else {
        /* Not executed */
    }

    if (negativeOutput && (Py_SIZE(z) != 0)) {
        /* Not executed */
    }
    goto Done;

  Error:
    /* Not executed */
  Done:
    for (i = 0; i < num_table_entries; ++i)
        Py_DECREF(table[i]);
    Py_DECREF(a);
    Py_DECREF(b);
    Py_XDECREF(c);
    Py_XDECREF(a2);
    Py_XDECREF(temp);
    return (PyObject *)z;
}

即使像这样缩短，也有很多代码检查各种情况并操作引用，因为此函数需要能够处理的不仅仅是单个乘法。

在所有这些代码中，MULT 宏内部有一个对整数乘法实现 long_mul 的单个调用。

#define MULT(X, Y, result)                      \
    do {                                        \
        temp = (PyLongObject *)long_mul(X, Y);  \
        ...

当你用*将一个数字与自己相乘时，它可以跳过我刚刚发布的所有内容，直接进入long_mul。

- user2357112