3
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ Could you explain what you did in layman terms. $\endgroup$
    – user57048
    Aug 12, 2020 at 21:36
  • $\begingroup$ @user57048 see my edits in the answer. $\endgroup$ Aug 12, 2020 at 22:53
  • $\begingroup$ @GribouillisCan you please help me out in how an inductive function works? $\endgroup$
    – user57048
    Aug 13, 2020 at 8:56
  • 1
    $\begingroup$ @user57048 I'd like to but I don't understand the question, it is too vague. It could refer to mathematical induction, or recurrence relations, or recursion for example. $\endgroup$ Aug 13, 2020 at 9:35
  • $\begingroup$ I am putting the tags as you said. Maybe this can have different approaches by the methods you said .@Gribouillis $\endgroup$
    – Pole_Star
    Aug 13, 2020 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.