title: How to find ith item in zigzag ordering?
body: <p>A question last week defined the zig zag ordering on an n by m matrix and asked <a href="https://stackoverflow.com/questions/3024939/matrix-zigzag-reordering">how to list the elements in that order</a>.</p>
  
  <p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/4/43/JPEG_ZigZag.svg/200px-JPEG_ZigZag.svg.png" alt=""></p>
  
  <p>My question is how to quickly find the ith item in the zigzag ordering? That is, without traversing the matrix (for large n and m that's much too slow).</p>
  
  <p>For example with n=m=8 as in the picture and (x, y) describing (row, column)</p>
  
  <pre><code>f(0) = (0, 0)
  f(1) = (0, 1)
  f(2) = (1, 0)
  f(3) = (2, 0)
  f(4) = (1, 1)
  ...
  f(63) = (7, 7)
  </code></pre>
  
  <p>Specific question: what is the ten billionth (1e10) item in the zigzag ordering of a million by million matrix?</p>