Comparing mathematical expressions

Question

So here's my situation: I have two mathematical expressions which contains variables (x, y, z, etc). I have already compiled them to postfix using the shunting yard algorithm for execution and now I need a way to test if they're mathematical equal.

Examples:

x+5==5+x
x*2==x+x
4/(x/2)==8/x

My initial thinking is to just throw a couple of thousand different random inputs and see if the evaluation result is the same.

Problems I foresee with this approach: Precision problems, NaN-situations and possible overflows.

All calculations are done with Java's double type.

Any ideas? :)

Edit: As this is for a casual game, the solution doesn't need to be perfect, only good enough!

Answer 1

For the example expressions you have provided, you could transform the function to produce one polynomial divided by another, with the most significant coefficient of the divisor one, and with no common factor. This would give you a canonical form - if there was a difference the two functions would really be different. However, you would also need to represent the coefficients as arbitrary precision rationals or hit precision problems here too, and by then you will have written most of a basic computer algebra system, such as those listed at http://en.wikipedia.org/wiki/List_of_computer_algebra_systems - which does include some free systems.

Answer 2

According to Wikipidea on this topic:

http://en.wikipedia.org/wiki/Symbolic_computation

"There are two notions of equality for mathematical expressions. The syntactic equality is the equality of the expressions which means that they are written (or represented in a computer) in the same way. As trivial, it is rarely considered by mathematicians, but it is the only equality that is easy to test with a program. The semantic equality is when two expressions represent the same mathematical object, like in

It is known that there may not exist a algorithm that decides if two expressions representing numbers are semantically equal, if exponentials and logarithms are allowed in the expressions. Therefore (semantical) equality may be tested only on some classes of expressions such as the polynomials and the rational fractions.

To test the equality of two expressions, instead to design a specific algorithm, it is usual to put them in some canonical form or to put their difference in a normal form and to test the syntactic equality of the result."

That seems to be the best practice.