ee.txt

快速表达式运算

Fast Expression Evaluator.
========================================================================

This DLL (ee.dll) provides some of 'C' routines that allow you to
incorporate mathematical expressions evaluation into your programs. For
example, using these routines you can evaluate such expressions as:
100/5*(1+2)
LN( PI )
sqrt(p*(p-a)*(p-b)*(p-c))

The main advantage of this evaluator is explained in the following
example. Suppose we ask user to define a function. And we want to
compute value of the function on a number of points. This DLL allows
to make syntactic analysis of the function definition once and then
using "image" of the expression to calculate value of the function on
any number of points. Since the syntactic analysis is made only once
time of calculation decreases by factor 20-30.

Evaluation is performed by two routines: MakeImage and Value. MakeImage
gives string form of an expression, performs syntactic analysis and
produces the image of the expression. Image is a linear sequence of fast
commands. Then if no errors occur value of the expression can be
retrieved by function Value which interprets these commands. Size of
function MakeImage in code is 450 lines while size of Value is 30.

There is also a function called Simplify available. It modifies image by
calculating almost all operations that can be calculated without knowing
values of expression's parameters. For example, 3+sin(5)+x+2^2^5 will be
replaced by 2.041+x+1024.

int MakeImage(void *image, int size, const char *formula,
              char *errorstring, int *errorposition,
              const char *argnames);

image       -- Buffer for image of expression.
size        -- Size of the buffer in bytes. The smallest size that will
               not cause an error is sizeof(int) bytes.
formula     -- String form of expression.
errorstring -- If an error is found the explanation is placed here.
               Otherwise empty string is returned. Must be large
               enough to contain 128 bytes or NULL.
errorposition --
               Zero-based position where an error occurred is returned
               through this pointer. If the position cannot be
               determined (for example, if unpaired parenthesis is found)
               -1 is returned. Also may be NULL. Note: MakeImage parses
               expressions from the end to the beginning.
argnames    -- This string should contain names of arguments of the
               expression divided by spaces. Allowed symbols are like
               in C. May be NULL or empty string.

Return values:
0 (EE_OK)           No errors were found and image is ready for
                    evaluation.
EE_SYNTAXERROR      General syntax error. See 'errorstring'.
EE_UNPAIRED         Unpaired parenthesis is found.
EE_UNKNOWNFUNCTION  Unknown function or wrong use of parentheses.
EE_UNKNOWNARGUMENT  Found an argument that is not included in the list
                    in 'argnames' or unknown constant.
EE_WRONGARGUMENTS   Wrong number of arguments in function.
EE_SMALLBUFFER      No other errors found but the buffer is too small
                    to contain image of the expression. Required number
                    of bytes is returned in *(int*)image.

If no errors are found the size of image is returned in *(int*)image.
Rest bytes can be used for other purposes. In general, size of image
can be calculated by formula:
 SIZE=(2*Nnumbers + Nunary_operators + Ncalls)*16,
where
Nnumbers         -- number of numbers or user's identifiers in
                    expression.
Nunary_operators -- number of unary operators that are not before
                    digits.
Ncalls           -- number of calls of functions that take one argument.

int Value(const void *image, double *presult,
          char *errorstring, int numberofarguments, ... );

image       -- Buffer with image.
presult     -- Returned result is placed here.
errorstring -- If an exception raises during calculation the
               explanation will be written here. Otherwise empty string
               is returned. Must be large enough to contain 128 bytes.
               May be NULL.
numberofarguments --
               Number of arguments that follow. Should be equal to the
               actual number of arguments that passed after this
               parameter.
...         -- Zero or more arguments to the expression. Must be in the
               same order as in 'argnames'. Note: all these arguments
               must be of type double. What do you think
               printf("%f %d",2,3) will print? So use numbers with
               points (e.g. 1.0) or variables of type double or cast
               them to double.

Return values:
0 (EE_OK)      No exceptions were raised and the result is a finite
               number.
EE_PARTIAL     Partial usability. Either there were exceptions during
               calculation or result is infinite. See 'errorstring'. To
               test whether the number is finite use '_finite' function.
EE_UNUSEABLE   Result cannot be represented as a number. E.g. asin(2).

int Simplify(void *image, char *errorstring);

image       -- Buffer with image for simplification.
errorstring -- Buffer for explanation of error. The same as above.

Return values:
This function returns the number of bytes by which the image has become
shorter. If no simplification is possible zero is returned.

Supported functions:

Arguments or returns of all trigonometric functions are in radians.
sin(x)   \
cos(x)   - Return is precise if -9e+18 < x < 9+e18.
tan(x)   /
sinh(x)  \
cosh(x)  - Hyperbolic.
tanh(x)  /
asin(x)    Returns the arcsine of x in the range -pi/2 to pi/2.
           To avoid exceptions x must be in range [-1,1].
acos(x)    Returns the arccosine of x in the range 0 to pi.  x must be
           -1 <= x <= 1.
atan(x)    Returns the arctangent in the range -pi/2 to pi/2.
atan2(y,x) Returns the arctangent of y/x in the range -pi to pi using
           the signs of both parameters to determine the quadrant of the
           return value. x and y must not be both zero.

