»

[Sidewinder]

Hello all,

I am attempting to devise a formula to compute the memory address of a multi-dimensional array of arbitrary dimensions and size. So far the solution has been eluding me and I thought maybe you all could help point me in the right direction. Here's the problem:

I have a function that reserves a block of memory that is used to hold values in an array-like method. The function takes sizes of an arbitrary number of dimensions and reserves space to hold as many 4 byte integers. The trouble I'm having is finding the memory location of a specific element. I have formulas for finding the memory location of a 1-dimensional array element and a 2-dimensional array element, but I need a generic formula to find the address of an n-dimensional array element.

1-dimensional:

int base[x];
address = base[index1];

address = base + (index * sizeof(int));

2-dimensional:

int base[x][y];
address = base[index1][index2];

address = base + (index1 * x * sizeof(int)) + (index2 * sizeof(int))

n-dimensional:

int base[x][y][z][w]...;
address = base[index1][index2][index3][index4]...;

address = ???

This problem must be discussed somewhere because all C compilers use it to convert array indexes into pointer arithmetic when dealing with arrays. Does anyone have any ideas?

Thanks,

[Blitter]

This might get you pointed in the right direction.

Blitter

[Sidewinder]

@Blitter

Thanks for the prompt reply. The approach used in that example is different than the one I am using. I have one large block of contigious memory large enough to hold all the elements of the array. This example fragments the array by rows. Also, the example code deals only with 2 dimensional arrays.

I need a more generic example or formula for 3, 4, 5,..., n dimensional arrays in a contigious block of memory. :-(

I'm getting a headache.

[Blitter]

Okay, It's been a while since I've done this in C but I'll try and explain my understanding of it.

In actuality an array is a pointer to a set pf pointers, so a multi-dimentional array is a pointer to a pointer to set of pointers, etc.

I'll use a 3 dimentional array as an example.

ary[x][y][z]

so we have x number of planes that have y number of rows that has z number of colums.

Now in order to traverse every element in this multi-dimentional array we have to go through every colum of every row of every plane. But we dont't want to do that. We want the pointer of a specific element in our multi-dimetional array.

So we know what we want but how to get it? Well, since we have x planes that contain our y rows and z colums, then we can add them like this:

I'll use your example but with 3 dimentions.

int base[x][y][z];
address = base[index1][index2][index3]

address = base+(index1* x * sizeof(int))+(index2 * y * sizeof(int))+(index3 * sizeof(int))

Okay, I was going to go into n-dimentional arrays but It's getting late and I'm starting to confuse myself now. :-P

Basically for an n-dimentional array you're gonna have to create a loop to traverse your array.

If this is of no help, then I appologize. It's been quite a while since I've had to do this.

This contains more algorithyms for finding addresses.

Blitter

[Blitter]

You know, it just hit me. You stated contigious memory block. I'm not sure what I posted would work in that situation and I'd have to go back to my books to find an ABSOLUTE solution. If one of the more regular C programmers here can't help, then I'll did my books out this weekend and see what I can figure out for ya.

Also if you have time, this is an interresting read.

It's for TI-89 and TI-92+ calculators, but also covers some of the pointer inderection stuff that I wanted to get into for ya.

Blitter

[FluffyMcDeath]

The number of elements in such an array is simply
m1 x m2 x m3 x ... x mN

where any dimension has elements indexed 0 to m-1

A linear array is m1 elements,
A 2D array is m1 x m2
A 3D array is m1 x m2 x m3 etc.

The total size of memory to allocate is
number of elements x sizeof(element)

At this point, since you are doing the pointer math, you are free to arrange your data any way you wish, but probably the simplest way is to build it up a layer at a time.

Think of the number 9999 as a 4D array with m1,m2,m3 and m4 = 10 (elements 0-9) Then the simplest way to traverse all the elements is thus:
0000
0001
0002
0003 etc ...

0009
0010
0011
0012 etc ...

9998
9999

So, an element at n1,n2,n3,n4 is at

n1 + (n2 * m1) + (n3 * m1 * m2) + (n4*m1*m2*m3)

You can expand this to as many dimensions as you wish (and watch all your memory magically disappear as the storage requirements rapidly approach huge :-D ).

[Jupp3]

I also use 3-dimensional array in my game, reading and writing it directly with pointers.

For writing and reading, I use inline functions (one lined). That way I should be able to modify used methods & possibly add 4th dimension (might need that...) later rather easily...

[tonyw]

The question was "what is the general expression?"

For an n-dimensional array of elements 'type'

the declaration might be:
"type name[m1][m2][m3][ . . . ][mn];"

where "type" is int, char, etc;
"name" is the array name;
"m1", "m2" etc are the sizes of each subscript.

The address of an element (&name[M1][M2][. . . ][MN]) = (type *)name + MN * (sizeof(type) + M(N-1) * (sizeof(type) + . . . . +M1 * (sizeof(type)))))))); (N closing paren)

