GATE CSE 2014 Set 2 | Question: 34

Question

For a C program accessing $\mathbf{X[i] [j] [k]}$, the following intermediate code is generated by a compiler. Assume that the size of an integer is $32$ bits and the size of a character is $8$ bits. 

t0 = i ∗ 1024 
t1 = j ∗ 32
t2 = k ∗ 4 
t3 = t1 + t0 
t4 = t3 + t2 
t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

• A. $\mathbf{X}$ is declared as "int $\mathbf{X[32] [32] [8]}$”.
• B. $\mathbf{X}$ is declared as "int $\mathbf{X[4] [1024] [32]}$”.
• C. $\mathbf{X}$ is declared as "char $\mathbf{X[4] [32] [8]}$”.
• D. $\mathbf{X}$ is declared as "char $\mathbf{X[32] [16] [2]}$”.

Comments

Can it be written like this?

t5 = X[ t4 ]

     = X [ t3 ] [ t2 ]

     = X [ to ] [ t1 ] [ t2 ]

     = X [ i*1024 ][  j *32 ][ k * 4 ]

     = X [ i * ( j * ( k * 4 ) ) ][ j * ( k * 4 )][ k * 4 ]  ( multiplication by 4 is due to 32 bit ( or 4 B) integer )

From here clearly option A) is the answer.

---

$(i\times j\times k+ j\times k+ k)\times 4\ bytes$

$Put\ A)\ values\ "intX[32][32][8]"\ above$

$=(32\times 32\times 8+32\times 8+8)\times 4$

$=33824$

---

$t5=X[t4]$

$t4=t3+t2$

     $=t0+t1+k\times 4$

     $=i\times 1024+j\times 32+k\times 4$

$Put\ A)\ values\ "intX[32][32][8]"\ in\ 't4'$

$=32\times 1024+ 32\times 32+ 8\times 4$

$=33824$

---

$Ans: A$

In order to visualize what exactly is happening: Refer here

---

Trial and error kind of method:
form the equation for address at A[i][j][k], which will be 1024i+32j+4k.

That makes A[0][0][0], 0.

similarly A[0][1][0] = 32, A[0][2][0] = 64, ie incrementing by 32 implying a 32 bit integer. (C and D eliminated)
Now A[1][0][0] = 1024, which means A[0][j_max][0] – 1024-32 = 992, and 992/32 = 31.
j_max = 31, and 31-0+1, 32 integers.

---

Found this beautiful explanation:

https://www.youtube.com/watch?v=bMJn1ZagJk4&list=PL4hV_Krcqz_Itby1KA3caCvut2JntP6jD&index=275&ab_channel=SuccessGATEway

Answer 1

The final expression can be simplified in form ofi, j and k by following the intermediate code steps in reverse order

t5 = X[t4]
   = X[t3 + t2]
   = X[t1 + t0 + t2]
   = X[i*1024 + j*32 + k*4]
   = X + i*1024 + j*32 + k*4 

Since k is multiplied by 4, the array must be an int array. We are left with 2 choices (A and B) among the 4 given choices. X[i][j][k]'th element in one dimensional array is equivalent to X[i*M*L + j*L + k]'th element in one dimensional array (Note that multi-dimensional arrays are stored in row major order in C). So we get following equations

j*L*4 = j*32, we get L = 8 (4 is the sizeof(int))
i*1024 = i*M*L*4, we get M = 1024/32 = 32

Therefore option A is the only correct option as M and L are 32 and 8 respectively only in option A.

Comments

It's size of data type mentioned in question.i.e., 32 and 8

---

@Regina Phalange Ma'am why we are multiply j with L  like j*L and for i with M*L

Also how are you evaluating this   X + i*1024 + j*32 + k*4 to X[i*M*L + j*L + k]?

from where did this X[i*M*L + j*L + k] came?

---

This is answer for me. Thanks

If given permission , I would have up voted answer at least 10 times

Answer 2

Answer - A

Explanation - 

Element needed - X[i][j][k]

A 3D array is a collection of 2D arrays and a 2D array is a collection of 1D arrays, and a 1D array is a collection of elements.

