时间戳

首页 > 解决方案 > 数幂的整数除法可以优化吗？

python - 数幂的整数除法可以优化吗？

问题描述

在 Python 中有一个内置函数pow可以优化a**b%c. 为什么没有计算函数a**b//c？

标签： pythonbuilt-inpow

解决方案

我将尝试在这里总结为什么a ** b // c无法优化计算，不太可能a ** b % c。

先决条件：计算a ** b % c

让我们举一个说明性的例子：说a=2and b=11。如果我们假设它很慢，那么我们就可以推断出b = 1 + 2 + 8 = 2**0 + 2**1 + 0*2**2 + 2**3。之后，这个扣除可以用作结果乘法的规则a, a**2, a**4, a**8。每个结果都是在对前一个结果进行平方之后分配的。最后，a**11 = a*(a**2)*(a**8)这个过程只需要 3 次平方。

如果我们概括这个过程，可以这样完成：

a, b, r = 2, 11 , []

while b>0:
    if b % 2: r.append(a)
    b = b//2
    a = a*a
else:
    if b % 2: r.append(a)

print(r)

一个输出是r=[2, 4, 256]。接下来，我们需要将这些乘数相乘。可以使用from functools import reduce命令来完成reduce(lambda x,y: x*y, r)。

最后，如果乘法器变得非常大，乘法器变得非常慢，所以我们需要m用它的模数替换每个乘法器并在功能上m%c做同样的事情。reduce最后，我们有：

from functools import reduce
def pow(a, b, c):
    # returns a ** b % c
    r = []
    while b > 0:
        if b % 2: r.append(a)
        b = b // 2
        a = (a * a) % c
    else:
        if b % 2: r.append(a)

    return reduce(lambda x, y: (x * y) % c, r)

输出是4因为2 ** 11 % 7是4。

我已经2046457 ** 1103207 % 71872在我的电脑上测试了结果。输出是 18249，计算需要 9 秒，同时pow(2046457, 1103207, 71872)立即给出相同的结果。

更新：插入a ** b // c计算

按照上述思路，我将尝试对a**b // c. 我假设平方过程保持不变，这里的主要区别是我们需要在取平方时同时考虑积分和残差（以前很容易，因为积分部分并不重要）。如果x是一个整数部分并且y是一个残差部分，我们有一个关系：

[1]：https://i.stack.imgur.com/ReNeV.gif

我们还需要为两个不同的乘数引入类似的计算：

在此处输入图像描述

我的脚本现在看起来像这样：

from functools import reduce
def pow(a, b, c):
    #returns tuple (a ** b // c,  a ** b % c)
    print(f'calculating: {a}**{b} = ', end='')
    r = []
    ir = (a//c, a%c) # we keep integral and residual part of a instead of a
    while b > 0:
        if b % 2: r.append(ir)
        b = b // 2
        ir = (ir[0]*ir[0]*c + 2*ir[0]*ir[1]+ (ir[1]*ir[1])//c, (ir[1]*ir[1]) % c)
    else:
        if b % 2: r.append(ir)
    out = reduce(lambda x, y: (c*x[0]*y[0] + x[0]*y[1] + x[1]*y[0] + (x[1] * y[1])//c, (x[1] * y[1]) % c), [(2, 2)]+[r[-1]])

    print(' * '.join(str(n[0]*c+n[1]) for n in r), end=' = ')
    print(' * '.join(str(n) for n in r),'=', out)
    return out

pow(2,7,3)

输出

calculating: 2**7 = 2 * 4 * 16 = (0, 2) * (1, 1) * (5, 1) = (42, 2)

笔记

为什么还没有优化？我们可以看到每个因子中的第二项始终很小，但这不是第一项的规则，例如以下示例pow(26,31,35)：

calculating: 26**31 = 26 * 676 * 456976 * 208827064576 * 43608742899428874059776 = 
(0, 26) * (19, 11) * (13056, 16) * (5966487559, 11) * (1245964082840824973136, 16) = 
(89709413964539398065824, 32)

在这种情况下，我们无法避免a%b // c. 这就是为什么不存在的内置函数 fora%b // c对我来说似乎是合理的。

推荐阅读