I know this is off-topic here, but posters here have good general programming knowledge and may be able to help. I have some long expressions, generated by computer algebra software, in which many terms contain powers, expressed as x^2, c^4 etc. I need to use these expressions in a C program. If I tried to do the conversion manually it would take an age and I'd be bound to make mistakes. To give an idea of the scale of this task, the equations are in three text files, each about 700 Kb, with about 5000 lines of about 130 characters. (I didn't create these, it was done for me by one Robert Lewis using his Fermat program).
I wonder if there exists a program for converting this kind of standard maths format into C code. As an illustration, here are the first two of 130 lines of the expression for 'a':
> I know this is off-topic here, but posters here have good general
> programming knowledge and may be able to help. I have some long
> expressions, generated by computer algebra software, in which many terms
> contain powers, expressed as x^2, c^4 etc. I need to use these
> expressions in a C program. If I tried to do the conversion manually it
> would take an age and I'd be bound to make mistakes. To give an idea of
> the scale of this task, the equations are in three text files, each
> about 700 Kb, with about 5000 lines of about 130 characters. (I didn't
> create these, it was done for me by one Robert Lewis using his Fermat
> program).
> I wonder if there exists a program for converting this kind of standard
> maths format into C code. As an illustration, here are the first two of
> 130 lines of the expression for 'a':
Hah! This didn't explain well, because the mail reader (Mozilla Thunderbird, anyway) translates the powers, replacing '^ 2' by superscripted 2. In case it still isn't clear, I have thousands of '^' to deal with.
>I know this is off-topic here, but posters here have good general >programming knowledge and may be able to help. I have some long >expressions, generated by computer algebra software, in which many terms >contain powers, expressed as x^2, c^4 etc. I need to use these expressions >in a C program. If I tried to do the conversion manually it would take an >age and I'd be bound to make mistakes. To give an idea of the scale of >this task, the equations are in three text files, each about 700 Kb, with >about 5000 lines of about 130 characters. (I didn't create these, it was >done for me by one Robert Lewis using his Fermat program).
> I wonder if there exists a program for converting this kind of standard > maths format into C code. As an illustration, here are the first two of > 130 lines of the expression for 'a':
> You might have to adjust the regular expression further if the input can be
> more complicated (like ^ of ^, or ^ split over multiple lines).
> If you're on Windows, you can get sed as part of Cygwin. Many text editors
> (e.g. textpad) also provide regular expression support.
> Regards
> Rafik
That's perfect! One question: executing that sed command works fine, but when I put the script into a text file and call it power.txt, this fails:
>sed -e power.txt input.txt
sed: -e expression #1, char 2: Extra characters after command
If I remove the quotes it fails with the same error message. This indeed on Windows, using sed from the UnixUtils collection of utilities. How should I put the command in a script file?
>You might have to adjust the regular expression further if the input can be >more complicated (like ^ of ^, or ^ split over multiple lines).
>If you're on Windows, you can get sed as part of Cygwin. Many text editors >(e.g. textpad) also provide regular expression support.
It's amazing what you can do with sed.
If there are nested expressions, that regular expression might not
balance parentheses. It's probably better to assume there aren't --
the example given looks like a kind of canonical form with no
parentheses -- and try something slightly simpler (and then check for
leftover carets).
Or the OP could replace the caret by '**' and convert the expressions
to Fortran, keeping in mind that if an expression contains something
like 'a^b^c', commutativity might be an issue.
>"Gib Bogle" <g.bo...@auckland.ac.nz> wrote in message >news:j9pu3i$nq3$1@speranza.aioe.org...
>>I know this is off-topic here, but posters here have good general >>programming knowledge and may be able to help. I have some long >>expressions, generated by computer algebra software, in which many terms >>contain powers, expressed as x^2, c^4 etc. I need to use these expressions >>in a C program. If I tried to do the conversion manually it would take an >>age and I'd be bound to make mistakes. To give an idea of the scale of >>this task, the equations are in three text files, each about 700 Kb, with >>about 5000 lines of about 130 characters. (I didn't create these, it was >>done for me by one Robert Lewis using his Fermat program).
>> I wonder if there exists a program for converting this kind of standard >> maths format into C code. As an illustration, here are the first two of >> 130 lines of the expression for 'a':
> If there are nested expressions, that regular expression might not
> balance parentheses. It's probably better to assume there aren't --
> the example given looks like a kind of canonical form with no
> parentheses -- and try something slightly simpler (and then check for
> leftover carets).
> Or the OP could replace the caret by '**' and convert the expressions
> to Fortran, keeping in mind that if an expression contains something
> like 'a^b^c', commutativity might be an issue.
As it turns out the format is very simple, and this works a treat. The problem now is going to be compiling it for the target host, which is an embedded processor system (on a tiny board that fits in your hand, which comes with a C compiler). I've tested one of the three files. It compiles with MSVC (after a bit of a wait on a fast Win 7 box), producing a 4.5 Mb object file. gcc however just crashes silently. I fear that the size of the executable might be an issue for the tiny computer.
The situation is quite amusing. It would take too long to go into the details, but what I have here is the analytical solution to 7 nonlinear equations. I thought it would be nice and fast to have a closed form solver, although I've already implemented an approach (in Fortran) using Newton-Raphson. The ifort executable for this is 650 Kb. Surprisingly the numerical approach yields code that is about an order of magnitude smaller than the analytical approach yields. The reason, of course, is that the (canonical?) code that the computer algebra program spits out is extremely verbose.
> As it turns out the format is very simple, and this works a treat. The > problem now is going to be compiling it for the target host, which is an > embedded processor system (on a tiny board that fits in your hand, which > comes with a C compiler). I've tested one of the three files. It > compiles with MSVC (after a bit of a wait on a fast Win 7 box), > producing a 4.5 Mb object file. gcc however just crashes silently. I > fear that the size of the executable might be an issue for the tiny > computer.
It might be smaller to compile to an intermediate form and then
interpret that. If you encode just the needed operations and
operands, it should take just a few bits each.
Louis Krupp <lkr...@nospam.indra.com.invalid> wrote:
> On Sun, 13 Nov 2011 21:51:38 -0500, "Rafik Zurob" <nos...@hotmail.com>
> wrote:
>>You can use a regular expression to convert. For example, I used the >>following sed command:
>>sed "s#\([a-zA-Z_(][a-zA-Z_() ,0-9]*\)\^\([0-9][0-9]*\)# pow(\1, \2) #g" >>input.txt
(snip)
> It's amazing what you can do with sed.
> If there are nested expressions, that regular expression might not
> balance parentheses. It's probably better to assume there aren't --
> the example given looks like a kind of canonical form with no
> parentheses -- and try something slightly simpler (and then check for
> leftover carets).
I think you can write separate sed commands for different levels
of nested parentheses.
Otherwise, it shouldn't be so hard to do with flex and bison,
to write a real parser for it.
On Mon, 14 Nov 2011 17:44:28 +1300, Gib Bogle wrote:
> On 14/11/2011 4:49 p.m., Louis Krupp wrote:
>> Or the OP could replace the caret by '**' and convert the expressions
>> to Fortran, keeping in mind that if an expression contains something
>> like 'a^b^c', commutativity might be an issue.
> As it turns out the format is very simple, and this works a treat. The
> problem now is going to be compiling it for the target host, which is an
> embedded processor system (on a tiny board that fits in your hand, which
> comes with a C compiler). I've tested one of the three files.
The real problem (once you can get it to compile) is the inefficiency in
calling pow(). It would be much better to change the ^ to **, and compile
this with a Fortran compiler. If you can't use Fortran and must use
C, then convert x^2 to x*x etc.
Do you have with numerical round-off issues? With an
expression like
Steven G. Kargl <s...@removetroutmask.apl.washington.edu> wrote:
(snip of converting complicated expressions to use pow())
> The real problem (once you can get it to compile) is the inefficiency in
> calling pow(). It would be much better to change the ^ to **, and compile
> this with a Fortran compiler. If you can't use Fortran and must use
> C, then convert x^2 to x*x etc.
Personally, I would like to see a separate function, such as ipow(),
for integer powers. However, there is no requirement that the
implementation actually use a function call, and it can optimize
the case of integer powers, especially integer constants.
As a quick test with gcc:
#include <stdio.h>
#include <math.h>
int main() {
double x,y;
while(scanf("%lf",&x)>0) printf("%f\n",pow(x,2));
}
gcc does figure it out and generate a multiply instruction
without any function call.
I didn't check what it does with in integer variable.
> Do you have with numerical round-off issues? With an expression like
> a := 4*bx^2*cy^2*dz^2 - 8*ax*bx*cy^2*dz^2 + 4*ax^2*cy^2*dz^2
> - 4*c2^2*cy^2*dz^2 - 8*bx*by*cx*cy*dz^2 + 8*ax*by*cx*cy*dz^2
> + 8*ay*bx*cx*cy*dz^2 - 8*ax*ay*cx*cy*dz^2 + 8*ax*bx*by*cy*dz^2
> - 8*ax^2*by*cy*dz^2 + 8*c2^2*by*cy*dz^2 - 8*c1*c2*by*cy*dz^2
> - 8*ay*bx^2*cy*dz^2
> subtracting nearly equal large numbers typically yields erroneous > rsults.
That certainly could cause problems. Factoring, if it could be
factored, might help.
glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> Steven G. Kargl <s...@removetroutmask.apl.washington.edu> wrote:
> (snip of converting complicated expressions to use pow())
>> The real problem (once you can get it to compile) is the >> inefficiency in calling pow().
(snip, then I wrote)
> Personally, I would like to see a separate function, such as ipow(),
> for integer powers. However, there is no requirement that the
> implementation actually use a function call, and it can optimize
> the case of integer powers, especially integer constants.
> As a quick test with gcc:
(snip)
Further tests show that for anything other than a constant 2,
even a constant 3, gcc calls the actual pow() function.
I suppose the case of a constant 2 is the largest fraction,
but it wouldn't be hard to special case other constants, or
even integer variables (which are converted according to
the prototype in scope, but the compiler still knows that
they are integer at compile time).
> On Mon, 14 Nov 2011 17:44:28 +1300, Gib Bogle wrote:
>> On 14/11/2011 4:49 p.m., Louis Krupp wrote:
>>> Or the OP could replace the caret by '**' and convert the expressions
>>> to Fortran, keeping in mind that if an expression contains something
>>> like 'a^b^c', commutativity might be an issue.
>> As it turns out the format is very simple, and this works a treat. The
>> problem now is going to be compiling it for the target host, which is an
>> embedded processor system (on a tiny board that fits in your hand, which
>> comes with a C compiler). I've tested one of the three files.
> The real problem (once you can get it to compile) is the inefficiency in
> calling pow(). It would be much better to change the ^ to **, and compile
> this with a Fortran compiler. If you can't use Fortran and must use
> C, then convert x^2 to x*x etc.
> Do you have with numerical round-off issues? With an
> expression like
> subtracting nearly equal large numbers typically yields erroneous
> rsults.
It's highly likely that Fortran will not be available on the tiny computer.
Maybe some kind soul will show me the sed script that turns x^2 into x*x, y^3 into y*y*y, and z^4 into z*z*z*z. I've never worked with regular expressions, and I have a feeling that my brain is too ossified to start now.
Another option is to replace pow() by ipow(), then in the function use *. Would that make a difference?
The easiest way to help the compiler swallow this big mouthful would be to cut each expression (actually just the three big ones - 700, 1400 and 3100 lines) up into many pieces. I presume it's the length of the expressions that is creating the problem. It wouldn't be much effort to create pieces no more than 100 lines long.
As far as roundoff is concerned, at this stage I don't have a clue about this. I suspect it will not be an issue.
If all else fails, the fall-back is to pass the info to another computer via a serial link, use a Fortran program to get the solution (either analytical or Newton-Raphson, which works well), then pass it back. The hitch here is that the computation has to be done within a 10 ms time-slice, together with various other things, and therefore we'd prefer to keep communications to a minimum.
On Mon, 14 Nov 2011 21:47:14 +1300, Gib Bogle <g.bo...@auckland.ac.nz>
wrote:
<snip>
>Maybe some kind soul will show me the sed script that turns x^2 into >x*x, y^3 into y*y*y, and z^4 into z*z*z*z. I've never worked with >regular expressions, and I have a feeling that my brain is too ossified >to start now.
etc., for as many powers as you need, and call it good.
If you're not going to balance parentheses, I would keep it simple and
leave them out entirely. I would search the file for carets after
running sed, and if you find any, then you know you have something
else to deal with.
Expanding on Glen's suggestion of an intermediate form, you might be
able to put your variables (c1, c2, ax, bx, cx, ay, cy, dy, etc) in an
array and have a parallel arrary with exponents. I.e., if
v[1] = c1
v[2] = c2
v[3] = ax
v[4] = bx
and you want to evaluate 3*c2*ax^2, then set
e[0] = 3
e[2] = 1
e[3] = 2
and all other members of e[] to 0.
To evaluate things like c1* bx^3 - 3*c3^ax, you could have a
two-dimensional array and add a level of nesting.
> On Mon, 14 Nov 2011 21:47:14 +1300, Gib Bogle<g.bo...@auckland.ac.nz>
> wrote:
> <snip>
>> Maybe some kind soul will show me the sed script that turns x^2 into
>> x*x, y^3 into y*y*y, and z^4 into z*z*z*z. I've never worked with
>> regular expressions, and I have a feeling that my brain is too ossified
>> to start now.
> <snip>
> etc., for as many powers as you need, and call it good.
Thanks Louis. I've just realized there is another rather simple option that will speed things up a bit. I could just globally replace ^ with _, then at the start of the function define all the powers like this:
In article <j9qrl2$e...@speranza.aioe.org>,
Gib Bogle <g.bo...@auckland.ac.nz> wrote:
> Thanks Louis. I've just realized there is another rather simple option > that will speed things up a bit. I could just globally replace ^ with > _, then at the start of the function define all the powers like this:
and so on. Also, you might try to run your expression through a symbolic algebra program to look for common subexpressions and other such simplifications. This may both shorten the code and make the execution faster.
> I know this is off-topic here, but posters here have good general
> programming knowledge and may be able to help. I have some long
> expressions, generated by computer algebra software, in which many terms
> contain powers, expressed as x^2, c^4 etc. I need to use these
> expressions in a C program. If I tried to do the conversion manually it
> would take an age and I'd be bound to make mistakes. To give an idea of
> the scale of this task, the equations are in three text files, each
> about 700 Kb, with about 5000 lines of about 130 characters. (I didn't
> create these, it was done for me by one Robert Lewis using his Fermat
> program).
> I wonder if there exists a program for converting this kind of standard
> maths format into C code. As an illustration, here are the first two of
> 130 lines of the expression for 'a':
> On 11/13/2011 8:23 PM, Gib Bogle wrote:
>> I know this is off-topic here, but posters here have good general
>> programming knowledge and may be able to help. I have some long
>> expressions, generated by computer algebra software, in which many terms
>> contain powers, expressed as x^2, c^4 etc. I need to use these
>> expressions in a C program. If I tried to do the conversion manually it
>> would take an age and I'd be bound to make mistakes. To give an idea of
>> the scale of this task, the equations are in three text files, each
>> about 700 Kb, with about 5000 lines of about 130 characters. (I didn't
>> create these, it was done for me by one Robert Lewis using his Fermat
>> program).
>> I wonder if there exists a program for converting this kind of standard
>> maths format into C code. As an illustration, here are the first two of
>> 130 lines of the expression for 'a':
These associations are permitted by Fortran (although not by C, why is C being discussed here?) and many compilers will go part way. As a consequence, each compiler may produce slightly different numerical results; those variations may be reduced by writing the associations into the source.
This thread is in C.L.F. not because of Fortran association; the original post said, "posters here have good general programming knowledge and may be able to help" and "I need to use these expressions in a C program."
> In article<j9qrl2$e...@speranza.aioe.org>,
> Gib Bogle<g.bo...@auckland.ac.nz> wrote:
>> Thanks Louis. I've just realized there is another rather simple option
>> that will speed things up a bit. I could just globally replace ^ with
>> _, then at the start of the function define all the powers like this:
> and so on. Also, you might try to run your expression through a
> symbolic algebra program to look for common subexpressions and other
> such simplifications. This may both shorten the code and make the
> execution faster.
> $.02 -Ron Shepard
The idea of simplifying the expression systematically had occurred to me (as to mecej4 as well). I don't have ready access to Maple (but possibly could locate someone who has it). Do you know of any free program with the required capability?
> I know this is off-topic here, but posters here have good general
> programming knowledge and may be able to help. I have some long
> expressions, generated by computer algebra software, in which many terms
> contain powers, expressed as x^2, c^4 etc. I need to use these
> expressions in a C program. If I tried to do the conversion manually it
> would take an age and I'd be bound to make mistakes. To give an idea of
> the scale of this task, the equations are in three text files, each
> about 700 Kb, with about 5000 lines of about 130 characters. (I didn't
> create these, it was done for me by one Robert Lewis using his Fermat
> program).
> I wonder if there exists a program for converting this kind of standard
> maths format into C code. As an illustration, here are the first two of
> 130 lines of the expression for 'a':
I haven't seen such a program, but that might be because I haven't
been looking for one.
If you decide to write such a program yourself, some suggestions
for these lines:
1. Replace the ":=" with "=".
2. Add a semicolon at the end of the last line.
3. For each of the groups after the "=" with no spaces included,
add parentheses around that group. For example, "4*bx^2*cy^2*dz^2"
becomes "(4*bx^2*cy^2*dz^2)".
4. For each of the powers, create a new variable for that power of
that variable. For example,
x2 = x * x;
y2 = y * y;
z2 = z * z;
Or, if you prefer, the equivalent using pow().
Depending on your C compiler's level of optimization, this may
speed up the code by avoiding calculating those powers over and
over.
5. Wherever two variables are adjacent, insert a "*" between
them. For example, "bx^2" becomes " b*x^2".
6. Using some text editing program, replace such powers with the
corresponding new variable; or just have your program do that.
For example, replace "x^2" with "x2", "y^2" with "y2", and "z^2"
with "z2".
7. Note that I haven't mentioned writing the first few lines,
including declarations of all the variables, or the last few.
Those should be short enough to do them by hand.
If that's not adequate, show us more about what fails.
Is there any particular reason for not converting it into
Fortran instead?
> On 15/11/2011 1:55 a.m., Ron Shepard wrote:
>> In article<j9qrl2$e...@speranza.aioe.org>,
>> Gib Bogle<g.bo...@auckland.ac.nz> wrote:
>>> Thanks Louis. I've just realized there is another rather simple option
>>> that will speed things up a bit. I could just globally replace ^ with
>>> _, then at the start of the function define all the powers like this:
>> and so on. Also, you might try to run your expression through a
>> symbolic algebra program to look for common subexpressions and other
>> such simplifications. This may both shorten the code and make the
>> execution faster.
>> $.02 -Ron Shepard
> The idea of simplifying the expression systematically had occurred to me
> (as to mecej4 as well). I don't have ready access to Maple (but possibly
> could locate someone who has it). Do you know of any free program with
> the required capability?
Maple is available free. Do you have a suitable computer to run it on?
> On 11/13/2011 8:23 PM, Gib Bogle wrote:
>> I know this is off-topic here, but posters here have good general
>> programming knowledge and may be able to help. I have some long
>> expressions, generated by computer algebra software, in which many terms
>> contain powers, expressed as x^2, c^4 etc. I need to use these
>> expressions in a C program. If I tried to do the conversion manually it
>> would take an age and I'd be bound to make mistakes. To give an idea of
>> the scale of this task, the equations are in three text files, each
>> about 700 Kb, with about 5000 lines of about 130 characters. (I didn't
>> create these, it was done for me by one Robert Lewis using his Fermat
>> program).
>> I wonder if there exists a program for converting this kind of standard
>> maths format into C code. As an illustration, here are the first two of
>> 130 lines of the expression for 'a':
I managed to locate an old Matlab CD, and I've installed it on a Win32 machine. So I now do have Maple capability, albeit a few years old. Meanwhile Bob Lewis has pointed out something that should have been obvious but I missed it. All the variables appearing in the expressions are constant parameters except for the c1, c2 and c3. To be more precise, they are not known now, but will be determined in advance each time the device is deployed, in an initial setup stage. What this means is that if I could represent the expressions as polynomials in c1, c2 and c3, with coefficients given as functions of ax, ay, az etc, it would be a simple matter to precompute the coefficients in the setup stage, then pass these values to the program that uses the expressions, which would now be very small and fast.
My new question, then, is can I use Matlab symbolics (i.e. Maple) to extract the coefficients of an expression thought of as a polynomial in c1, c2 and c3? BTW this old version of Matlab has the ability to generate C code from a symbolic expression.