So, we need to first cross the required no. of 2D arrays(no. of elements in 1 2D array * i), then the required no. of 1D arrays(no. of elements in 1 1D array(no. of rows in 1 2D array) * j) in our reached 2D array, and then the required no. of elements in our reached 1D array(k).

1. We have t0 = i * 1024, which means that there are 1024 elements in 1 2D array.

2. We have t1 = j * 32, which means that we have 32 elements in 1 1D array of our 2D arrays or in other words, the no. of rows of our 2D array is 32, so the no. of columns can easily be found by 1024 / 32 = 32. 

So now we have the dimensions of our 2D arrays = 32*32.

so clearly our answer is A (no other close option).

elaborating further, 

3. We have calculated t3 of our 3-address code = (i * (32*32)) + (j * 32) + k.

4.We now need to multiply the above expression with the size of the datatype. 

Since we have t2 = k * 4, it clearly means that the size of our datatype of each element is 4 bytes, hence an int. 

And the expression t4 of our 3-address code in high level language is - ((i * (32*32)) + (j * 32) + k) * 4

5. t5 gives the specific element. 

Conclusion - our required 3D array is - x[32][32][8] and it is of type integer. 

Note - There is no way of finding out the 3rd dimension of our 3D array, here 8 with the help of our 3-address code, since its not required in the calculation of an element's location.

Comments

@ ravi_ssj4

Sir, I think u have made a mistake in point 2. j is the number of rows and 32 is the number of elements in each row, although this should not effect final answer.

And I could not understand why they have multiplied k by 4. If it is size of each element of the array, then why multiply k alone, why not all the remaining elements in the 2D and 1D arrays we have surpassed to reach the desired element.

Answer 3

Prerequisite: The visualisation of multidimensional arrays.

---

How do we get to $A[i][j]$ ? (in RMO)

From the base address, we skip $i$ rows and $j$ columns. This is quite well known.

See this or this for example.

 

Actually, a better perspective is to see it as skipping $i$ arrays and $j$ elements.

An even better perspective is to look at it as skipping $i$ $1D$ arrays, and $j$ elements.

 

By extending this, $A[i][j][k]$ is nothing but skipping $i$ $2D$ arrays, $j$ $1D$ arrays and $k$ elements. You can extend this generalised perspective to any number of dimensions.

 

Now,

t0 = i ∗ 1024 
t1 = j ∗ 32
t2 = k ∗ 4 

This is nothing but "skipping". Start from the innermost index. We're skipping $k$ by multiples of $4$. So, single-elements in the array occupy space of $4$ (Bytes). Hence, we're dealing with ints.

 

We're skipping $j$ by multiples of $32$. This means the $1D$ "sub-arrays" are of size $32$ (Bytes).

//Visualisation of multidimensional arrays is needed. If you don't know how to picturise it, I'll draw that in the comments.

 

Size of the $1D$ array = $32$ .

Number of elements = $\frac{32}{4}=8$

So, the last array subscript has a size 8.

 

With this knowledge, Option A is the answer.

But let's continue.

 

We're skipping $i$ by multiples of $1024$. This means the $2D$ "sub-arrays" are of size $1024$ (Bytes).

Number of elements in $2D$ subarrays = $\frac{1024}{32}=32$

Hence, there are $32$ $1D$ subarrays.

So the middle subscript is of size 32.

 

Nothing can be concluded about the first subscript. (Why? Hint: we don't know the total number of 2D subarrays)

 

So, we conclude the array must have been declared like: $int X[?][32][8]$

Answer 4

Size of an integer = 32 bits = 4 Bytes
Size of a character = 8 bits = 1 Byte
Let array be

            type x[A] [B] [C]
type  may be integer / character

we want  t5=x[t0+t1+t2]=x[i*1024 + j*32 + k*4 ] element,

From t0 = i *1024,
we can conclude that

          B * C * (size of type) = 1024
From t1 = j *32, we can conclude that

         C *(size of type) = 32
From t2 = k *4, we can conclude that   

         (size of type) = 4
therefore  type = int
                    C *4 = 32    => C = 8
                    B *8 * 4 = 1024 => B = 32

Choice (A)