Position item in an array larger than 3D

General FreeBASIC programming questions.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Position item in an array larger than 3D

Code: Select all

Question:

How to find the position that has an element of an array / vector / multidimensional array, using a mathematical formula?

For example, in a 2D array of 4 x 4

A B C D
E F G H
I J K L
M N O P

A 1D 2D array = Array = ABCDEFGHIJKLMNOP
Position = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16. Ok!

Then, the position Rowx = 3, colx = 3, position = 11 & content = K

Formula: ((Rowx -1) * col) + colx

= ((3 - 1) * 4) + 3 = Position 11 = element = K

:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::

Now in a 3D array = 4 x 4 x 4

1D = 3D = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... 60 61 62 63 64
POSITION 63 = CONTENT = 63

level 1

1 2 3 4
5 7 7 8
9 10 11 12
13 14 15 16

level 2

17 18 19 20
21 22 23 24
25 26 27 28
29 30 31 32

level 3

33 34 35 36
37 38 39 40
41 42 43 44
45 46 47 48

level 4

49 50 51 52
53 54 55 56
57 58 59 60
61 62 63 64

Example: Row 4 x column 3 x Level 4 = 4x3x4 = 63 Position 63 = Element

3D position pa Formula:

((Rowx - 1) * col) + colx + ((rows * cols) * (level -1))

((4 - 1) * 4 * 4) + 3 + ((4 * 4) * (4 - 1)) = POSITION 63 = content = 63

:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::

So my question is:

What is the formula to find the position within an array larger than 4 or 5 or 20?

Thanks"
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

This code finds the array descriptor in FB. I'm sorry it only finds one dimension, but it shows what information is available in the descriptor for computation of pointer addresses. You can expand it to more dimensions by adding lines.

Code: Select all

'=======================================================================
' Local Array Descriptor is in the stack
'=======================================================================
Dim As Integer j = 1, k = 8

'=======================================================================
' keep this block together because the relative positions of the array
' descriptor and ip, referenced by ebp in the stack frame, is critical.
Dim As Double x(j To k)     ' creates  descriptor  in the stack frame
Dim As Integer Pointer ip   ' creates  ip  4 bytes below in the frame
ip = Cptr(Integer Ptr, @ip + 1) ' ip should now point at the descriptor
' @ip is a "Ptr" to an "Integer Ptr" so it must be changed back
'=======================================================================
Print Hex(ip, 8); "  ip  address of descriptor in stack "
Print

'-----------------------------------------------------------------------
Print Hex(@x(j), 8); "  @x(j)  address of lowest element  "
Print Hex(@x(k), 8); "  @x(k)  address of highest element "
Print

'-----------------------------------------------------------------------
Print "Descriptor "
Print Hex(*(ip+0), 8); "  element(zero) address for indexing "
Print Hex(*(ip+1), 8); "  base address of allocated memory "
Print Hex(*(ip+2), 8); "  total allocated memory in bytes "
Print Hex(*(ip+3), 8); "  element size in bytes "
Print Hex(*(ip+4), 8); "  number of dimensions "
Print
Print Hex(*(ip+5), 8); "  number of elements in dimension "
Print Hex(*(ip+6), 8); "  lower bound of dimension "
Print Hex(*(ip+7), 8); "  upper bound of dimension "
Print

'-----------------------------------------------------------------------
' if it passes these tests then it probably found the descriptor OK
'-----------------------------------------------------------------------
' test to detect position disagreement of lowest element
If @x(j) <> *(ip+1) Then
Color 14
Print "Fault in descriptor position or values "
Print Hex(  @x(j), 8); "  base element "
Print Hex(*(ip+1), 8); "  base memory "
Print
Sleep
End If

'-----------------------------------------------------------------------
' test if  memory_allocated = element_size * number_elements
If *(ip+2) <> (*(ip+3) * *(ip+5)) Then
Color 14
Print "Suspicious allocated memory space error "
Print
Sleep
End If

'-----------------------------------------------------------------------
' check that upper and lower bounds match the element(zero) address
Dim As Integer z = Cint(@x(j)) - (j*(Cint(@x(k)) - Cint(@x(j))) \ (k - j))
If z <> *ip Then
Color 14
Print " faulty bounds or zero index interpolation value "
Print Hex(  z, 8); "  interpolated "
Print Hex(*ip, 8); "  descriptor "
Print
Sleep
End If

'=======================================================================
' to align array elements
Dim As Integer ByteAlign = 16
Dim As Integer np = 1 + (((*ip) - 1) Or (ByteAlign - 1))
Print  Hex( *ip, 8); "  old base "
Print  Hex(  np, 8); "  new base "

