整数除法如何在python中工作?

Question

所以，我最近听说了整数除法，它非常快。当我做floor(x/2^n)时，我一直在使用Bit shift。

所以，我已经测试了哪个是更快的整数除法或位移位，所以，我做了这个代码，它测试和比较它100次，并找到平均值:

import timeit
import statistics as stat

def compare_times(a, b):
res_a = timeit.timeit(a)
res_b = timeit.timeit(b)
c = res_a - res_b # if negative, a is faster 
return c

output = []

for _ in range(100):
output.append(compare_times("5 >> 1", "5 // 2"))

print (stat.mean(output))

且结果为正，表示b更快。位移位不是直接作用于数字的位吗?为什么它比整数除法慢?

我测试了另一件事，看看是否因为我选择了5，所以:

import timeit
import statistics as stat
import random

def compare_times(a, b):
res_a = timeit.timeit(a)
res_b = timeit.timeit(b)
c = res_a - res_b # if negative, a is faster 
return c

output = []

for _ in range(100):
number = random.randrange(5000, 50001)
output.append(compare_times(f"{number} >> 1", f"{number} // 2"))

print (stat.mean(output))

输出也为正。

我唯一一次看到(位移位)比整数除法快的时候是在floor(x/2^n)， n>= 2.

那么，最终，整数除法是如何工作的呢?为什么在较小的数字上它比Bit Shift快?

Answer 1

你看到的任何时差都是假的;事实上，5 // 2和5 >> 1都编译成相同的CPython字节码:

>>> from dis import dis
>>> dis('5 // 2')
1           0 LOAD_CONST               2 (2)
2 RETURN_VALUE
>>> dis('5 >> 1')
1           0 LOAD_CONST               2 (2)
2 RETURN_VALUE

也就是说，计算是在编译时完成的，而不是在运行时完成的，因此在这两种情况下，您实际上只是测量加载预先计算的常量所需的时间。为了获得准确的基准测试，您需要在运行时实际执行计算，例如通过传递变量;我还建议使用更大的数字(或将重复次数提高到默认的1,000,000以上)以获得更可靠的比较。

>>> n = 1234 ** 56 # a 174-digit number
>>> from timeit import timeit
>>> timeit(lambda: n // 2)
0.32904140199389076
>>> timeit(lambda: n >> 1)
0.12879745499958517

所以我们可以看到，至少对于非常大的数字，位移位更快，正如你所期望的那样。对于较小的数字，可能没有显著差异。

至于CPython实际如何计算整数除法，GitHub上的源代码可以免费阅读，根据那里的评论，所使用的算法可以在一本著名的教科书中找到:

/* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
edn.), section 4.3.1, Algorithm D], except that we don't explicitly
handle the special case when the initial estimate q for a quotient
digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
that won't overflow a digit. */