Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say you have a few expressions like the following:

$$\begin{array}((x+17)^2 \\ x^2 + 34x + 289 \end{array} \\ 288 + \frac{x^2}{2} + \frac{x^2}{2} + 34x + 1 \\ [...] $$

You get the idea: there's an infinite number of ways of representing the same expression. The challenge is that my application is validating answers to math problems, input by math students practicing a certain concept. I'd like to make sure that whenever they submit an answer, the checker is completely insensitive to the issues of ordering, simplification, formatting etc. which would be plain frustrating. I'd also ideally like to support more than one variable such as x, y, z in the same expression.

What's a reliable way to check that two expressions are the same? The most brute force way I can think of would be to just plug a number into each variable of each expression and see what the result is.

I have a hunch however that there might be ways of getting false positives this way. That, and I might be either missing something really obvious about this, or there might be a better way of doing the comparison.

Would love to hear what you think.

share|improve this question
    
Compare the constant & the coefficients of the different powers of $x$ –  lab bhattacharjee Nov 28 '13 at 4:53
    
Type the difference into a good symbolic math program and ask it to simplify. If it simplifies to zero, you win. –  Gerry Myerson Nov 28 '13 at 4:55
    
@GerryMyerson any command-line programs you would recommend on Linux? I was going to build a really simple compiler for these expressions, but I'd certainly prefer to leverage an existing tool. –  Alexandr Kurilin Nov 28 '13 at 5:01
    
I don't know what Linux is. The only symbolic math program I know much about is Maple. And if this is really a coding question, maybe there are better sites for it. –  Gerry Myerson Nov 28 '13 at 5:03
    
@GerryMyerson it's both a software and a mathematics question. Here on math.stackexchange I'm trying to make sure that my mathematical approach is sound before I focus too much on the implementation. –  Alexandr Kurilin Nov 28 '13 at 5:04

3 Answers 3

up vote 4 down vote accepted

In general, this is a hard problem. For classes of expressions for which there is a canonical form, such as polynomials (in any number of variables), the answer is straightforward: two expressions are equal if and only if they have the same canonical form. (A canonical form means that for each expression there is one and only one canonical expression to which it is equal, and there is an effective procedure for calculating the canonical form of any given expression.) Then you can get an algorithm for comparing two expressions: calculate the canonical form for each expression and check to see if the canonical forms are identical.

Algebra students learn to do exactly this in order to decide themselves if two polynomials are equal. (Students of arithmetic learn an analogous method for deciding if two arithmetic expressions are equal, for example converting the expression $2\cdot(3+4)$ into the canonical form $14$; this algorithm is a subroutine of the one that reduces polynomial expressions to canonical form.) A canonical form for polynomials is to combine all the like terms, list the terms in descending order of degree, with the terms of equal degree listed in lexicographic order by the variables they contain, or something of that sort. Calculating a canonical form for an arbitrary polynomial is not a difficult matter. It is the sort of thing a competent programmer can produce in a couple of hours; or as several other people here have suggested you could put the solutions into a computer algebra system, which will contain exactly this sort of algorithm for several different sorts of expressions.

But for more general expressions it can be extremely difficult, or even impossible, to decide of the two expressions are equal. There is no canonical form, and recognizing when two particular expressions are equal can be a major theorem. For example, consider the expressions $\cos 2x$ and $\left(\cos x\right)^2 - \left(\sin x\right)^2$. These are equal, but not obviously so. Or for a more difficult example, consider the two expressions $$0$$ and $$\sum_{a,b,c > 1\atop n>2} I(a^n + b^n - c^n)$$ (where $I(x)$ denotes the function which has $I(0)=1$ and $I(x)=0$ for $x\ne 0$). It was conjectured for some time that these two expressions were equal, but the proof turned out to be somewhat tricky.

The previous paragraph was a joke, but it is a serious joke: a substantial part of mathematics is precisely how to perform such calculations and to recognize when two different-seeming expressions are equal. Euler is famous (among other things) for recognizing that $e^{ix}$ and $\cos x + i\sin x$ are equal expressions. Leaving aside jokes, a theorem of Daniel Richardson says that for a fairly small, fairly natural class of expressions, there is no method that can reliably determine equality in all cases.

So to get an answer, you need to be more specific about what your question is. If you only need to compare polynomials, the answer is fairly straightforward. If your expressions are more complicated than that, there may or may not be an answer; it depends on what is in them.

[ Addendum: I see that you have added comments saying that you are only interested in polynomials, and that you want to know if your idea of substituting test values for $x$ is sound. It is sound, but plugging in one number is not enough, even for the simples polyomials. The polynomials $x+1, 3x-1$, and $3-x$ all have the same value at $x=1$. But you can easily avoid false positives by checking $n+1$ different values for an $n$th-degree polynomial. A polynomial of degree $n$ is completely determined by its values at $n+1$ points, so if two polynomials of degree $n$ agree at $n+1$ different points you can be sure they are identical; it does not even matter which $n+1$ values you sample. (In the example above, any value of $x$ other than $x=1$ is sufficient to distinguish the three polynomials.) Similarly if the polynomial has three variables $x$, $y$, and $z$, of degrees $n_x, n_y, $ and $n_z$, it suffices to select $n_x+1$ values for $x$, $n_y+1$ values for $y$, and $n_z+1$ values for $z$, and then check all $(n_x+1)(n_y+1)(n_z+1)$ triples of those values. ]

share|improve this answer

@AlexandrKurilin I believe the mathematical approach is not the problem. The software is the key. Two expressions $A$ and $B$ are equal iff: you can go from $A$ to $B$, or you can go from $B$ to $A$, or you can go from $A$ to $C$ and from $B$ to $C$. Where go means that you only use iff operations.

As you mentioned, there might be infinitely many representations. So, solutions for your problem that come to mind are:

  • Ask the students to express the solution in a fully simplified expression. This is application dependent, maybe some times it won't be unique. But as an example, if the answer must be a polynomial, then you can request them to factor it, or fully expand it and group like terms, etc.
  • Provide a list of possible answers or answer templates. I am not particularly fond of multiple choices problems in math, but maybe you can provide them with guidelines of how the different possible answers might be expressed as. From there, creating a parser like you suggested would be easier.
  • Use an engine like Mathematica or Mapple that can compare the solutions for you. The automation you are looking for might be achieved by coding in those programs. Here the math aspect of your question would be resolved fully.

Your suggestion of using values is very error prone for two reasons. 1. Unless you are coding in an environment with arbitrary precision algebra capabilities, then two different correct expressions might yield (slightly) different results. 2. Unless you test on every possible value for your variables, then you can't confirm the proposed solution is equal to your correct expression.

Considering this, then I would test over a list of test values and not just one. An easy way in one variable would be to define ends to a segment $a$ and $b$, and a step size $\delta$ and populate the list with $a$, $a+\delta$, $a+2\delta$,$\cdots$,$b$. Let's call them $x_1$, $x_2$,$\cdots$,$x_n$, and let $A(x)$ and $B(x)$ the two expressions to compare. Because of numeric errors, I would define a metric and a tolerance to compare them and declare them equal if, for instance, $$\sum_{i=1}^n\left[A(x_i)-B(x_i)\right]^2<\epsilon$$

The tolerance $\epsilon$ may need to be adapted for problems that have sensitive regions.

share|improve this answer
    
Thanks for the extensive response, Kevin. Regarding 2, I'm not looking for a completely bullet-proof solution right now if it increases implementation complexity tenfold. I'm tempted to go with a "good enough" one for now if it covers 99.9% of the cases. As in, I feel that if I avoid plugging 0 into these equations (to avoid situations like x^2 + x = x^3 + x^2 + x) I should be able to avoid the vast majority of the false positives. What are your thoughts? –  Alexandr Kurilin Nov 28 '13 at 5:32
    
I edited the answer to address your comment. Note that the list of test values, metric and tolerance should be adapted to the problem at hand. –  Kevin Nov 28 '13 at 5:50

For polynomials you can expand all products and collect like terms to get a canonical form. Or you could compute the maximum possible degree d and check that two polynomials have the same values at d+1 points.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.