为什么python两个n位整数相乘的时间只在n增加10s时才增加？

Question

我正在计算在我的计算机上计算两个 n 位整数的乘积所花费的时间。

我正在使用此代码来执行此操作：

import timeit
for i in range(50):
    avg=0
    for j in range(30):
        avg+=timeit.timeit('a*b','a='+str(10**i)+';b='+str(10**i))
    print(avg/30)

它 returns 结果图表为：

其中X轴是n，Y轴是以秒为单位的时间。可以看到，当它是10的倍数时，花费的时间在n左右递增，并不是一直递增的。

我不明白为什么花费的时间会这样变化。

Answer 1

A Python int 的大小是 stored 作为 30 位块的序列（或者有时是 15 位块，但现在这种情况很少见）。让你的数字长 9 位十进制数字大约需要 30 位，两个数字相乘所花费的时间主要取决于每个数字需要多少个 30 位块，所以时间以大约 9 位十进制数字的增量增加。