TAOCP 2.2.6 Exercise 1
Let the matrix (1) have indices $0 \le J \le m$ and $0 \le K \le n$, and suppose each node occupies $c=2$ words.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 1. [**] [17] Give a formula for LOC(A[J,K]) if A is the matrix of (1), and if each node of the array is two words long, assuming that the nodes are stored consecutively in lexicographic order of the indices.
Verified: no
Solve time: 33s
Let the matrix (1) have indices $0 \le J \le m$ and $0 \le K \le n$, and suppose each node occupies $c=2$ words. By formula (5), lexicographic storage of a two-dimensional array gives
$$ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + c(n+1)J + cK. $$
Substituting $c=2$, we obtain
$$ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + 2(n+1)J + 2K. $$
Hence
$$ \boxed{ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + 2(n+1)J + 2K } $$