Calculating the address of an element in an n-dimensional array

Question

In a single dimensional array the address of an element of an array say A[i] is calculated using the following formula Address of $A[i] =B+W * (i–L_B)$ where $B$ is the base address of the array, W is the size of each element in bytes, i is the subscript of an element whose address is to be found and $L_B$ is the Lower limit / Lower Bound of subscript (if not specified assume 0).

Similarly, in the case of a two-dimensional array, the address of an element of any array say A[i][j] may be calculated in 2 methods depending upon what type of ordering the array follows. In case of Row Major System, the address of the location is calculated using equation while in case of Column Major System, the address of the location is calculated using the equation where, B = Base address, i = Row subscript of an element whose address is to be found, j = Column subscript of an element whose address is to be found, W = Storage Size of one element stored in the array (in byte), Lr = Lower limit of row/start row index of the matrix, if not given assume 0 (zero), Lc = Lower limit of column/start column index of the matrix, if not given assume 0 (zero), M = Number of rows of the given matrix, N = Number of columns of the given matrix.

Row Major:Address of $A[i][j] =B+W * [N * (i - L_r) +(j-L_c)] $

Column Major:Address of $A[i][j] =B+W*[(i – L_r)+M*(j -L_c)] $

So how can we devise an equation to find the address of the cell of a k-dimensional array considering the base address as B, Storage Size of one element stored in the array as W (in byte), $L_k$ as the lower limit of the kth dimension and $N_1, N_2…N_k$ be the dimension of the array along the kth direction?

My approach is as follows here:

If we see the formulae we understand that there is a certain the address of different dimensions follow a pattern

$A[i] =B+W*(i–L_B)$----->1 D Matrix

$A[i][j] =B+W * [N * (i - L_r) +(j-L_c)]$------->2 D Matrix(Row Major Formula,Where N is the 2nd index or the column,Mis the 1st index or the row number)

By the pattern here...

$A[i][j][k]=B+W * [(i - L_1)*n*p + p*(j-L_2) + (k-L_3)]$---->3 D Matrix with the 3 dimensions as m rows,n columns and p height variables.

Then how can we change this problem to an induction problem and proceed? Other ways to are welcome.

As I want to understand how this can go by induction that's why I have uploaded in maths StackExchange.

Answer 1

I would say that \begin{equation} A[i_1]\cdots[i_k] = B + W f(i_1-L_1, \ldots, i_k-L_k) \end{equation} where for $k>1$ and $0\le i'_p < N_p$ \begin{equation} f(i'_1,\ldots, i'_k) = f(i'_1,\ldots, i'_{k-1})N_k + i'_k \end{equation} and \begin{equation} f(i'_1) = i'_1 \end{equation}

Edit: to answer @user57048 's comment, the idea here is that the quantity $f(i'_1, \ldots,i'_k)$ is an integer in $[0, N_1 ...N_k)$, the index of a logical position where to insert an array element. When the array grows from $k-1$ directions to $k$ directions, the function $f(i'_1, \ldots,i'_{k-1})$ defines only $N_1\ldots N_{k-1}$ positions. The idea is to gain free space for the $k$-th direction by multiplying the positions by $N_k$. For example, if $N_k=10$ and we have the positions $... 11, 12, 13, ...$, by multiplying these positions by $10$, we now have $... 110, 120, 130, ...$. This creates the space for the $k$-th direction because between $110$ and $120$ for example we now have $10$ free positions where to insert array elements, namely $110, 111,\ldots, 119$, that is to say $110 + i'_k$ with $0\le i'_k < N_k$. I hope it helps understanding the above formula.

Edit: One can also write a generalized "column major formula" by defining $P_k=N_1\ldots N_k$ and use instead of $f$ a function $g$ defined inductively by \begin{equation} g(i'_1,\ldots,i'_k) = g(i'_1,\ldots,i'_{k-1}) + i'_k P_{k-1},\qquad k>1 \end{equation} and \begin{equation} g(i'_1) = i'_1 \end{equation}