Finding FORTRAN array location, 4-dimensional array

Hey guys, I have a question. If given a four dimensional array in FORTRAN, and told to find a location of a certain开发者_StackOverflow part of it (with a starting location of 200 and 4 bytes per integer). Is there a formula to find the location if is stored in row-major and column-major order.

Basiically given array A(x:X, y:Y, z:Z, q:q) and told to find the location at A(a,b,c,d) what is the formula for finding the location

This comes up all the time when using C libraries with Fortran -- eg, calling MPI routines trying to send particular subsets of Fortran arrays.

Fortran is row-major, or more usefully, the first index moves fastest. That is, the item after A(1,2,3,4) in linear order in memory is A(2,2,3,4). So in your example above, an increase in a by one is a jump of 1 index in the array; a jump in b by one corresponds to a jump of (X-x+1); a jump in c by one corresponds to a jump of (X-x+1)x(Y-y+1), and a jump in d by one is a jump of (X-x+1)x(Y-y+1)x(Z-z+1). In C-based languages, it would be just the opposite; a jump of 1 in the d index would move you 1 index in memory; a jump in c would be a jump of (Q-q+1), etc.

If you have m indicies, and n_i is the (zero-based) index in the i^th index from the left, and that index has a range of N_i, then the (zero-based) index from the starting position is something like this:

where the product is 1 if the upper index is less than the lower index. To find the number of bytes from the start of the array, you'd multiply that by the size of the object, eg 4 bytes for 32-bit integers.

Been over 25 years since I did any FORTRAN.

I believe FORTRAN, unlike many other languages, lays arrays out in column major order. That means the leftmost index is the one that changes most frequently when processing a multi dimensional array in linear order. Once the maximum dimension of the leftmost index is reached, set it back to 1, assuming 1 based indexing, and increment the next level index by 1 and start the process over again.

To calculate the index configuration for any given address offset you need to know the value of each of the 4 array dimensions. Without this you can't do it.

Example:

Suppose your array has dimensions 2 by 3 by 4 by 5. This implies a total of 2 * 3 * 4 * 5 = 120 cells in the matrix. You want the index corresponding to the 200th byte. This would be the (200 / 4) - 1 = 49th cell (this assumes 4 bytes per cell and offset zero is the first cell).

First observe how specific indices translate into offsets...

What cell number does the element X(1,1,1,1) occur at? Simple answer: 1 What cell number does element X(1, 2, 1, 1) occur at? Since we cycled through the leftmost dimension it must be that dimension plus 1. In other words, 2 + 1 = 3. How about X(1, 1, 2, 1)? We cycled trough the first two dimensions which is 2 * 3 = 6 plus 1 to give us 7. Finally X(1, 1, 1, 2) must be: 2 * 3 * 4 = 24 plus 1 gives the 25th cell.

Notice that the next righmost index does not increment until the cell number exceeds the product of the indices to its left. Using this observation you can calculate the indices for any given cell number by working from the rightmost index to the left most as follows:

Right most index increments every (2 * 3 * 4 = 24) cells. 24 goes into 49 (the cell number we want to find the indexing for) twice leaving 1 left over. Add 1 (for 1 based indexing) that gives us a rightmost index value of 2 + 1 = 3. Next index (moving left) changes every (2 * 3 = 12) cells. One goes into 12 zero times, this gives us index 0 + 1 = 1. Next index changes every 2 cells. One goes into 2 zero times giving an incex value of 1. For the last (leftmost index) just add 1 to whatever is left over, 1 + 1 = 2. This gives us the following reference X(2, 1, 1, 2).

Double check by working it back to an offset:

((2 - 1) + ((1 - 1) * 2) + ((1 - 1) * 2 * 3) + ((3 - 1) * 2 * 3 * 4) = 49.

Just change the numbers and use the same process for any number of dimensions and/or offsets.

Fortran has column-major order for arrays. This is described at http://en.wikipedia.org/wiki/Row-major_order#Column-major_order. Further down in that article there is the equation for the memory offset of a higher dimensional array.