1

我一直假设整数除法比浮点除法更快，但我做了一些似乎证明并非如此的测试。

import gmpy2, time, math

digits = 100000

scale = 10**digits  # Decimal precision
gmpy2.get_context().precision = int(math.log2(10) * digits)  # Binary precision

def start_timer():
    global start_time  
    start_time = time.time()

def print_timer():
    print("%s s" % (time.time() - start_time))

start_timer()
for i in range(1000):
    x = scale // 3
print_timer()

start_timer()
for i in range(1000):
    x = gmpy2.mpfr(1) / 3
print_timer()

start_timer()
for i in range(1000):
    x = gmpy2.mpfr(1) / gmpy2.mpfr(3)
print_timer()

整数除法耗时 0.17 秒，mpfr 除法耗时 0.06 秒，两个浮点数相除耗时 15.56 秒。

我的问题：

  1. 我是否正确设置了此测试？
  2. mpfr除法真的比native除法更优化吗？
  3. 涉及浮点数和整数的除法是否比涉及两个浮点数的除法快得多？
4

3 回答 3

4

我正在使用 IPython 来计时一些简短的示例，然后我将尝试解释结果。

from gmpy2 import mpfr, get_context
get_context().precision=1000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000000 loops, best of 3: 669 ns per loop
%timeit a/3
1000000 loops, best of 3: 464 ns per loop

get_context().precision=10000
a=mpfr(1);b=mpfr(3)

%timeit a/b
100000 loops, best of 3: 12.9 µs per loop
%timeit a/3
1000000 loops, best of 3: 1.33 µs per loop

get_context().precision=100000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000 loops, best of 3: 505 µs per loop
%timeit a/3
100000 loops, best of 3: 8.13 µs per loop

请注意，随着精度的增加，运行时间的a/b增加速度比a/3. 计算时a/b，MPFR 使用两个值的完整精度，运行时间（大致）为 O(n * ln(n))。在计算 时a/3，MPFR 使用 3 的简短但精确的表示，并且运行时间（大致）为 O(n)。这解释了为什么a/b比a/3高精度慢。（n 是以位为单位的长度a。）

当 Python 计算scale//3时，它利用了 3 将适合单个digit并且运行时间与scale. 这实际上与计算相同，a/3但由于底层 GMP 库比 Python 快，a/3因此计算速度比scale//3.

这是 Python 和 GMP 之间性能差异的简短示例。

from gmpy2 import mpz
scale = 10**100000

%timeit scale//3
10000 loops, best of 3: 162 µs per loop

scale = mpz(scale)

%timeit scale//3
100000 loops, best of 3: 19 µs per loop

当您比较和时，您正在衡量一个nby nDivision 和 an nby Division 之间的性能。（是位的长度，比 小得多。）当您比较和 'a/3' 时，您是在比较一个简单、直接的除法实现和一个高度优化的实现。ka/ba/3naknscale//3

实现说明：在当前不稳定的开发分支中，直接a/3调用mpfr_div_ui。这消除了 MPFR 创建临时对象的过程。这提高了性能，如下所示。

from gmpy2 import mpfr, get_context
get_context().precision=1000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000000 loops, best of 3: 593 ns per loop
%timeit a/3
1000000 loops, best of 3: 231 ns per loop

get_context().precision=10000
a=mpfr(1); b=mpfr(3)

%timeit a/b
100000 loops, best of 3: 12.7 µs per loop
%timeit a/3
1000000 loops, best of 3: 927 ns per loop

get_context().precision=100000
a=mpfr(1);b=mpfr(3)

%timeit a/b
1000 loops, best of 3: 505 µs per loop
%timeit a/3
100000 loops, best of 3: 6.77 µs per loop
于 2014-07-30T06:17:04.300 回答
2

关于 GNU MPFR 实现的说明（我是一名 MPFR 开发人员，虽然我没有真正研究过除法）：选择乘法和除法的最佳算法非常困难，因为有各种参数（输入和输出，以及输入是否可以因为尾随零而以较小的精度表示，特别是），并且某些情况可能比其他情况更难四舍五入。此外，算法因此时间可能会从一个版本更改为另一个版本，从而改善某些情况，但同时使其他情况变慢。甚至在最近（两个月前），我们也讨论过是否对 mpfr_mul_ui 和 mpfr_div_ui 中的整数进行 2 的常数幂的特殊识别。

如果你想真正比较整数除法和 MPFR FP 除法，你应该用 GMP 的整数除法进行比较。MPFR是基于GMP的划分，但并不天真。了解 MPFR 正在做什么的最好方法是将 MPFR 日志记录（这可能需要使用 重建--enable-logging）与相应的环境变量一起使用。请注意，在 MPFR 构建中启用日志记录时，即使不使用日志记录，MPFR 也可能会慢一些。

于 2014-07-30T10:43:35.593 回答
1

浮点除法通常比 CPU 上的整数除法更快。可以推测，这与 FPU 对该操作进行了更优化有关，或者浮点表示使除法更容易。但无论什么原因都改变不了事实。最后，获得第二个和第三个问题具体答案的唯一方法就是测试它。是的，你的测试对我来说看起来不错。

如果我不得不冒险猜测，我认为将 MPFR 数除以整数的情况更快，因为 GMP 在计算除法时可以利用其有限的精度来发挥其优势。

于 2014-07-29T20:37:45.853 回答