3

通常我很懒，计算模逆如下：

def inv(a,m):
    return 1 if a==1 else ((a-inv(m%a,a))*m+1)//a
print(inv(100**7000,99**7001))

但我很想知道将更多信息传回的方法，即 Bezout 定理的解决方案（而不仅仅是其中一个），在实践中是否会产生更快或更慢的算法：

def bez(a,b):
    # returns [x,y,d] where a*x+b*y = d = gcd(a,b) since (b%a)*y+a*(x+(b//a)*y)=d
    if a==0: return [0,1,b] if b>0 else [0,-1,-b]
    r=bez(b%a,a)
    return [r[1]-(b//a)*r[0],r[0],r[2]]
def inv(a,m):
    r=bez(a,m)
    if r[2]!=1: return None
    return r[0] if r[0]>=0 else r[0]+abs(m)
print(inv(100**7000,99**7001))

我惊奇地发现后者的运行速度比前者快了 50 多倍！但是两者都使用几乎相同数量的递归调用和每次调用 1 个整数除法和 1 个模运算，并且操作数的位长度平均大约是前者的两倍（因为所涉及的参数是相同的），所以我只期望它的时间复杂度大约是后者的 4 倍，而不是 50 倍。

那么为什么我会观察到这种奇怪的加速呢？

请注意，我使用的是 Python 3，并且在online运行时观察到了这一点，并在顶部添加了以下代码以阻止 Python 解释器抱怨超出最大递归深度或堆栈空间：

import resource,sys
sys.setrecursionlimit(1000000)
resource.setrlimit(resource.RLIMIT_STACK,[0x10000000,resource.RLIM_INFINITY])
4

1 回答 1

1

我终于想通了。假设初始输入是 n 位整数。在典型情况下，除了第一次调用invor之外inv2，递归调用的参数大小平均相差仅 O(1) 次，并且平均有 O(n) 次递归调用，这都是由于某种数论现象。这种 O(1) 大小差异意味着这两种方法实际上具有截然不同的平均时间复杂度。我的问题中隐含的假设是两个 n 位整数的乘法或除法大约需要 O(n^2) 时间；这适用于最坏的情况（对于教科书乘法），但不适用于快速方法的平均情况！

对于快速方法，可以证明当 p,q > 0 时，返回的三元组 [x,y,d]bez(p,q)满足 abs(x) ≤ q 和 abs(y) ≤ p。因此，当每个调用bez(a,b)执行b%aand(b//a)*r[0]时，模和除法和乘法平均每个都需要 O(size(a)) 时间，因为 size(b)-size(a) ∈ O(1) 平均和 abs(r[0] ) ≤ 一个。因此，总时间大约为 O(n^2)。

然而，对于慢速方法，当每个调用inv(a,m)执行时((a-inv(m%a,a))*m+1)//a，我们的 a-inv(m%a,a) 的大小与 a 大致相同，因此这个除法是两个整数，其中第一个的大小大约是第二个的两倍，这将花费 O(size(a)^2) 时间！因此，总时间大约为 O(n^3)。

实际上，模拟与上述分析非常吻合。作为参考，使用快速方法inv(100**n,99**(n+1))where n = 1400·k for k∈[1..6] 花费时间/ms 17,57,107,182,281,366，而使用慢速方法 where n = 500·k for k∈[1..6] 花费时间/毫秒22,141,426,981,1827,3101。它们分别与 9·k^2+9·k 和 13·k^3+8·k^2 非常吻合，平均分数误差分别为 ≈3.3% 和 ≈1.6%。（我们包括前两个最高阶项，因为它们的贡献很小但很重要。）

于 2021-08-30T19:39:14.770 回答