home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / formu220.zip / formulc.doc < prev    next >
Text File  |  1995-05-17  |  15KB  |  411 lines
  1. /*  FORMULC.DOC as of 5/17/95 (v2.2 definitive) */
  2. /*  Copyright (c) 1995 Harald Helfgott (E-MAIL: hhelf@cs.brandeis.edu) */
  3. /*  This file must be distributed with its corresponding
  4.     README.DOC. You should read it, for you will find my regular
  5.     address and the copyright and availability information there.   */
  6.  
  7.           Overview of the FORMULC 2.2 functions
  8.           -------- -- --- ------- --- ---------
  9.  
  10.  
  11.      The FORMULC set of functions is written in ANSI C. It has
  12. been tested in a 386SX running GNU CC (DJGPP 1.11), in another
  13. 386SX running Turbo C++ v3.0 and in a VAX/VMS, but it will probably
  14. run in any machine with an ANSI C compiler. The functions enable
  15. the user of a C program to enter mathematical functions and to 
  16. evaluate them very rapidly. This project was undertaken for the
  17. Finite Elements Laboratory of the School of Mathematics in the
  18. Universidad Mayor de San Marcos, Lima, Peru.
  19.  
  20.      Any programmer who handles mathematical problems must
  21. sometimes require the users of his or her programs to enter a
  22. mathematical function by the keyboard. Embedding the function in
  23. the program is time-consuming and not user friendly. Consequently,
  24. there is a large number of programs in C and Pascal that parse
  25. strings representing mathematical formulas. In fact, most good
  26. Pascal and C books have a more or less inchoate parser. However,
  27. all the formula interpreters I have seen are extremely slow.
  28.  
  29.      On May 1993, a mathematics professor in Lima, Peru asked me
  30. whether I could write a quick formula interpreter. His program
  31. needed to compute a formula entered by the user hundreds of
  32. thousands of times. I decided, therefore, to write a two-stage
  33. interpreter. First, a string containing a mathematical function is
  34. translated into another string in a postfix format. Every formula
  35. goes through this stage once. Then, the string in postfix format is
  36. interpreted whenever one wants to evaluate the mathematical
  37. function. Since this string's structure makes the use of a stack
  38. rapid, lacks white space and has additional characters to ensure
  39. that the computer understands the formula swiftly, interpretation
  40. is little time consuming. Although extra space is needed for the
  41. intermediate string, the velocity of the two-stage method
  42. compensates the space overhead.
  43.  
  44.      The FORMULC routines are easy to use. They are all in one
  45. file, FORMULC.C; one only needs to type
  46.          #include "formula.h"
  47.      and to link FORMULC with one's program to use the functions.
  48. There are no initialization routines. There are utilities that
  49. describe and extend the types of expressions that the formula
  50. interpreter can understand. Moreover, I expect the program to be
  51. error free and resistant to the human fallibility of the users.
  52.  
  53.  
  54.      Please read TIME.DOC to know about the velocity of my formula
  55. interpreter (*). My address, the instructions for reporting bugs, the
  56. statement of what you are allowed to do with the program and the
  57. registration information are in README.DOC.
  58.  
  59. (*) The benchmarks for version 2.2 have not been done yet.
  60.  
  61.      Description of the functions
  62.      ----------- -- --- ---------
  63.  
  64. 1. Evaluation
  65.  
  66. formu translate(char *source, char *args, int *length,
  67.                            int *error);
  68.  
  69.  Examples:
  70.  
  71.      formu f,g;
  72.      int leng;
  73.      int error;
  74.  
  75.      f = translate("x^2 + sin(3*x) + 0.1", "x", &leng, &error);
  76.  
  77.      f = translate("1E+5 * x/x \n", "x", &leng, &error);
  78.  
  79.      gets(gsource);
  80.      g=translate(gsource, "xyz", &length, &error);
  81.          /* g is a function of x, y and z */
  82.  
  83.      This function transforms a legible mathematical function in
  84. string source[] into a coded function which is returned. The
  85. arguments of source are in string arg[]; they must be lower-case
  86. letters. If source uses an  undeclared argument, translate stops
  87. coding and returns the index of the  argument in *error. In fact,
  88. if any error occurs, *error contains an approximation of the index
  89. of the character in source[] that causes the error, *length acquires
  90. the value 0 and translate returns empty code (see fnot_empty() ). 
  91. However, if source[] contains a valid mathematical function, the 
  92. transformation occurs, *length contains the length of function[] (not 
  93. including the final \0) and *error contains -1.
  94.  
  95.      The result string is dynamically allocated. It is likely to be
  96. far larger than source[]. If it does not fit in memory, or if any other
  97. out-of-memory or internal error occurs, translate returns NULL, but *error 
  98. contains -1. The result string can always be destroyed using destrf().
  99.  
  100.           source[]                |   Length of function[]
  101.                       |   (VMS 5.5 CC)
  102.                       |
  103.                   "4", "4.0" or "4.0E-3"  |     9 chars
  104.                   "x"                     |     2 chars
  105.             "(x+3)^2"                     |     22 chars
  106.             "(x+3)*(x+3)"                 |     25 chars
  107.             "atan2(x^2,sqrt(x)-x))"       |     21 chars
  108.             "acos(cos(x)-x)"              |     9 chars
  109.  
  110.  
  111.        The syntax of source is the following one (in Extended
  112. Backus-Naur Form):
  113.  
  114.      source = expression "\0"
  115.      expression = [-] summand {("+" | "-") summand}
  116.      summand = factor {("*" | "/") factor}
  117.         /*Please, don't forget "*" ! */
  118.      factor = base {"^" base}
  119.      base = "(" expression ")" | function "(" expression ")" |
  120.          function "(" expression "," expression ")" |
  121.    function "(" expression "," expression "," expression ")" |
  122.                       number | parameter
  123.      function = a string in the function table
  124.      parameter = a lower-case letter mentioned by arg[]
  125.      number = any nonnegative number  /* the sign is considered in
  126.                                     the definition of expression */
  127.                              /* please write 3.5E-3, not 3.5e-3 */
  128.  
  129.      This description of the syntax mimics the algorithm in
  130. translate(...). It must be noticed that -3+5*6 and 3+5*(-6) are
  131. allowed, but 3+5*-6 and 3+-5*6  are not.  White space is ignored. 
  132. Moreover, translate(...) is not case-sensitive.
  133.  
  134.  
  135. Precedence:
  136.  
  137.     parentheses, function
  138.     power
  139.     unary minus
  140.     * /
  141.     + -
  142.  
  143.     
  144.      translate(...) works recursively. First, it locates the
  145. operator with  the lowest order of precedence. Then, it calls
  146. itself to translate each operand. Thereafter, it adds the operator
  147. at the end and stops. If both operands are constants, translate
  148. executes fval to evaluate the expression at "compile time". (Beware
  149. of overflows! They can be perceived by the standard methods.) If
  150. there is no operator, translate(...) checks whether its input is
  151. a variable or a constant. If the input is invalid, translate(...)
  152. points out the error. Otherwise, *error contains -1.
  153.  
  154.      The coded function in string function uses postfix notation.
  155. The syntax is the following one:
  156.  
  157. coded function = ce "\0"
  158. ce = ("" | ce | (ce ce) | (ce ce ce) ) operator |
  159.                                       parameter | number
  160. parameter = "V" lower-case letter
  161. number = "D" index of a real number
  162.          in a table of constants 
  163.     (there is one table for each function; it can contain up to
  164.          256 doubles)
  165. operator = "^" | "+" | "*" | "-" | "/" | "M"  /*i.e. unary minus */
  166.                                        | function
  167. /*each operand has a characteristic number of operands
  168.                     (i.e. ce's) */
  169.  
  170. function = "F" index of a function in the table (one char)
  171.       /* Be careful! The index may be represented as \0 */
  172.       /* Trust only the result of translate when finding */
  173.       /*  out the length of the coded function.         */
  174.       /* Since there can be more than 128 functions, */
  175.       /* please declare function[] as an array of unsigned */
  176.       /* char                                              */
  177.    No blanks exist.
  178.      The standard functions are exp(), ln(x), sin(), cos(), tan(),
  179. asin(), acos(), atan(), abs(), pi() (without parameters inside the
  180. brackets), sqrt() and rnd(). One can add new functions by using fnew(..);
  181. the name of each function obeys C regulations but can be as long as
  182. needed. If a new function  is used, fnew(..) must be called in the
  183. same run as translate(..); one must  not call fnew, translate a
  184. function, store the coded function and call a  program that uses
  185. fnew(..) and loads the coded function.
  186.  
  187. double fval(formu function, char *args, ...);
  188.  Examples:
  189.  
  190.      function=translate("x^2+sin(cos(x))","x", &leng, &error);
  191.      result=fval(f,"x",3.0);  /* 3.0, not 3 */
  192.      /* returns 3^2+sin(cos(3)) */
  193.  
  194.  
  195.      g=translate("n*m","nm", &leng, &error);
  196.      for(p=0; p<100; p++)
  197.       for(q=0; q<1000; q++)
  198.        a[p][q]=fval(g,"nm",(double) p,(double) q);
  199.                          /* the arguments must always be double */
  200.  
  201.   fval(...) calculates the value of a coded mathematical function
  202. in string function[] when the arguments, whose names are in string
  203. args[], are given. If there are not enough parameters or if the
  204. parameters don't belong to the function, the result is undefined.
  205. If there are any mathematical errors such as trying to obtain the
  206. square root of -5, errno is EDOM (domain error) or ERANGE (range
  207. error), the results are Infinity and Not-A-Number, or the program
  208. stops, depending on the compiler and how you use it.
  209.  
  210. double f_x_val(formu function, double x);    
  211.  
  212.  Examples:
  213.       result=f_x_val(f,3);   /* calculates f(3) if f is a function
  214.                                                             of x */
  215.  
  216.      A shorthand version of fval(..) for functions of x. It is
  217. about as rapid as fval(..) .
  218.  
  219. double fval_at(formu function);
  220. void make_var(char var, double value);
  221.  
  222.     This is the interface for the evaluation of functions whose
  223. number of parameters is determined at run-time.
  224. Example:
  225.  
  226. make_var('x',2);
  227. make_var('y',0.2);
  228. make_var('z',-2);
  229. result=fval_at(f);
  230. /* evaluates f(x,y,z) at point x=2, y=0.2, z=-2 */
  231.  
  232. 2. Management of the Function Library
  233.  
  234. int fnew(char *name, Func f, int n_pars, int varying);
  235.  
  236.   Examples:
  237.  
  238.      fnew("sinh",(Func) sinh,1,0);   /* sinh has been declared as
  239.                                             double sinh(double); */
  240.      fnew("logb",(Func) logb,2,0);   /* logb has been declared as
  241.                                        double logb(double, double); */
  242.      fnew("rnd", (Func) rnd, 0,1);  /* varying = 1 because the result
  243.                     of rnd is not determined
  244.                     by its parameters.         */    
  245.  
  246.    fnew(...) adds a user-defined C function with double parameters
  247. to the  library of FORMULA. The C function can have from 0 to 3
  248. parameters. fnew(...)  returns 0 if the library is full (255
  249. functions) or if other error occurs.  Otherwise, it returns 1.
  250.  
  251.     Please, do not call any function 'E' ! It would be similar
  252. to exponential notation (e.g. 3.5E+3) .
  253.  
  254. int read_table(int i, char *name, int *n_of_pars, int *varying);
  255.  
  256.   Example:
  257.      i=0;
  258.      while(read_table(i++, name, &n_pars, &varying)
  259.          printf("%s %d",name,n_pars);
  260.  
  261.     read_table copies the name, the number of parameters and the
  262. non-determinism bit of function #i onto name[], *n_of_pars and *varying. 
  263. If function #i does not exist, read_table returns 0. Otherwise, it
  264. returns a positive number.
  265.  
  266. int where_table(char *name);
  267.  
  268.  Example:
  269.      if(where_table("sinh") == -1)
  270.       printf("Hyperbolic sine not defined.");
  271.  
  272.    If there is a mathematical function called name[],
  273. where_table(..) returns  its index in the table of functions.
  274. Otherwise, where_table(..) returns -1.  Use fnew(..) to define
  275. mathematical functions which are not in FORMULA's  standard
  276. library.
  277.  
  278. int fdel(char *name);
  279.  
  280.  Example:
  281.     if(where_table("sinh" != -1)
  282.      fdel("sinh");
  283.  
  284.    If there is a mathematical function called name[], fdel deletes
  285. it. If fdel is succesful, it returns a non-negative number;
  286. otherwise, it returns -1.
  287.  
  288. 3. Random-Number Generation
  289.     
  290.     The standard library of FORMULC includes double rnd(void).
  291. Any program that generates random numbers through FORMULC must call
  292.  
  293.     void rnd_init(void);
  294.  
  295. first.
  296.  
  297.     By default, FORMULC uses the random-number generator r250 (written 
  298. by W. L. Maier, S. Kirkpatrick and E. Stoll). If you want to use another
  299. RNG, you must define functions according to the declarations
  300.  
  301.     double rnd(void);
  302.     void rnd_init(void);
  303.  
  304.  Furthermore, you must compile formulc.c with -DMY_RND (i.e., defining
  305. MY_RND).
  306.  
  307.      
  308. 4. Miscellaneous
  309.  
  310. void destrf(formu f);
  311.  
  312.  frees memory occupied by f
  313.  
  314. void make_empty(formu f);
  315.  
  316.  makes f an empty function
  317.  Note: This function should NOT be used to dispose functions but to
  318. initialize them. It does not deallocate any memory. Use destrf(f) to 
  319. destroy a function.
  320.  
  321.  
  322. int fnot_empty(formu f);
  323.  
  324.  returns 1 if f is not an empty function
  325.  returns 0 otherwise
  326.  
  327. const char *fget_error(void);
  328.  
  329.  Every routine in FORMULC gives an error message if it fails and erases
  330. the previous error message from memory if it succeeds. fget_error()
  331. renders an error string if the last routine failed; otherwise, it
  332. returns NULL.
  333.     
  334.     The only routines that does not alter the error message is
  335. fget_error() itself.
  336.  
  337. Normal error messages:
  338.  they are self explanatory.
  339. Internal error messages:
  340.  These errors should never happen. If they do occur, please, send
  341. me E-MAIL (my address is at the beginning of this file) describing
  342. under what circumstances the program failed. Be as precise as possible.
  343.  
  344. value:
  345.  I1: unrecognizable operator
  346.  I2: too many parameters
  347.  I3: corrupted buffer
  348.    I1, I2 and I3 can occur if you change the contents of a coded
  349. function directly. You should never do that.
  350.  
  351. translate:
  352.  I4: size estimate too small
  353.     This is a serious error, for it happens when a function
  354. occupies more space than it should and overwrites some variables.
  355.  
  356.  
  357. UNIX-filter version of FORMULC:
  358.  
  359.     If you compile formulc.c with -dSTAND_ALONE, you will obtain
  360. an executable file. This program will act as a UNIX filter. Given a
  361. function and the values of the variables, it will return the value of the
  362. function. This process is repeated several times; an input file
  363. with several columns produces an output file with a single column containg
  364. the results of the function.
  365.     
  366.     Example:
  367.  
  368.     formulc "a*b+c"      "acb"          <data      >results
  369.         (function)  (variables corresponding
  370.                  to the columns)    
  371.  
  372.     uses file "data":
  373.  
  374.         1 3 2
  375.         2 0 9
  376.         4 1 3 
  377.         1 0 2
  378.         -2.4 2 3
  379.  
  380.            (the first column corresponds to a,
  381.         the second one to c, and the third one to b)    
  382.  
  383.      and outputs file "results":
  384.  
  385.        5
  386.        18
  387.        13
  388.        2
  389.          -5.2
  390.  
  391.     The user can determine the format of the output by typing a
  392. third parameter:
  393.  
  394.     formulc "a*b+c" "acb" "%f" <data >results
  395.  
  396.     outputs
  397.     
  398.     5.000000
  399.     18.000000
  400.     13.000000
  401.     2.000000
  402.     -5.200000
  403.  
  404.     The UNIX filter was done by Ralf Grosse Kunstleve
  405.                     <ralf@kristall.erdw.ethz.ch>
  406.  
  407.  
  408.  
  409.  
  410.  
  411.