N-dimensional mathematical functions

[jacek.strzelczyk]

Hello,

I'm looking for a C library that provides the notation of n-
dimensional mathematical functions. Or is there any other way to
decode that kind of functions in C language?

Thanks in advance,
Jacek

 

[user923005]

Hello,

I'm looking for a C library that provides the notation of n-
dimensional mathematical functions. Or is there any other way to
decode that kind of functions in C language?

In C, we just code a vector as an array.
Sample C vector code for differential equations is found here for
cvode.tar.gz:
http://www.netlib.org/ode/

 

[jacek.strzelczyk]

In C, we just code a vector as an array.
Sample C vector code for differential equations is found here for
cvode.tar.gz:http://www.netlib.org/ode/

But vector is not enough to note all kinds of functions. For example
f(x)=1/x is not in polynomial form, so you can't describe it by simple
vector. Is there any other, more sophisticated way?

 

[Chris Dollin]

But vector is not enough to note all kinds of functions. For example
f(x)=1/x is not in polynomial form,

-1 is a perfectly good exponent. I presume I'm missing something.

 

[Ben Bacarisse]

But vector is not enough to note all kinds of functions. For example
f(x)=1/x is not in polynomial form, so you can't describe it by simple
vector. Is there any other, more sophisticated way?

comp.programming may be better. I, for one, was not replying simply
because all the questions I had about what you need are not C
questions. Anyway, to get further it would be better to know an
example of the kind of thing you need the library to do, together with
some idea of the range ("I need to work for all piece-wise continuous
functions of n variables"). The example makes it concrete, the range
says what can and can not be ignored. "Decode" and "n-dimensional"
are very broad (and to me, at least, the dimension of a function is a
very specific thing that crops up only in fractal geometry).

 

[jacek.strzelczyk]

comp.programming may be better. I, for one, was not replying simply
because all the questions I had about what you need are not C
questions. Anyway, to get further it would be better to know an
example of the kind of thing you need the library to do, together with
some idea of the range ("I need to work for all piece-wise continuous
functions of n variables"). The example makes it concrete, the range
says what can and can not be ignored. "Decode" and "n-dimensional"
are very broad (and to me, at least, the dimension of a function is a
very specific thing that crops up only in fractal geometry).

Ok, you're right. So example:
I want to create a library function that will use Monte Carlo methods
to find a minimum of given mathematical function. The application
programmer that wants to use this library feature need to pass given
mathematical function to the library in some way. For example, the
function can be:
f(x1,x2) = 2*pi^2 / 3*(x1+x2)^3 + x1*x2
So, to find its minimum the programmer has to call library function
'minimum' and pass the f(x1,x2) function.
My question is: how can that kind of function be decoded in C
language? In my opinion using just an array is not enough.
I simply need to calculate function value for some random arguments in
program.

 

[Eric Sosman]

Ok, you're right. So example:
I want to create a library function that will use Monte Carlo methods
to find a minimum of given mathematical function. The application
programmer that wants to use this library feature need to pass given
mathematical function to the library in some way. For example, the
function can be:
f(x1,x2) = 2*pi^2 / 3*(x1+x2)^3 + x1*x2
So, to find its minimum the programmer has to call library function
'minimum' and pass the f(x1,x2) function.
My question is: how can that kind of function be decoded in C
language? In my opinion using just an array is not enough.
I simply need to calculate function value for some random arguments in
program.

The magic phrase is "function pointer."

double func(double x1, double x2)
{
return 19.739208802178717237668981999752
/ (3 * (x1+x2)*(x1+x2)*(x1+x2))
+ x1 * x2;
}

result_type minimize(various_params,
double (*fptr)(double,double),
more_params)
{
...
z = fptr(x, y);
...
}

...
result = minimize(params, func, other_params);

 

[jacek.strzelczyk]

The magic phrase is "function pointer."

double func(double x1, double x2)
{
return 19.739208802178717237668981999752
/ (3 * (x1+x2)*(x1+x2)*(x1+x2))
+ x1 * x2;
}

result_type minimize(various_params,
double (*fptr)(double,double),
more_params)
{
...
z = fptr(x, y);
...
}

...
result = minimize(params, func, other_params);

Ok, this is some solution. But in this case, the function has to be
directly programmed by programmer. What if user would type the
function and then the input would be parsed by some parser. How can
the function can be coded then?

 

[Keith Thompson]

The above was written by Eric Sosman. Google Groups automaticalloy
inserts an attribution line for quoted material, a line of the form
"So-and-so writes:". Please don't delete that line; it makes it
easier to follow the discussion.

Ok, this is some solution. But in this case, the function has to be
directly programmed by programmer. What if user would type the
function and then the input would be parsed by some parser. How can
the function can be coded then?

The only pure C solution I can think of is to write your own
expression parser that produces a (mostly binary) tree representing
the mathematical function. You can then have a C function, perhaps
called "evaluate", that takes a pointer to the root of the tree and
the values of x1 and x2, and returns the result of evaluating the
mathematical function with those arguments.

It's going to be substantially slower than using a C function
directly; this may or may not matter. It's also going to be
substantially mor work; you'd essentially be doing part of what the
compiler normally does.

Consider that some other languages provide features that could make
this easier. For example, Perl's built-in "eval" function can
directly execute a chunk of Perl code passed as a string. The various
Lisp-like languages provide similar facilities.

Or you could take a C representation of the mathematical function as
input and automatically generate a C source file that you then compile
and execute.

 

[Eric Sosman]

Ok, this is some solution. But in this case, the function has to be
directly programmed by programmer. What if user would type the
function and then the input would be parsed by some parser. How can
the function can be coded then?

Parse the user's input, "compile" it into an interpreted
"instruction set" of your own devising, and run your own
interpreter on it each time you need a new value. There's
nothing particularly C-specific about this stuff.

 

[jacek.strzelczyk]

Parse the user's input, "compile" it into an interpreted
"instruction set" of your own devising, and run your own
interpreter on it each time you need a new value. There's
nothing particularly C-specific about this stuff.

Eric, your second solution seems to be quite complicated. It's not my
aim to create my own interpreter. I was thinking about some easy way.
But I think there is no other option despite your first advice -
function pointer.
Keith, I think this is what you've been also saying - that using C
function directly would be the best solution.
Ok, but maybe there is already a parser and interpreter in C to
evaluate multi dimensional mathematical functions? You've mentioned
that I could create it by myself, but isn't there something like this
already?

 

[Ben Bacarisse]

Please don't quote sigs (the -- bit).

Eric, your second solution seems to be quite complicated.

There is a middle way where you don't have to parse the input (if you
don't want to). You use postfix notation and encode that in an array
and interpret it with a little stack machine.

Using $1, $2 for the parameters, your example is:

19.73920 $1 $2 + $1 $2 + $1 $2 + * * 3 * / $1 $2 *

(simpler if you allow a "dup" operation). In C you could have

enum instruction_type {
Number,
Parameter,
Operation
};

enum operation {
Add,
Multiply,
Divide,
/* and do on ... */
};

struct instruction {
enum instruction_type type;
union instruction_data {
double number;
int parameter;
enum operation operation;
} data;
};

It is not too hard to read input and store it in an array of these
instructions and the execution is simple enough. Of course, it may
not be fast enough for some numerical work.

 

[dj3vande]

Keith, I think this is what you've been also saying - that using C
function directly would be the best solution.

You would still have to write code to compile it to a temporary
executable and run that executable. This may or may not be easier than
writing a parser yourself, and in any case it will tie your program
down to a particular system, while an expression parser and interpreter
can be done portably.

Ok, but maybe there is already a parser and interpreter in C to
evaluate multi dimensional mathematical functions? You've mentioned
that I could create it by myself, but isn't there something like this
already?

There isn't (that I know of) a pre-packaged one.
If you don't mind forcing the user to enter the function in something
other than standard mathematical notation, section 4.3 of K&R2
describes a fairly simple RPN calculator; adapting this to your needs
would probably be a worthwhile exercise and would have as its end
result something you can use.
If you need standard mathematical notation and don't mind picking up
new tools, there are code generators like yacc that will do most of the
hard work of generating the parser for you. (You give the code
generator a description of what your input looks like and the code you
want it to run when it parses each sub-expression, and it will generate
C code to parse the input and run your code at appropriate times.)
comp.programming or comp.unix.programmer (or maybe comp.compilers)
would be good places to ask about that.


dave

 

[Eric Sosman]

[...]
Parse the user's input, "compile" it into an interpreted
"instruction set" of your own devising, and run your own
interpreter on it each time you need a new value. There's
nothing particularly C-specific about this stuff.

Eric, your second solution seems to be quite complicated.

Not very. I've written such a thing in Java and it runs
to only 1036 lines, of which 304 are comments. Java isn't C,
but I imagine a C version would be of similar size.

Ok, but maybe there is already a parser and interpreter in C to
evaluate multi dimensional mathematical functions? You've mentioned
that I could create it by myself, but isn't there something like this
already?

There's no such thing built into the C language or library.
If you search for a term like "expression evaluator" you might
find that somebody else has written something that you could use.
(By the way, I still don't understand why you seem so fixated on
the "multi dimensional" aspect; the same issues arise for user-
entered expressions in one variable, or even in no variables!)

 

[user923005]

Ok, this is some solution. But in this case, the function has to be
directly programmed by programmer. What if user would type the
function and then the input would be parsed by some parser. How can
the function can be coded then?

I see two potential solutions:
1. You can pass the dimention of a vector and then the vector. This
is easy to program but possibly less convenient for the tool user.
2. You can make the function varadic. From the C-FAQ:

15.4: How can I write a function that takes a variable number of
arguments?

A: Use the facilities of the <stdarg.h> header.

Here is a function which concatenates an arbitrary number of
strings into malloc'ed memory:

#include <stdlib.h> /* for malloc, NULL, size_t */
#include <stdarg.h> /* for va_ stuff */
#include <string.h> /* for strcat et al. */

char *vstrcat(const char *first, ...)
{
size_t len;
char *retbuf;
va_list argp;
char *p;

if(first == NULL)
return NULL;

len = strlen(first);

va_start(argp, first);

while((p = va_arg(argp, char *)) != NULL)
len += strlen(p);

va_end(argp);

retbuf = malloc(len + 1); /* +1 for trailing \0 */

if(retbuf == NULL)
return NULL; /* error */

(void)strcpy(retbuf, first);

va_start(argp, first); /* restart; 2nd scan */

while((p = va_arg(argp, char *)) != NULL)
(void)strcat(retbuf, p);

va_end(argp);

return retbuf;
}

Usage is something like

char *str = vstrcat("Hello, ", "world!", (char *)NULL);

Note the cast on the last argument; see questions 5.2 and 15.3.
(Also note that the caller must free the returned, malloc'ed
storage.)

References: K&R2 Sec. 7.3 p. 155, Sec. B7 p. 254; ISO Sec. 7.8;
Rationale Sec. 4.8; H&S Sec. 11.4 pp. 296-9; CT&P Sec. A.3 pp.
139-141; PCS Sec. 11 pp. 184-5, Sec. 13 p. 242.

 

[jacek.strzelczyk]

Thanks for the comments. I'll read them through tomorrow, because
today it's already too late for me to understand everything and write
something clever. Then I'll probably have more questions.

 

[jacek.strzelczyk]

Ben, dj3va: Thanks for ideas. I have no question, so I'll try to read
more and implement your solutions.

Eric:
Ok, maybe it's not so complicated, but if there already is something
like that, why create it one more time? And yes, I think you've
called it properly - "expression evaluator', I'll try to look for it.
I'm not fixated on the "multi dimensional" aspect, that's just my
perspective of this problem.

user923005:
Hmmm... right, I'll take that into consideration. Thanks.

 

[Keith Thompson]

Eric:
Ok, maybe it's not so complicated, but if there already is something
like that, why create it one more time? And yes, I think you've
called it properly - "expression evaluator', I'll try to look for it.
I'm not fixated on the "multi dimensional" aspect, that's just my
perspective of this problem.

[...]

I'm still not 100% clear on what you mean by "multi dimensional". Are
you merely referring to functions that take multiple arguments, or is
there more to it?

 

[user923005]

(e-mail address removed) writes:

[...]> Eric:

   Ok, maybe it's not so complicated, but if there already is something
like that, why create it one more time? And yes, I think you've
called it properly - "expression evaluator', I'll try to look for it.
   I'm not fixated on the "multi dimensional" aspect, that's just my
perspective of this problem.

[...]

I'm still not 100% clear on what you mean by "multi dimensional".  Are
you merely referring to functions that take multiple arguments, or is
there more to it?

From his description, I think that he does not know how many
parameters will be passed from the end-user.
That is why I suggested either using arrays or a varadic function.

 

[jacek.strzelczyk]

(e-mail address removed) writes:

[...]> Eric:

Ok, maybe it's not so complicated, but if there already is something
like that, why create it one more time? And yes, I think you've
called it properly - "expression evaluator', I'll try to look for it.
I'm not fixated on the "multi dimensional" aspect, that's just my
perspective of this problem.

[...]

I'm still not 100% clear on what you mean by "multi dimensional". Are
you merely referring to functions that take multiple arguments, or is
there more to it?

From his description, I think that he does not know how many
parameters will be passed from the end-user.
That is why I suggested either using arrays or a varadic function.

Aaa... We are mixing the ideas! I do not mean a _programming_
function, but _mathematical_ ! Like f(x)=x+1. This one, for example is
one-dimensional (one argument - x). f(x1, x2) = x1*x2^3 + 2 is a two-
dimensional, etc.