Loop with very large number (2 ^ 64) hangs, how to iterate faster?
<p>I'm using python 2.7 version.
I have simple loop like below given</p>

<pre><code>while i &lt; math.pow(2,64):
 do_something()
 i += 1000 
</code></pre>

<p>But this code runs too long. I have heard that python has scientific libraries for working with very large numbers like scipy, numpy, but i don't use them previously.
Is there any way to iterate over that range faster ?</p>

<p><strong>EDIT</strong>: corrected base conversion from 2 to 10 (thanks Nick A!)</p>

<p>It's not clear what <code>do_something()</code> does, but I don't think this is a senseful approach. If you have to loop over <code>2^54</code> items it simply won't ever stop because it takes so long. Let's do some math.</p>

<p>Say your loop is this:</p>

<pre><code>while i &lt; math.pow(2, 54):
  i += 1
</code></pre>

<p>You do nothing in the cycle, you just increment <code>i</code> and cycle <code>2^54</code> times.</p>

<blockquote>
  <p>You increment by 1000, which is roughly <code>2^10</code> (1024). The cycles will be <code>2^64 / 2^10 = ~2^54</code>. In my example I increment by 1, so that's why I cycle to <code>2^54</code> and not <code>2^64</code>.</p>
</blockquote>

<p>You run this single-threaded on a 4 GHz CPU (4*10^9 cycles per second).</p>

<p>Now we devide these two numbers and get the seconds it takes to compute:</p>

<pre><code>2^54 / (4 * 10^9) = ~4611686
</code></pre>

<p>I've devided by 1000 (not 1024) and rounded it down. Let's see how long those seconds are:</p>

<pre><code>76861 miutes, or
1281 hours, or
53 days
</code></pre>

<p>So, on a single-core CPU it takes 53 days (!) to just count and cycle.</p>

<blockquote>
  <p>On a 8-core CPU it would still take ~7 days... but you have to be able to implement <code>do_something()</code> for parallel execution, which is not always possible (it totally depends on what it actually does). And parallelization introduces some overhead.</p>
</blockquote>

<p>Now add in your <code>do_something()</code> function and you can imagine the general idea:</p>

<blockquote>
  <p>If an algorithm does not terminate in a relatively short time, it is as if it never ends. As such, it underlies the halting problem and therefore it is not decidable if the result is correct.</p>
</blockquote>

<p>In other words <strong>your code is wrong because it does not end in time</strong>.</p>

<p>Say you switch your computer off once a month. Anything that takes longer than a month would be plain out wrong.</p>

<p>More about the <a href="https://en.wikipedia.org/wiki/Halting_problem" rel="nofollow">halting problem here</a>.</p>

<hr>

<p><strong>EDIT</strong>: I'm wrong! It takes longer than that.</p>

<p>Your program cannot just increment <code>i</code>, you also must test it to be less than <code>2^54</code> and only loop if it's not. The least pseudo-assembler code would be:</p>

<pre><code>      MOV 2 ^ 54, i
loop: DEC i
      JNZ loop        # Jump Not Zero
</code></pre>

<p>You need at least 2 instructions in the loop.</p>

<blockquote>
  <p>x86 CPUs actually have special instructions that do all three steps at once (like <a href="http://stackoverflow.com/a/1756322/3227403">LOOP, LOOPE, LOOPNE</a>). From a comment in the link we know it takes longer than the <code>DEC/JNZ</code> combination, which takes 2 cycles.</p>
</blockquote>

<p>This means the computation will take twice as long:</p>

<pre><code>single core: ~106 days
octa-core:   ~13 days
</code></pre>

<p>But that's without doing anything useful.</p>

<p>Even if you do very simple stuff in <code>do_something()</code> it easily <strong>BLOATS</strong> those numbers up, even to years and beyond...</p>

python numpy scipy largenumber