python - 计算非常大的功率

Question

我想计算非常大的数字，例如 n = 10^15。
不知何故我不能，因为OverflowError。

xd = lambda n : ((((5+ sqrt(17)) * ((3 + sqrt(17)) ** n)) - ((5-sqrt(17))* ((3 - sqrt(17)) ** n)))/((2 ** (n+1)) * sqrt(17)))

即使 n=1000，也不会计算。
不过，我应该提到我想要它的模块化(1000000007)
解决方案是什么？

Answer 1

看the answer on maths.stackexchange公式来自哪里，似乎最容易计算的是a(n)。
所以，这可以通过递归非常简单地计算出来，而这一次，由于我们只使用乘法和加法，我们可以利用模运算的规则并保持我们操作的数字很小:

def s(n, mod):
    a1 = 1
    a2 = 3
    for k in range(n-1):
        a1, a2 = a2, (3*a2 + 2* a1) % mod
    return (a1 + a2) % mod


mod = 1000000007

print(s(10, mod))
# 363314, as with the other formulas...

print(s(10**6, mod))
# 982192189

%timeit s(10**6, mod)
# 310 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit s(10**7, mod)
# 3.39 s ± 93.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

我们得到与其他公式相同的结果，(这是一件非常好的事情......)。由于计算过程中使用的数字保持相同的大小，最多取模的 5 倍，计算时间约为 O(n) - s(10**7)只需要比 s(10**6) 多 10 倍的时间.