Modular arithmetic in Python

Question

Problem 48 description from Project Euler:

The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317. Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.

I've just solved this problem using a one-liner in Python:

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

I did it that way almost instantly, as I remembered that division mod n is very fast in Python. But I still don't understand how does this work under the hood (what optimizations does Python do?) and why is this so fast.

Could you please explain this to me? Is the mod 10**10 operation optimized to be applied for every iteration of the list comprehension instead of the whole sum?

$ time python pe48.py 
9110846700

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

Answer 1

Given that

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

and

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

function equally fast in Python, the answer to your last question is 'no'.

So, Python must be able to do integer exponentiation really fast. And it so happens that integer exponentiation is O(log(n)) multiplications: http://en.wikipedia.org/wiki/Exponentiation#Efficient_computation_of_integer_powers

Essentially what is done is, instead of doing 2^100 = 2*2*2*2*2... 100 times, you realize that 2^100 is also 2^64 * 2^32 * 2^4 , that you can square 2 over and over and over to get 2^2 then 2^4 then 2^8... etc, and once you've found the values of all three of those components you multiply them for a final answer. This requires much fewer multiplication operations. The specifics of how to go about it are a bit more complex, but Python is mature enough to be well optimized on such a core feature.

Answer 2

No, it's applied to the whole sum. The sum itself is very fast to compute. Doing exponents isn't that hard to do quickly if the arguments are integers.