EV3 CSLite C libs: matrix algebra, array sort and more

[HaWe]

hey,
where can I find "built-in" CSLite libraries and documents about
- matrix algebra (matrix multiplication, determinants, adjugates, inverse, rotation)
- sort algorithms (quick sort, heap sort, shell sort, insertion sort, bubble sort)

I'm also curious about external libs how to access daisy-chaining just like the lms VM provides it (although I guess that nothing exists like daisy chaining already).

[HaWe]

Using NQC/NXC so far after >10 years weaning of pointers I lack the exercise to pass arrays correctly to functions, especially multidimensional ones.
If no matrix algebra library already exists for CSLite - how can I mimic the following NXC code by C ?

Code: Select all

#define ArrayInit2D(array, tmp, init_val, dimx, dimy) { \
  ArrayInit(tmp, init_val, dimy);  \
  ArrayInit(array, tmp, dimx);     \
  ArrayInit(tmp,0,0);              \
}

void MatrixMatrixMult(float A[][], float B[][], float &C[][], int N, int M, int K){
  int i, j, s;
  float tmp[];
  ArrayInit2D(C,tmp, 0, N, K);
  for (i=0; i<N; ++i) {
    for (j=0; j<K; ++j) {
       C[i][j]=0;
       for (s=0; s<M; ++s) {
         C[i][j]=C[i][j] + A[i][s]*B[s][j];
      }
    }
  }
}


task main() {
    float A[2][2], B[2][2], C[2][2];
 
    A[0][0]=1;   A[0][1]=3;
    A[1][0]=2;   A[1][1]=4;
 
    B[0][0]=10;  B[0][1]=30;
    B[1][0]=20;  B[1][1]=40;
 
    MatrixMatrixMult(A,B,C, 2,2,2);  // C[2][2] is the result matrix

    // ...
}

[mightor]

I think you'll find that having something like this: http://www.gnu.org/software/gsl, would be far more useful to you than a bunch of #defines.

As for the #defines, are these dynamically allocated arrays? If that's the case, then you will have to use malloc() and possibly free() as well.
The first one would be more like

Code: Select all

// Assuming it's a char[][].
char **a;

a=(char **) malloc(10*sizeof(char *));

for(i=0;i<10;i++)
    a[i]=(char *) malloc(20*sizeof(char));

Lots more examples here: http://stackoverflow.com/questions/1970 ... onal-array. The multiplication part of the second #define will probably work, but you'll have to malloc() the space first, of course. You can see why a proper math library like the one I pasted above would make your life a lot easier

= Xander

[HaWe]

thank you,
my question actually was about how to pass multi dim arrays (matrices) to a function and get multi-dim arrays (matrices) back to the calling function, not about this #define thing (I know I have to use malloc in C - this #define ArrayBuild construct of course was only needed for NXC because there was no other way in NXC to do it C-like).

I had a look at the gsl lib, but I'm not sure about what a gsl matrix is, to me a 2-dim array (matrix) is sth like float or int a[][]
The documentation gives information just about

8.4.10 Matrix operations

The following operations are defined for real and complex matrices.

Function: int gsl_matrix_add (gsl_matrix * a, const gsl_matrix * b)

This function adds the elements of matrix b to the elements of matrix a. The result a(i,j) \leftarrow a(i,j) + b(i,j) is stored in a and b remains unchanged. The two matrices must have the same dimensions.

Function: int gsl_matrix_sub (gsl_matrix * a, const gsl_matrix * b)

This function subtracts the elements of matrix b from the elements of matrix a. The result a(i,j) \leftarrow a(i,j) - b(i,j) is stored in a and b remains unchanged. The two matrices must have the same dimensions.

Function: int gsl_matrix_mul_elements (gsl_matrix * a, const gsl_matrix * b)

This function multiplies the elements of matrix a by the elements of matrix b. The result a(i,j) \leftarrow a(i,j) * b(i,j) is stored in a and b remains unchanged. The two matrices must have the same dimensions.

Function: int gsl_matrix._div_elements (gsl_matrix * a, const gsl_matrix * b)

This function divides the elements of matrix a by the elements of matrix b. The result a(i,j) \leftarrow a(i,j) / b(i,j) is stored in a and b remains unchanged. The two matrices must have the same dimensions.

Function: int gsl_matrix_scale (gsl_matrix * a, const double x)

This function multiplies the elements of matrix a by the constant factor x. The result a(i,j) \leftarrow x a(i,j) is stored in a.

Function: int gsl_matrix_add_constant (gsl_matrix * a, const double x)

This function adds the constant value x to the elements of the matrix a. The result a(i,j) \leftarrow a(i,j) + x is stored in a.

I can't find more detailed information about how to use a general formula to multiply a NxM matrix by a MxK matrix, and I'm completely missing informations about determinants, adjugates, inverse, and rotation.

So I think I'll have to write it on my own, and for the first step I'll need to know how to make this sort of thing:

Code: Select all

void MatrixMatrixMult(float A[][], float B[][], float &C[][], int N, int M, int K)

all matrices must be able to be passed at any size, so the function must work for multiplying
2x3 by 3x5 (returns a 2x5 matrix)
as well as for 2x2 by 2x2 (returns a 2x2 matrix)
or 2x3 by 3x2 (returns also a 2x2 matrix).

The function call should be like I did it in the former task main():

Code: Select all

