为什么 2 * x * x 在 Python 3.x 中比 2 * ( x * x ) 快,对于整数?

以下 Python 3.x 整数乘法平均需要 1.66 秒到 1.77 秒:

import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
# num += 2 * (x * x)
num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))
如果我替换2 * x * x为2 *(x * x),则需要介于2.04和之间2.25。怎么来的?

另一方面,在 Java 中则相反:在 Java2 * (x * x)中更快。Java测试链接:为什么Java中2*(i*i)比2*i*i快?

我运行每个版本的程序 10 次,结果如下。
2 * x * x | 2 * (x * x)
---------------------------------------
1.7717654705047607 | 2.0789272785186768
1.735931396484375 | 2.1166207790374756
1.7093875408172607 | 2.024367570877075
1.7004504203796387 | 2.047525405883789
1.6676218509674072 | 2.254328966140747
1.699510097503662 | 2.0949244499206543
1.6889283657073975 | 2.0841963291168213
1.7243537902832031 | 2.1290600299835205
1.712965488433838 | 2.1942825317382812
1.7622807025909424 | 2.1200053691864014

已邀请:
首先,请注意我们在 Python 2.x 中看不到同样的东西:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115
所以这让我们相信这是由于 Python 3 中整数的变化:具体来说,Python 3long在任何地方都使用(任意大的整数)。

对于足够小的整数(包括我们在这里考虑的整数),CPython 实际上只是使用 O(MN)小学逐位乘法算法(对于较大的整数,它切换到Karatsuba 算法)。您可以自己在源代码中看到这一点。

in 的位数x*x大约是2*xor 的两倍x(因为 log(x 2 ) = 2 log(x))。请注意,此上下文中的“数字”不是以 10 为基数的数字,而是 30 位值(在 CPython 的实现中被视为单个数字)。因此,2是个位数的值,并且x和2*x是循环的所有迭代的个位数值,但对于x*x是两位数x >= 2**15。因此,对于x >= 2**15,2*x*x只需要一个个位数的乘法,而2*(x*x)需要一个个位数和一个个位数的乘法(因为x*x有 2 个 30 位数字)。

这是查看此内容的直接方法(Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615
再次将其与 Python 2 进行比较,后者不使用任意长度的整数:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973
(一个有趣的注释:如果你查看源代码,你会发现该算法实际上有一个特殊情况用于平方数字(我们在这里做的),但即使这仍然不足以克服2*(x*x)只需要处理更多数字。)

要回复问题请先登录注册