What optimisations are done that this code completes quickly?
<p>I was solving a problem I came across, what is the sum of powers of 3 from 0 to 2009 mod 8.</p>

<p>I got an answer using pen and paper, and tried to verify it with some simple python</p>

<pre><code>print(sum(3**k for k in range(2010)) % 8)
</code></pre>

<p>I was surprised by how quickly it returned an answer. My question is what optimisations or tricks are used by the interpreter to get the answer so quickly?</p>

<p>The only optimization at work is that each instance of <code>3**k</code> is evaluated using a number of multiplications proportional to the number of bits in <code>k</code> (it does <em>not</em> multiply 3 by itself <code>k-1</code> times).</p>

<p>As already noted, if you boost 2010 to 20100 or 201000 or ..., it will take much longer, because <code>3**k</code> becomes very large.  However, in those cases you can speed it enormously again by rewriting it as, e.g.,</p>

<pre><code>print(sum(pow(3, k, 8) for k in range(201000)) % 8)
</code></pre>

<p>Internally, <code>pow(3, k, 8)</code> still does a number of multiplications proportional to the number of bits in <code>k</code>, but doesn't need to retain any integers internally larger than about 8**2 (the square of the modulus).</p>

python python-3.x optimization