Python中的模运算

Question

这是Project Euler的第48题描述：

这个数列是 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317。现在要找出这个数列的最后十个数字，也就是 1^1 + 2^2 + 3^3 + ... + 1000^1000 的最后十个数字。

我刚用Python写了一个一行代码就解决了这个问题：

print sum([i**i for i in range(1,1001)])%(10**10)

我几乎是瞬间就完成了，因为我记得在Python中，取模运算（也就是求余数）是非常快的。但我还是不太明白这个背后的原理（Python做了什么优化？）以及为什么这么快。

你能给我解释一下吗？这个mod 10**10操作是针对列表推导的每一次迭代进行优化，而不是对整个总和进行优化吗？

$ time python pe48.py 
9110846700

real 0m0.070s
user 0m0.047s
sys  0m0.015s

Answer 1

不，这个是应用在整个求和上。求和本身计算起来非常快。如果参数是整数，计算指数也并不难。

Answer 2

给定这个代码：

print sum([i**i for i in range(1,1001)])%(10**10)

还有这个代码：

print sum([i**i for i in range(1,1001)])

在Python中，这两个函数的运行速度是一样的，所以你最后的问题的答案是“不是”。

这说明Python在计算整数的幂时速度非常快。而且，整数的幂运算其实只需要O(log(n))次乘法：http://en.wikipedia.org/wiki/Exponentiation#Efficient_computation_of_integer_powers

简单来说，计算的时候，不是直接做2^100 = 2*2*2*2*2……一共100次，而是可以把2^100看作2^64 * 2^32 * 2^4。你可以不断地把2平方，先得到2^2，再得到2^4，再得到2^8……等等。等你找到了这三个部分的值后，再把它们相乘，就能得到最终的结果。这样做需要的乘法运算次数少得多。具体的实现方法会复杂一些，但Python已经足够成熟，能够在这个核心功能上进行很好的优化。