1. RE: simplify math expression
- Posted by Matthew Lewis <matthewwalkerlewis at YAHOO.COM> Jun 11, 2002
- 448 views
> -----Original Message----- > From: tone.skoda at gmx.net [mailto:tone.skoda at gmx.net] > some math expert will sure know how to do this. > > simplify math expression so that you remove all braces and > put arguments in > alphabetical order. no calculation, just "pretty print". > > examples: > > b+(c+(a+d)) --> a+b+c+d > c+((d+b)+a) --> a+b+c+d > (b*a)/c --> a*b/c > a/(b/c) --> a*c/b > b*(c+a) --> a*b+a*c > > i guess removing all braces and puting arguments in > alphabetical order is > not so important, > but important is that these two expressions get simplified to > same result: > b+(c+(a+d)) --> a+b+c+d > c+((d+b)+a) --> a+b+c+d > > tough cookie huh? > speed is also important > i didn't find this feature in any math evaluator library in > euphoria archive > or on the net. if you know some c source code for this that > would also be > okay, i'll just make dll out of it. My current matheval lib makes a start at this. I haven't updated the lib proper, but and updated version is included in EuSQL on my page: http://www14.brinkster.com/matthewlewis/projects.html The relevant files are * matheval.e : Main matheval lib file * symeval.e : Symbolic/algebraic simplification * parseval.e : Parses mathematical/logical expressions * booleval.e : Evaluates boolean expressions * ppeval.e : Formats matheval sequences for display * misceval.e : Used by matheval.e There's not much documentation there, but if you d/l the matheval from the page, you can get some old docs that explain how some stuff works. One of my long term goals of the project was to be able to do some fairly serious symbolic calculations, which requires some pattern matching capability. Basically, each expression is a recursive sequence: sorta-pseudocode: a+b+c = {ADD,A,{ADD,B,C}} or {ADD,{ADD,A,B},C} etc In symeval, you'll see some code that simplifies expressions. You might be interested in ExpandAddition(). This function will take the above addition example, and return {A,B,C}. You could always sort these, and then use CompactExpr() to get back to a real matheval expression. Scanning the file, I don't see that it would know what to do about a/(b/c) --> a*c/b although it could probably be made to do so. This could probably be done in ExpandMult(): function ExpandMult( sequence expr ) integer ix, jx atom exp sequence term, bits ix = 1 if matheval_seq( expr ) then expr = { expr } end if while ix <= length(expr) do if expr[ix][FUNC] = MULTIPLY then expr[ix] = { expr[ix][ARG1], expr[ix][ARG2] } for i = 1 to 2 do term = ExpandMult( expr[ix][i] ) expr[ix] &= term end for --- start adding code here --- elsif expr[ix][FUNC] = DIVIDE then expr[ix] = { expr[ix][ARG1], expr[ix][ARG2] } if expr[ix][2][FUNC] = DIVIDE then if expr[ix][1][FUNC] = DIVIDE then -- (a/b)/(c/d) => (ad)/(bc) expr[ix] &= expr[ix][1][ARG1] expr[ix] &= expr[ix][2][ARG2] expr[ix] &= {{EXPONENT,{MULTIPLY,expr[ix][1][ARG2], expr[ix][2][ARG1]},{CONSTANT,{-1},{}}}} else -- a/(b/c) => (ac)/b expr[ix] &= expr[ix][1][ARG1] expr[ix] &= expr[ix][2][ARG2] expr[ix] &= {{EXPONENT,expr[ix][2][ARG1],{CONSTANT,{-1},{}}}} end if end if Then... function MultiplyOut( sequence expr ) integer func, ix, jx sequence rest, temprest, bits, term, divide -- add this object exp ... ix = find(ONE, expr ) while ix do expr = RemoveOne(expr, ix) ix = find(ONE, expr ) end while --- add code here --- divide = {} ix = 1 while ix <= length(expr) do if expr[ix][FUNC] = EXPONENT and expr[ix][ARG2][FUNC] = CONSTANT and expr[ix][ARG2][ARG1] < 0 then -- find all negative exponents and separate them out expr[ix][ARG2][ARG1] *= -1 divide = append(divide,expr[ix]) expr = RemoveOne(expr, ix) else ix += 1 end if end while --- stop adding here --- expr = CompactExpr( expr, MULTIPLY ) --- add code here --- if length( divide ) then divide = CompactExpr( MultiplyOut( divide ), MULTIPLY ) expr = {DIVIDE, expr, divide} end if -- stop adding here--- return expr end function That should put everything that belongs on the bottom of the division. I haven't fully tested this, and its been a while since I've messed around in symeval, but that should do the trick for you. If you do the sort on ExpandMult() and ExpandAdd(), it should handle all the cases you've listed. NB: The main point of the code was to figure out if things could be put into polynomials, because these are highly optimized [in the lib] versus a long chain of addition, multiplication and exponentiation that otherwise makes a polynomial. In ppeval.e, you could change the routines easily enough to not output ()'s around everything. You can download the actual lib to get some documentation that's still pretty accurate. The only thing that's changed (besides more functionality) is the modularity of the lib. Also, the demo that's up there is pretty cool IMHO. :) It's sorta like a graphing calculator program. You can enter in expressions, variables and equations and then evaluate and graph them. Matt Lewis
2. RE: simplify math expression
- Posted by Matthew Lewis <matthewwalkerlewis at YAHOO.COM> Jun 11, 2002
- 424 views
> -----Original Message----- > From: Matthew Lewis [mailto:matthewwalkerlewis at YAHOO.COM] Oops! There should be some {} around the &= (or use append) > expr[ix] &= expr[ix][1][ARG1] > expr[ix] &= expr[ix][2][ARG2] should be expr[ix] &= {expr[ix][1][ARG1]} expr[ix] &= {expr[ix][2][ARG2]} and > expr[ix] &= expr[ix][1][ARG1] > expr[ix] &= expr[ix][2][ARG2] should be expr[ix] &= {expr[ix][1][ARG1]} expr[ix] &= {expr[ix][2][ARG2]} Matt Lewis
3. RE: simplify math expression
- Posted by a.tammer at hetnet.nl Jun 11, 2002
- 404 views
Hi Matthew, maybe we could cooperate on nimplementing your libs and my= ICD.lib could turn into quite a powerful tool I guess a@t, antoine
4. RE: simplify math expression
- Posted by Matthew Lewis <matthewwalkerlewis at YAHOO.COM> Jun 11, 2002
- 432 views
> -----Original Message----- > From: a.tammer at hetnet.nl [mailto:a.tammer at hetnet.nl] > maybe we could cooperate on nimplementing your libs and my ICD.lib > could turn into quite a powerful tool I guess It's pretty easy to add new stuff to the lib with an include file. In fact, booleval.e is an add on I wrote. You don't have to have booleval.e to run matheval. If you want to add a new type of matheval sequence, you have to create the funtion that handles it, a parse routine, a pretty print routine, and you also need to initialize it. In order to parse it, you might have to fool the parser using some notation like (otherwise, it would try to make 1e1000 into a constant, i.e., atom--KABOOM): MAKEBIG("1e1000") Then, for the parsing routine for MAKEBIG (really a function), you would have to know to convert the token to your right (should be {DATA,"1e1000"} ) into a BIGNUM. My notation for the parsing routines is to prefix the routine with a 'C', for Collapse, because that's actually what it does. The parser scans the input and tokenizes everything, and then, based on precedence rules (specified in the initialization), the 'Collapse' routine sucks up the tokens around it (based on whether it's binary or left/right unary). You would also have to use add_to_func(). This would allow the builtin operators to use your new stuff. For instance, ADD doesn't know how to add BIGNUM's. So you would write a routine that handles all the cases of adding BIGNUM's (BIGNUM+BIGNUM,BIGNUM+CONSTANT, etc). I don't think you'd be able to have constant operations automatically promote to BIGNUM's, but then you probably shouldn't be using constants if you think you might create a BIGNUM. You could always use MAKEBIG to promote manually like if you had a variable or some other result that you knew was a constant (since it would be faster to calculate as a constant). If you're interested, I could help you with any questions. I'd definitely recommend reading the docs before you start. They give you an idea of how some of the guts of the lib work. Matt Lewis