Position item in an array larger than 3D

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

Position item in an array larger than 3D

Post by lrcvs »

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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

Post by Richard »

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: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Position item in an array larger than 3D

Post by dodicat »

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
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Post by fxm »

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
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Post by fxm »

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: 578
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Post by lrcvs »

Hi all!

Richard, Dodicat, Fxm:

Firstly thank you for your interest in my question.

I have not had time to test your example.

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
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Post by fxm »

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: 578
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Post by lrcvs »

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

Re: Position item in an array larger than 3D

Post by codeFoil »

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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

Post by Richard »

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: 578
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Post by lrcvs »

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: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Position item in an array larger than 3D

Post by Richard »

@Ircvs. I am sorry if we have taken over your thread.

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: 578
Joined: Mar 06, 2008 19:27
Location: Spain

Re: Position item in an array larger than 3D

Post by lrcvs »

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

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

Re: Position item in an array larger than 3D

Post by dodicat »

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
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Position item in an array larger than 3D

Post by fxm »

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
Post Reply