task main() {
    float A[2][2], B[2][2], C[2][2];

    A[0][0]=1;   A[0][1]=3;
    A[1][0]=2;   A[1][1]=4;

    B[0][0]=10;  B[0][1]=30;
    B[1][0]=20;  B[1][1]=40;

    MatrixMatrixMult(A,B,C, 2,2,2);  // C[2][2] will be the result matrix

[gloomyandy]

Doc the gsl library has support for BLAS (which has more stuff than any sane person would ever want):
http://www.gnu.org/software/gsl/manual/ ... AS-Support

However this may be over the top for what you need.

The definition of gsl_matrix can be found here:
http://www.gnu.org/software/gsl/manual/ ... l#Matrices

As to writing routines that handle arbitrarily sized 2D arrays then things are not so simple. You will need to understand how C lays things out in memory (or you will need to use some structure other than a simple 2D array to hold your matrix). The problem is that due to the memory layout used, the compiler can not (easily) generate code to help you access your 2D matrix, as that same code needs to be used to access arrays of different sizes. Unlike some other programming languages when you declare int a[10][5]; all that you get is a lump of memory that is 50 integers in size there is no additional information stored with it that describes the layout, in effect it is identical to int b[5][10]; However the code needed to access a[1][1] is different to b[1][1] (due to the actual layout used). This lack of information is why C unlike many other languages will not give you an error if you attempt to access an array element past the end of the array (though your program may crash). It may seem to you that this does not make sense because if you write a trivial program like:

Code: Select all

main()
{
  int a[10][5];
  int b[5][10];

  a[1][1] = 27;
  b[1][1] = 42;
}

then all seems well. But this is simply because in this case the compiler has information from the declarations about the size and shape of the array available to it and so can generate the code needed. in the example above with 4 byte integers then a[1][1] will actually access the following byte address
<base of a> + 5*4*1 + 4*1
while b[1][1] will access the following byte address:
<base of b> + 10*4*1 + 4*1
However when you pass an array to a function none of this information is available to the compiler when it compiles the function (that is designed to handle arrays of different sizes, there is a mechanism that works for arrays of a fixed size) and as I've already explained there is no run time information attached to the array to make it possible to "do the right thing" at run time. All of this is explained much better than I can do it here:
http://pw1.netcom.com/~tjensen/ptr/pointers.htm


Good luck and welcome to the world of "standard C"

[HaWe]

yes, thanks Andy.
The function should be able to handle all kinds of matrices,
2x2
2x3
3x3
...
10x10
of float


At runtime I usually know what sizes they have, but sometimes the function will be called by larger matrices by one of the threads and sometimes by smaller sized matrices by other threads.
Generally it's about the matrix sizes like about string functions and sizes - usually you don't know at any time in advance how large a string might become.
So the matrix function must be of a geneneral typ, just like string handling functions.

if I try I get the following errors:

Code: Select all

void MatrixMatrixMult(float A[][], float B[][], float &C[][], int N, int M, int K){

btest.c:69: error: array type has incomplete element type

Instead,

Code: Select all

void MatrixMatrixMult(float **A, float **B, float **C, int N, int M, int K){

now compiles without error - **C has to be created by malloc,
I will try to find out how the function call by my example with static arrays will have to look like and how I get that **C back to main().
(actually I can't imagine that one will be able to do things by NXC what's impossible to do by ANSI C...)

[gloomyandy]

Doc,
you almost certainly do not want int **A if you intend to pass something created by int a[10][10] (or whatever) to it, a 2D array in C is not structured as an array of pointers to single dimensioned arrays (which is what is implied by int **A). It is simply a flat chunk of memory. Now obviously you can create such a thing using malloc, but that is not what you get with int a[10][10]. Take a look at:
http://c-faq.com/aryptr/pass2dary.html
For an explanation.

Yes you can do something similar to what NXC does but you will have to do some of the work yourself. Standard C is a pretty low level programming language and does not have many of these higher level features. If you take a look at the reference I gave to the definition of gsl_matrix, you will get an idea for the sort of thing you may need to do to implement the sort of arrays used by NXC.

[HaWe]

the gsl_matrix structure is too complex for my requirements,

Code: Select all

typedef struct
{
  size_t size1;
  size_t size2;
  size_t tda;
  double * data;
  gsl_block * block;
  int owner;
} gsl_matrix;

the NXC syntax I've been using so far did exactly what I wanted, and the arrays are just as simple as it needs to be, so I would like just to exchange some terms in the syntax by other ones.
In case I'd have to alloc some memory - that wouldn't be the hardest thing.
how would you do it not-exactly-NXC-like which matchs my intentions?
the explanation in the link is ...well...actually...many words...and no solution..

[gloomyandy]

Doc,
NXC and the Lego firmware do a lot of things for you behind the scenes. One of the downsides of using standard C is that some of these things are not as simple and you need to understand a little more about what is actually going on. Did you read the tutorial on pointers and arrays:
http://pw1.netcom.com/~tjensen/ptr/pointers.htm

If you did then you should have pretty much all you need to be able to write code that manipulates arrays using pointers (which is what you will need to do if you want to use 2D arrays of different sizes). There is no simple syntax change which will magically make all of this work like it does in NXC. The following is the best example I can find of the sort of thing you will need to do...
http://www.mymathlib.com/c_source/matri ... matrices.c
This is taken from:
http://www.mymathlib.com/

[HaWe]

OMG, I couldn't imagine that in view of the fact that C is existing already almost 30 years (?) it doesn't still exist a simple library which is able to handle passing multi-dim arrays to functions in a simple way.
Surely this is nothing what comes falling at the end of one's tether from the sky (or heaven) - but meanwhile I had expected that some smart preogrammers had made there thoughts about this issue - it's finally not the question about life, the universe, and everything.

So ok, if it doesn't exist already a SIMPLE library for this actually SIMPLE task - i simply have to resign, unfortunately :(