I have a flattened 3D array in row-major format with an index, $I$, defined as $I = x + y D_x + z D_x D_y$, where $x$, $y$, and $z$ are the indices and $D_x$, $D_y$, and $D_z$ are the dimensions of the 3D array. How can I obtain the original set of coordinates from the index $I$?
(This question has been asked a number of other places on StackExchange with no actual derivation of the solution.)
We start with the standard definition of integer division: $a = qd +r$, where $a$ is the dividend, $q$ is the quotient, $d$ is the divisor, and $r$ is the remainder. From here, we define the integer division operator $div(a, d)=q$ and the modulo operator $mod(a, d) = r$.
Starting with our index, $$I = x + y D_x + z D_x D_y$$
Rewriting to fit the division form above, $$I = D_x (y + z D_y) + x$$
We can now solve for $x$: $$mod(I, D_x) = x$$
Now for $y$ and $z$, we extract the inner expression: $$div(I, D_x) = y + D_y z$$
But, this has the same form as the expresion for $x$. Thus, $$mod(div(I, D_x), D_y) = y$$ $$div(div(I, D_x), D_y) = z$$
Note: this derivation extends quite easily to higher dimensions.