Dim As Integer Pointer upper_bound = ip + 7
print hex(*upper_bound , 8); "  old upper bound "
*ip = np            ' adjust the zero index pointer up a few bytes
*(ip+7) = *(ip+7)-1 ' reduce upper bound to enable bounds checking
print hex(*upper_bound , 8); "  new upper bound "

'-----------------------------------------------------------------------
Print
Print "normal exit encountered "

'=======================================================================
Sleep
'=======================================================================

dodicat
Posts: 6633
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Position item in an array larger than 3D

Here's a formula method for arrays up to six dimensions, for more you can extend.

Code: Select all

'=================================================
#define ub ubound
#define lb lbound
#define _r(arr,n) (ub(arr,n)-lb(arr,n)+1)

#define d1(a,i) (i-lb(a,1))
#define d2(a,i,j) (_r(a,2)*d1(a,i)+(j-lb(a,2)))
#define d3(a,i,j,k) (_r(a,3)*d2(a,i,j)+(k-lb(a,3)))
#define d4(a,i,j,k,l) (_r(a,4)*d3(a,i,j,k)+(l-lb(a,4)))
#define d5(a,i,j,k,l,m) (_r(a,5)*d4(a,i,j,k,l)+(m-lb(a,5)))
#define d6(a,i,j,k,l,m,n) (_r(a,6)*d5(a,i,j,k,l,m)+(n-lb(a,6)))
'Build more if needed
'==================================================
dim as string array(1 to 6,3 to 8,0 to 4,1 to 5,2 to 4,8 to 10)

print d6(array,1,3,0,1,2,8),"Start"
print d6(array,2,5,3,3,3,9),"Somewhere in the middle"
print d6(array,6,8,4,5,4,10),"End"
sleep

fxm
Posts: 9813
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Yes dodicat. This is a good recursive calculation method using macros.
We can verify the result with:

Code: Select all

Dim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)

Print @array(1,3,0,1,2,8) - @array(1,3,0,1,2,8),"Start"
Print @array(2,5,3,3,3,9) - @array(1,3,0,1,2,8),"Somewhere in the middle"
Print @array(6,8,4,5,4,10) - @array(1,3,0,1,2,8),"End"
Sleep

Another algorithm, but very rustic:

Code: Select all

Function offset6(array() As String, _
Byval I1 As Integer, _
Byval I2 As Integer, _
Byval I3 As Integer, _
Byval I4 As Integer, _
Byval I5 As Integer, _
Byval I6 As Integer) As Integer
Dim I As Integer
For K1 As Integer = Lbound(array,1) To Ubound(array,1)
For K2 As Integer = Lbound(array,2) To Ubound(array,2)
For K3 As Integer = Lbound(array,3) To Ubound(array,3)
For K4 As Integer = Lbound(array,4) To Ubound(array,4)
For K5 As Integer = Lbound(array,5) To Ubound(array,5)
For K6 As Integer = Lbound(array,6) To Ubound(array,6)
If I1 = K1 And I2 = K2 And I3 = K3 And I4 = K4 And I5 = K5 And I6 = K6 Then
Return I
Else
I = I + 1
End If
Next K6
Next K5
Next K4
Next K3
Next K2
Next K1
End Function

Dim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)

Print offset6(array(),1,3,0,1,2,8),"Start"
Print Offset6(array(),2,5,3,3,3,9),"Somewhere in the middle"
Print Offset6(array(),6,8,4,5,4,10),"End"
Sleep
fxm
Posts: 9813
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Same principle as dodicat, but using a true recursive function.
This recursive function is applicable to any number of dimensions:
(the number of dimensions is the parameter 'N')

Code: Select all

Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer
If N = 0 Then
Return 0
Else
Return offset(array(),I(),N-1)*(Ubound(array,N)-Lbound(array,N)+1)+I(N)-Lbound(array,N)
End If
End Function

Dim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)

Dim As Integer I1(1 To 6) = {1,3,0,1,2,8}
Print offset(array(),I1(),6),"Start"

Dim As Integer I2(1 To 6) = {2,5,3,3,3,9}
Print Offset(array(),I2(),6),"Somewhere in the middle"

Dim As Integer I3(1 To 6) = {6,8,4,5,4,10}
Print Offset(array(),I3(),6),"End"

Sleep
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Hi all!

Richard, Dodicat, Fxm:

Firstly thank you for your interest in my question.

All three are very interesting, but I think the example of Dodicat,

to me may be the most interesting, as it uses formulas and I have no loop "For / Next" or similar.

The application of a formula is faster than multiple loops.

I will try tonight to try the three examples.

Thank you very much everyone!

Regards
fxm
Posts: 9813
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

lrcvs wrote:The application of a formula is faster than multiple loops.

