On May 25, 2012, at 3:39 PM, Natalia Smirnova <smirnovanatalia2...@gmail.com> wrote:
> Hello, > > I integrated Sympy into the learning system which is meant for > "replacing the pencil and paper that students would ordinarily use to > solve math homework problems." > In this system a student is expected to enter full solution of the > problem, step by step. > > I use Sympy to compare expressions, entered by student (exp1), with > expressions stored for the possible solutions of the task being solved > (exp2). > Roughly it's like that: if simplify(exp1 - exp2) == 0, then student > entered a correct step. > > My science advisor wonders about the simplification procedure in > Sympy. He says - how come, the problem of simplification is > algorithmically unsolvable, how it works? So, the question is: > > - Can the procedure of expression simplification be described this way > - > http://cane.yuntech.edu.tw/member/WRC2004/Computer%20Algebra%20Papers/Understanding%20Expression%20Simplification.pdf > - part 5.2. "Implementations"? I don't think we apply that exact method, but the basic idea is the same. We have a bunch of targeted simplification functions. Most of these live in the simplify module. For example, factor() powsimp(), trigsimp(), combsimp(), and so on. In simplify(), we try to apply these intelligently to the input expression. For example, trigsimp is used only if the expression contains trigonometric functions. We apply different combinations of these, and then pick the answer that is the simplest, based on a metric. The original expression is included in this test, so simplify() should never make an expression more complicated. The metric we use is count_ops(), which is just the total number of operations in the expression. In the development version of SymPy, you can make your own metric function to pass in to simplify(). > > - Is there any data about how often simplification of expressions > doesn't work? How can "the class of expressions" - for which > simplification in Sympy is done well - be described? Unfortunately not really, since simplify() is mostly a heuristic that we are constantly trying to improve. The only kind of expressions that you can say for certain will always simplify to zero when it is zero in SymPy are rational functions, because they can be put into canonical form (p/q, where p and q are polynomials with gcd 1 and, say, q is monic), so you know a ration function is identically zero if and only if its canonical form is 0/1. Algorithms exist to canonicalize algebraic expressions, but they haven't been implemented for the most part yet. For transcendental expressions, there exist only heuristics. In my personal experience, if an expression is really zero but doesn't simplify to such, it's usually for one of two reasons: - The simplification required to reduce the expression to zero is quite complicated. To even simplify such an expression by hand requires a bit of ingenuity. This case is rare, but it does come up. It probably wouldn't come up in your situation, unless the takes a completely novel route that is correct but way off from your expected solution. - The simplification is not valid for some values if the variables. This is much more common. In SymPy, we assume all Symbols are complex by default, and try to avoid simplifications that are not valid for all complex numbers. For example, sqrt(x**2) == x is true only when x is positive. Even the identity log(exp(x)) == x is not true for all complex x (because if you replace x with x + 2*pi*I*n, exp(x) remains the same). The easiest way to avoid this is to put the necessary assumptions on your variables, like Symbol("x", real=True). Also, many simplification functions like logcombine() and expand() have force options that you can pass to force simplifications regardless of assumptions (we probably should add this option to simplify() itself). If you come across an expression that simplify() can't handle, and you're sure it's not just because of assumptions, then it should be considered a bug, and should be reported on our issue tracker on Google Code. This is especially true if the simplified form of the expression is just 0. Aaron Meurer -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com. To unsubscribe from this group, send email to sympy+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
