MPFR除法比本地整数除法快吗？

1 投票

3 回答

1127 浏览

提问于 2025-04-18 15:14

我一直以为整数相除比小数相除要快，但我做了一些测试，结果似乎证明了我的想法是错的。

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秒。

我有几个问题：

我这样测试设置得对吗？
mpfr相除真的比普通的相除更优化吗？
涉及小数和整数的相除，真的比两个小数相除要快很多吗？

算法优化性能测试整数运算浮点运算除法性能 mpfr库

3 个回答

浮点数的除法通常比整数的除法在CPU上要快。我们可以猜测这可能是因为浮点运算单元（FPU）对这个操作进行了更好的优化，或者是因为浮点数的表示方式让除法变得更简单。不过，不管原因是什么，这个事实是不会改变的。最终，想要对你第二和第三个问题得到确切的答案，最好的办法就是自己去测试一下。是的，我觉得你的测试看起来没问题。

如果让我猜的话，我认为把一个MPFR数字除以一个整数的情况会更快，因为GMP在计算除法时可以利用它的有限精度来提高效率。

回答于 2025-04-18 由 Python大师

分享举报

关于GNU MPFR的实现，有一点需要说明（我是MPFR的开发者，不过我没有专门研究过除法）：选择最合适的乘法和除法算法其实挺复杂的，因为有很多因素要考虑，比如输入和输出的精度，以及输入是否可以用更小的精度表示，特别是当有尾随零的时候。此外，有些情况下的舍入比其他情况更难处理。而且，不同版本之间的算法和运行时间可能会有所不同，有些情况可能会变快，但同时也可能让其他情况变慢。就连最近（两个月前），我们还讨论过是否要在mpfr_mul_ui和mpfr_div_ui中对常数的二次幂进行特殊处理。

如果你想真正比较整数除法和MPFR的浮点除法，最好是用GMP的整数除法来做比较。MPFR是基于GMP的除法，但并不是简单地直接使用。想要了解MPFR具体在做什么，最好的办法是使用MPFR的日志功能（这可能需要用--enable-logging重新编译），并设置相应的环境变量。需要注意的是，当MPFR构建时启用了日志功能，即使没有使用日志，MPFR的速度可能也会稍微变慢。

回答于 2025-04-18 由 Python大师

分享举报

我正在使用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可以放入一个数字的事实，因此运行时间与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

当你比较a/b和a/3时，你是在测量一个n乘n的除法和一个n乘k的除法的性能。（n是a的位数长度，而k远远小于n。）当你比较scale//3和a/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

回答于 2025-04-18 由 Python大师

分享举报

MPFR除法比本地整数除法快吗？

我有几个问题：

3 个回答

撰写回答