Why a great constraint on the execution speed of the offset computation?
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

I do not understand the question?
codeFoil
Posts: 255
Joined: Dec 22, 2011 4:45
Location: United States
Contact:

Re: Position item in an array larger than 3D

In other words, for what purpose is your calculation intended? As you can see, there are always several ways to approach a problem, but without knowing what your goal is, others may over look an obvious solution and steer you toward an "optimal" self defeating approach.
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

I assumed the array already existed and Ircvs wanted to use pointers or assembly code for access.
I once started to write a converter for “Row major” to “Column major” translation of any arity.
FB could support both systems since the difference is only the forward or reverse application of the indexes in the recursive solution.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Hi all!

Codefoil, Richard:

The ultimate goal of my question is to show that a possible mathematical formula, we can find any element in an array multideminsional, more efficiently than using loops "For / Next".

Richard:
My computer skills / Basic, sonlos of a child in a kindergarten, are very low.

Also, I am too old to learn assembler or machine code, for me, is unthinkable!

Regards
Richard
Posts: 3029
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

Assembly code is fun! IA32 is much easier than the old x86 segment addressed code.
You can play with asm blocks inside an FB program. You are never too old to have fun.
lrcvs
Posts: 576
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Sure, you're never too old for anything important, and above all learn!

Regards
dodicat
Posts: 6633
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Position item in an array larger than 3D

Richard's and fxm's snippets very enlightening.
I've messed about here with some asm code I dug out from the forum.
The scenario:
Somebody gives you an array (string here), and you haven't a clue what it is.
How this could come about I couldn't imagine, but it has happened.
You must investigate the array and get it's range, then pick a point in the middle.
(Perhaps fxm could overload his function sometime)
This is just a bit of fun, not to be used for mission critical work, but you can do it at home.

Code: Select all

'=================================================
#macro getdim(d)
Asm
mov esi, [ebp+8]
mov eax, [esi+16]
mov [d], eax
End Asm
#endmacro
Function DIMENSION overload (array() As Integer) As Integer
Dim d As Integer
getdim(d)
Return d
End Function
Function DIMENSION overload (array() As single) As Integer
Dim d As Integer
getdim(d)
Return d
End Function
Function DIMENSION overload (array() As double) As Integer
Dim d As Integer
getdim(d)
Return d
End Function
Function DIMENSION overload (array() As string) As Integer
Dim d As Integer
getdim(d)
Return d
End Function
'===================================================== FXM
Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer
If N = 0 Then
Return 0
Else
Return offset(array(),I(),N-1)*(Ubound(array,N)-Lbound(array,N)+1)+I(N)-Lbound(array,N)
End If
End Function

'========================================
function post(n as integer) as string'(for st,nd,rd etc)
dim as string d=" "+str(n),t
If Left(d,1)<>"1" Then
Select Case  Right(d,1)
Case "1":t="st"
Case "2":t="nd"
Case "3": t="rd"
Case Else:t="th"
End Select
Else
t="th"
End If
return t
end function
'=========================================================
'Some unknown string array:
Dim As String array(1 To 6,3 To 8,0 To 4,1 To 5,2 To 4,8 To 10)
'=========================================================

dim as integer n=DIMENSION(array())

dim as integer I1(1 to n),I3(1 to n)

For x As Integer  = 1 To n
I1(x)=Lbound(array,x)
Print "Lowerbound of ";x & post(x);" dimension ";Lbound(array,x)
I3(x)=ubound(array,x)
Print "Upperbound of ";x & post(x);" dimension ";Ubound(array,x)
Print
Next x

Print "Dimension of array (as can be seen)= ";n
print

Print offset(array(),I1(),n),"Start"
Print Offset(array(),I3(),n),"End"
print "Now we can pick somewhere in the middle e.g 2,5,3,3,3,9"

Dim As Integer I2(1 To 6) = {2,5,3,3,3,9}
Print Offset(array(),I2(),6),"Somewhere in the middle"

Sleep

fxm
Posts: 9813
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

dodicat wrote:(Perhaps fxm could overload his function sometime)

Any terminal recursion can be easily converted into a loop (no more risk of stack overflow, faster, but a little less compact code).

- Compacted function using recursion:

Code: Select all

Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer
If N > 0 Then
Return offset(array(),I(),N-1)*(Ubound(array,N)-Lbound(array,N)+1)+I(N)-Lbound(array,N)
End If
End Function

- Less compact function using loop:

Code: Select all

Function offset(array() As String,I() As Integer,Byval N As Integer) As Integer
Dim K As integer
For J As Integer = 1 To N
K = K*(Ubound(array,J)-Lbound(array,J)+1)+I(J)-Lbound(array,J)
Next J
Return K
End Function