However, I could have it backwards, in which case, run the N -> 0 indices back the other way. Draw a sketch on a piece of paper, with the last subscript of the array changing fastest, and you should see it.


tony

[Karlos]

Multidimensional arrays can be pretty expensive to lookup, as is clear from the replies already here. To summarise, you basically end getting N-1 multiplications and N-1 additions determining the pointer position for an N-dimensional array.
A compiler usually arranges statically defined multidimensional data in a contiguous block (in first index major order). When it comes to dynamically allocated data (which is usually the case), you have to handle the lookup yourself.

In any event, you may consider redesigning your data arrangement, or access to the critical areas to it, to require fewer dimensions (if possible).

[carls]

Getting.... dizzy....

Couldn't you just make a pointer to your array element and figure out the address of where it's pointing? No maths needed. Or am I just being very silly?

I'll stick to ARexx :-)

[Nick]

Hehe I`ll stick to OPL on my PSION :-)

[bloodline]

Ok, this is how I would visulise it:

for a two dimential array
to find x,y is easy:

Data = y(Addr+x)

This treats your array like a page:

***********
***********
***********
***********

where each * represents your data

Thus for a three dimentinal array, I would think of it like a book with lots of pages:

Data=z(y(Addr+x)


Thus:

*********** *********** ***********
*********** *********** ***********
*********** *********** ***********
*********** *********** ***********

I can't visulise more than 3 dimentions (lots of books? in lots libraries in lots of cities... gah.. the list goes on...), damn my human brain, so for an array where you have n dimentions, you would need a loop to keep multiplying by n-1 until you got to n!!! wow that would use a lot of memory!!!!

I suggest you find a size you are happy with an sick to it :-D

Unless you are doing some kind of qunatum mechanics, I don't see the need for more than 4 dimentions to an array :-p

[Atheist]

index1, index2, index3....

Shouldn't index1 itself, be an array?
i.e. index(x), x increments from array to array, in a loop to max arrays you have?
index(1)= no of elements in first index
index(2)= no of elements in second index

That way, you could multiply it out before hand and see if it will overflow the ram you reserved.


AmigaOne! Move to the next dimension of power!

[holbromf]

Hi,
The important idea here is the data being contiguous in memory. This is not guaranteed.

For example: int data[20][4] give us an array of 20 pointers addressed at &data or 'data' in C. Each of these pointers is to an array of 4 integers. These integer arrays may not be contiguous in memory where one array would lead onto another. Hence a formula for the address of an element would be unreliable. This would apply whether 'data' was declared on the heap i.e. with file scope or on the stack i.e. with function scope.
A reliable technique is to declare a single array in C such as data[big] and then using formulas to find addresses in this space.

Cheers Mike

[Karlos]

One way of creating fast multidimensional lookups (ie without multiplication involved) is to create a table of pointers to pointers. This requires more memory (to hold the pointer table) but then you can get a simple lookup technique.

For example, a dynamic 2D array can be set up as follows

/* create our contiguous block memory for the objects */

size_t i;
size_t numRows = ....;
size_t numCols = ....;

Type* data = 0;
Type** rowPointer = 0;

Type* data = (Type*)malloc(sizeof(Type)*numRows*numCols);

/* create our row lookup */
Type** rowPointer = (Type**)malloc(sizeof(Type*)*numRows);

/* Fill the row lookup table */
for (i=0; i<numRows; i++)
{
&nbsp&nbsp&nbsp rowPointer[i] = &data[i*numCols];
}

/* Now, the rowPointer table contains the offsets to the start of each 'row' in our main data array, so we can access by lookup without multiplication */

Type* p = (rowPointer[rowIndex])[columnIndex];

The principal drawback of this is that you need to allocate space for the rowPointer table. This is usually a lot smaller than the main data however (each entry is just 4 bytes typically), so you might not worry about this.