为什么Python中的浮点除法用较小的数字更快？

Question

在回答这个问题的过程中,我遇到了一些我无法解释的问题.

给出以下Python 3.5代码:

import time

def di(n):
    for i in range(10000000): n / 101

i = 10
while i < 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000:
    start = time.clock()
    di(i)
    end = time.clock()
    print("On " + str(i) + " " + str(end-start))
    i *= 10000

输出是:

On 10 0.546889
On 100000 0.545004
On 1000000000 0.5454929999999998
On 10000000000000 0.5519709999999998
On 100000000000000000 1.330797
On 1000000000000000000000 1.31053
On 10000000000000000000000000 1.3393129999999998
On 100000000000000000000000000000 1.3524339999999997
On 1000000000000000000000000000000000 1.3817269999999997
On 10000000000000000000000000000000000000 1.3412670000000002
On 100000000000000000000000000000000000000000 1.3358929999999987
On 1000000000000000000000000000000000000000000000 1.3773859999999996
On 10000000000000000000000000000000000000000000000000 1.3326890000000002
On 100000000000000000000000000000000000000000000000000000 1.3704769999999993
On 1000000000000000000000000000000000000000000000000000000000 1.3235019999999995
On 10000000000000000000000000000000000000000000000000000000000000 1.357647
On 100000000000000000000000000000000000000000000000000000000000000000 1.3341190000000012
On 1000000000000000000000000000000000000000000000000000000000000000000000 1.326544000000002
On 10000000000000000000000000000000000000000000000000000000000000000000000000 1.3671139999999973
On 100000000000000000000000000000000000000000000000000000000000000000000000000000 1.3630120000000012
On 1000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.3600200000000022
On 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.3189189999999975
On 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.3503469999999993

如您所见,大约有两次:一次是较小的数字,另一次是较大的数字.

使用以下函数保存语义时,Python 2.7也会出现相同的结果:

def di(n):
    for i in xrange(10000000): n / 101.0

在同一台机器上,我得到:

On 10 0.617427
On 100000 0.61805
On 1000000000 0.6366
On 10000000000000 0.620919
On 100000000000000000 0.616695
On 1000000000000000000000 0.927353
On 10000000000000000000000000 1.007156
On 100000000000000000000000000000 0.98597
On 1000000000000000000000000000000000 0.99258
On 10000000000000000000000000000000000000 0.966753
On 100000000000000000000000000000000000000000 0.992684
On 1000000000000000000000000000000000000000000000 0.991711
On 10000000000000000000000000000000000000000000000000 0.994703
On 100000000000000000000000000000000000000000000000000000 0.978877
On 1000000000000000000000000000000000000000000000000000000000 0.982035
On 10000000000000000000000000000000000000000000000000000000000000 0.973266
On 100000000000000000000000000000000000000000000000000000000000000000 0.977911
On 1000000000000000000000000000000000000000000000000000000000000000000000 0.996857
On 10000000000000000000000000000000000000000000000000000000000000000000000000 0.972555
On 100000000000000000000000000000000000000000000000000000000000000000000000000000 0.985676
On 1000000000000000000000000000000000000000000000000000000000000000000000000000000000 0.987412
On 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0.997207
On 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0.970129

为什么较小数字与较大数字的浮点除法之间存在这种一致差异？它是否与Python内部使用浮点数较小的数字和双数字较大的数字？

Answer 1

它更多地与Python存储精确整数作为Bignums.

在Python 2.7中,计算整数a/float fb,首先将整数转换为float.如果整数存储为Bignum [注1]则需要更长时间.所以这不是具有差别成本的部门; 它是整数(可能是Bignum)到double的转换.

Python 3对整数a/float fb执行相同的计算,但是对于整数a/integer b,它尝试计算最接近的可表示结果,这可能与天真略有不同float(a) / float(b).(这类似于经典的双舍入问题.)

如果两个float(a)和float(b)是精确(即,两个a和b不大于53比特),则幼稚解决方案工作,结果只需要两个双精度浮点值的划分.

否则,执行多精度分割以生成正确的53位尾数(指数被单独计算),并且结果被精确地转换为浮点数.这种划分有两种可能性:快速轨道if b小到足以适合单个Bignum单元(适用于OP中的基准),以及较慢的一般Bignum除法b.

在上述情况中,没有观察到与硬件执行浮点除法的速度有关的速度差.对于原始的Python 3.5测试,差异与是否执行浮点或Bignum除法有关; 对于Python 2.7的情况,差异与将Bignum转换为double的必要性有关.

感谢@MarkDickinson的澄清,以及指向实现算法的源代码(带有长而有用的注释)的指针.

笔记

1. 在Python 3中,整数总是存储为Bignums.Python 2具有int(64位整数)和long(Bignums)的单独类型.实际上,由于Python 3经常使用优化算法,而Bignum只有一个"腿","小"和"大"整数之间的差异仍然很明显.