title: n-squared / 2 chunking for parallel processing
body: <p>I have an n-squared loop that I want to break up into chunks to run concurrently. The loop looks like this:</p>
  
  <pre><code>for i = n to m
      for j = i to m
         // Do something
  </code></pre>
  
  <p><strong>Edit based on comment:</strong>
  Concrete example with n = 0, m = 60000:</p>
  
  <pre><code>for i = 0 to 60000
    for j = i to 60000
  </code></pre>
  
  <p>So, I am not really doing n-squared iterations, but, n-squared / 2. As i gets greater, the number of iterations in the inner look becomes less.</p>
  
  <p>Let's say n = 0 and m = 60000, and I want to break this into 5 separate processes to be run on parallel. How do I chose n and m so that the 5 different processes have equal iterations?</p>
  
  <p>I know 60000 / 5 = 12000. So, we could break it up like this:</p>
  
  <pre><code>0 - 11999
  12000 - 23999
  24000 - 35999
  36000 - 47999
  48000 - 60000
  </code></pre>
  
  <p>The idea is to break this up into x loops (Where x is 5 here) with equal numbers of iterations. Something like this:</p>
  
  <pre><code>for i = 0 to 11999
      for j = i to 60000
  
  for i = 12000 to 23999
      for j = i to 60000
  
  for i = 24000 to 35999
      for j = i to 60000
  
  for i = 36000 to 47999
      for j = i to 60000
  
  for i = 48000 to 60000
      for j = i to 60000
  </code></pre>
  
  <p>But, the loops at the end will have less comparisons. So, this is not the right answer. </p>
  
  <p>Seems like this is a calculus problem where you need to figure out equal areas under a curve. But, that math is about 20 years rusty for me. I am, of course, looking for a general solution given n = 0 and m > 0.</p>
  
  <p><strong>Edit 2:</strong>
  Clarification to the problem above.</p>
  
  <p>Thanks</p>