Python 中平方所需的时间

Question

我想知道 x**2 还是 x*x 更快

def sqr(x):
    for i in range (20):
        x = x**2
    return x
def sqr_(x):
    for i in range (20):
        x = x*x
    return x

当我计时时，这就是我得到的：

The time it takes for x**2: 101230500
The time it takes for x*x: 201469200

我已经尝试过很多次了，它们要么相等，要么 x ** 2 比 x * x 快。但 x*x 永远不会比 x**2 快。

所以我反汇编了代码：

对于 x**2：

  5          12 LOAD_FAST                0 (x)
             14 LOAD_CONST               2 (2)
             16 BINARY_POWER
             18 STORE_FAST               0 (x)
             20 JUMP_ABSOLUTE            8

对于 x*x：

  9          12 LOAD_FAST                0 (x)
             14 LOAD_FAST                0 (x)
             16 BINARY_MULTIPLY
             18 STORE_FAST               0 (x)
             20 JUMP_ABSOLUTE            8

是因为 load_const 比 load_fast 稍快吗？

LOAD_CONST：获取 co_consts 索引 1 处的文字值并将其推送

LOAD_FAST 通过索引访问数组中的值

或者binary_power比binary_multiply更快（我其实不知道binary_power算法）？

Answer 1

对于小整数，

x*x

明显比

x**2

快，因为 CPython 在内部执行了更多操作来计算

a**b

。实际上，在我的机器上

x*x

速度快了 4 倍（处理器 i5-9600KF，CPython 3.8.1，在 Windows 上）。话虽这么说，在您的代码中，数字增长得非常快，而 Python 整数是无界的。事实上，每次求幂都会导致二进制表示增大两倍。将指数相乘即可计算出

x**(2*2*2*...*2) = x**(2**20) = x**1048576

。对于大

x=2

，该数字需要 128 KiB 的内存，而对于

x=100

，则需要 850 KiB。这是相当大的。循环的每次迭代都受到内存中如此巨大数字的计算的限制。因此，对于大数，

x*x

和

x**2

一样快，因为这两种情况执行相同的内部计算，并且与大整数的计算相比，CPython 解释器的开销可以忽略不计。

---

在引擎盖下

在内部，CPython 似乎使用

_PyNumber_PowerNoMod

调用

PyNumber_Power

调用

ternary_op

，以及

PyNumber_Multiply

调用

binary_op1

。请注意，CPython 并未针对计算

x**2

进行优化：CPython 内部计算

pow(x, 2, None)

，这是计算模幂的函数（尽管对

pow

的调用效率稍低，因为 CPython 必须检查

pow

是否有没有被覆盖）。这个模幂函数要昂贵得多，因为与 x * x 相比，它是一个非常

通用函数

。

最后，在您的情况下似乎调用了

long_mul

和

long_pow

（请注意，

long_pow

在内部调用

long_mul

，因此

long_pow

实际上需要计算更多指令）。

对于大数，CPython 使用 Karatsuba 乘法（请参阅：

k_mul

）。

请注意，CPython 在这两种情况下实际上都非常慢，因为它需要几纳秒（至少在我的机器上）并且执行数十次检查和许多函数调用只是为了将两个整数相乘。对于主流 x86-64 处理器上的 64 位整数，这只需 1 个周期即可完成。大整数无法由主流处理器本地计算，并且需要更昂贵的计算。