exp(x)     Returns the exponential value.
ln(x)      Return the logarithm of x. x must be >0.
log(x)     The same as ln(x).
log10(x)   Return the logarithm of x with the base of 10. x must be >0.
pow(x,y)   Returns x raised to the power of y. Well defined not for all
           pairs of x and y. The same as x^y.
sqrt(x)    Returns the square-root of x. x must be >= 0.
mod(x,y)   Returns the floating-point remainder of x/y. y must not be 0.
           The same as x%y.
hypot(x,y) Returns the length of the hypotenuse. Equivalent to the
           square root of x^2+y^2.

deg(x)     Converts radians to degrees.
rad(x)     Converts degrees to radians.

abs(x)     Returns the absolute value of x.
floor(x)   Returns the largest integer that is <= x.
ceil(x)    Returns the smallest integer that is >= x.

j0(x)    \
j1(x)    - Return Bessel functions of the first kind: orders 0, 1 and n,
jn(n,x)  / respectively.
y0(x)    \
y1(x)    - Return Bessel functions of the second kind: orders 0, 1 and
yn(n,x)  / n, respectively. Truncation of n to integer is performed in
           accordance with C rules.

sign(x)    Sign. -1 for x<0; 0 for x=0; 1 for x>0.
step(x)    Heaviside step. 0 for x<0; 1 for x>=0.
max(x,y)   Returns greater number.
min(x,y)   Returns smaller number.

Known constants:
pi =3.1415926535897932385
e  =2.7182818284590452354

Neither functions nor these constants are case sensitive, but user's
identifiers are case sensitive.

Operators are handled in the following priority:
1) Unary (+) and (-) signs.
2) "To the power of" symbol: (^).
3) Times (*), divide (/) and modulus (%).
4) Plus (+) and minus (-).

Note: Because the priority of unary operator is higher than the priority
of "power" operator the expressions like -(3)^2 will evaluate to 8 other
than -8.

Some functions operate with numbers 'infinity' and '-infinity'. So
1/(1/0)=0; atan(1/0)=pi/2; atan(-1/0)=-pi/2; exp(-1/0)=0; sign(3/0)=1.
MakeImage performs strict syntactic check. Let's give  C-style
definition of an expression.

expression:
    simple_number
    function_call
    (expression)
    expression operator expression
    unary_operator expression

operator: one of + - * / % ^

With one exclusion: two sequential unary operators are not allowed.
simple_number is a known identifier or a number that can be read
entirely by the function 'strtod'.

Examples of valid numbers:
1
-2.3
3.
-.40              =-0.4
5.6e+7            =5.6*10^7
-.6E7             =-6*10^6
07.d-0008         =7*10^(-8)
- 00000000.08     =-0.08
9.D-0000100000000 =0
-10000000000000000000000000000000000000000.11    =-(10^40)

To mark exponential part either e, E, d or D can be used. Numbers in
absolute value should be less than 1e308.

Examples of illegal numbers:
1OO         unrecognizable symbol
-2.0e       no exponential part, but 'e' sign is present
3e444       too large
-4e5.6      exponential part must be integer
2 . 3       spaces in numbers are not allowed

Limitations:
Maximum length of expression, arguments or image is 2e9 bytes. Maximum
number of arguments is 100. Maximum depth of enclosed parentheses is
100. But it is also limited by stack of your application. Each enclosed
pair of parentheses takes 60 bytes of stack.

Calculations are performed with numbers of type double. So precision
is not less than 15 digits.

All these functions do not use heap.

Time that MakeImage takes is approximately proportional to the length of
expression. Time that Value takes is approximately proportional to the
length of the image.

Benchmark:
Comparison of calculating speeds between this evaluator and compiled
with volatile variables code was made on Pentium 100.
The expression:

2+2-2+2-2+2+2*2*2+2+2/2+(2+2-2+2-2+2*(2+2/2+2+2/2+2))+2+2-2+2-2+2+2*2*2+
2+2/2+(2+2-2+2-2+2*(2+2/2+2+2/2+2))+2+2-2+2-2+2+2*2*2+2+2/2+(2+2-2+2-2+2
*(2+2/2+2+2/2+2))+2+2-2+2-2+2+2*2*2+2+2/2+(2+2-2+2-2+2*(2+2/2+2+2/2+2))

was evaluated  1000000 times for 45 seconds. The same compiled expression
took 7.1 seconds. The ratio is 6.4
the another expression:

atan(asin(acos(abs(cos(sin(tan(2)))))))+
atan(asin(acos(abs(cos(sin(tan(2)))))))

was evaluated 1000000 times for 45 seconds by Value and for 39 seconds
by machine code. The ratio is 1.16

The file ee.cpp contains an example of usage of these routines. Make
sure to link it with ee.lib. ee.exe is compiled ee.cpp.

Similar application can be found at
http://ftp.digital.com/pub/micro/pc/winsite/win3/programr/calcdll.zip
But it can only calculate expressions without making "image". And its
syntactic analysis is not strict.

This software is free and freely distributable.

If you want to use these routines directly in your application, add your
functions or implement on platforms other than Intel/Windows95/NT mail
me and you will receive the source code of the DLL. Propositions or job
opportunities are also welcome.

November, 29, 1997.

Laptev Eugene.
E-mail:  [e-mail]
WinTalk: [e-mail]

Prekloniaju golovu pered temi, kto zarobatyvaet den'gi nichem.