title: Cache Oblivious Matrix Transposition Implementation in C++
body: <p>I have implemented an in-place cache-oblivious matrix transposition algorithm in C++ as below:</p>
  
  <pre><code>void CacheObliviousTransposition(int x, int delx, int y, int dely, int N, int* matrix) {
      if ((delx == 1) &amp;&amp; (dely == 1)) {
          int tmp = matrix[(N*y) + x];
          matrix[(N*y) + x] = matrix[(N*x) + y];
          matrix[(N*x) + y] = tmp;
          return;
      }
  
      if (delx &gt;= dely) {
          int xmid = delx / 2;
          CacheObliviousTransposition(x, xmid, y, dely, N, matrix);
          CacheObliviousTransposition(x + xmid, delx - xmid, y, dely, N, matrix);
          return;
      }
  
      int ymid = dely / 2;
      CacheObliviousTransposition(x, delx, y, ymid, N, matrix);
      CacheObliviousTransposition(x, delx, y + ymid, dely - ymid, N, matrix);
  }
  </code></pre>
  
  <p>However, when I called the below method after transposition to ensure that it worked correctly, the if loop is being entered so I'm assuming something must be wrong with the implementation.</p>
  
  <pre><code>void CheckTransposition(int N, int* matrix)
  {
      for (int i = 0; i &lt; N; i++)
      {
          for (int j = 0; j &lt; N; j++)
          {
              if (matrix[(i*N) + j] != (j*N) + i + 42)
              {
                  cout &lt;&lt; "Transposition failed at i=" &lt;&lt; i &lt;&lt; ", j=" &lt;&lt; j &lt;&lt; "\n";
              } 
          }
      }
  }
  </code></pre>
  
  <p>Can anyone help me identify what is wrong?</p>
  
  <p>Note: variable matrix is a dynamically assigned integer array as below, as matrix is stored row by row in N*N consecutive memory locations</p>
  
  <pre><code>int* MatrixInit(int N)
  {
  
      int* matrix = new int[N*N];
  
      for (int i = 0; i &lt; N; i++) {
          for (int j = 0; j &lt; N; j++) {
              matrix[(i*N) + j] = (i*N) + j + 42;
          }
      }
  
      return matrix;
  }
  </code></pre>