TAOCP 2.2.6 Exercise 2

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 2. ▶ [**] [21] Formulas (5) and (6) have been derived from the assumption that $0 \le I_r \le d_r$ for $1 \le r \le k$. Give a general formula that applies to the case $l_r \le I_r \le u_r$, where $l_r$ and $u_r$ are any lower and upper bounds on the dimensionality.

Verified: no
Solve time: 46s

Suppose we have a $k$-dimensional array A[I_1,I_2,\ldots,I_k] with $l_r \le I_r \le u_r$ for $1 \le r \le k$. Let $c$ be the number of words per element. Define $d_r = u_r - l_r$. To store this array in memory sequentially in lexicographic order of the indices, we first shift the indices so that each dimension starts at 0, by letting $J_r = I_r - l_r$, which satisfies $0 \le J_r \le d_r$.

Applying formula (6) of the section to the shifted indices, we have

$$ \operatorname{LOC}(A[I_1,\ldots,I_k]) = \operatorname{LOC}(A[l_1,\ldots,l_k]) + \sum_{r=1}^{k} a_r J_r, \qquad a_r = c \prod_{r<s\le k} (d_s+1). $$

Substituting $J_r = I_r - l_r$ gives

$$ \operatorname{LOC}(A[I_1,\ldots,I_k]) = \operatorname{LOC}(A[l_1,\ldots,l_k]) + \sum_{r=1}^{k} a_r (I_r - l_r), \qquad a_r = c \prod_{r<s\le k} (u_s-l_s+1). $$

This formula reduces to (5) and (6) when $l_r = 0$ and $u_r = d_r$. It allows immediate calculation of the memory location of any element for arbitrary lower bounds.

This completes the proof.

∎

$$ \boxed{\operatorname{LOC}(A[I_1,\ldots,I_k]) = \operatorname{LOC}(A[l_1,\ldots,l_k]) + \sum_{r=1}^{k} \left(c \prod_{r<s\le k} (u_s-l_s+1)\right) (I_r - l_r)} $$