Comparison of mathematical expressions

Question

So here is my situation: I have two mathematical expressions that contain variables (x, y, z, etc.). I already compiled them into postfix using the shunting yard algorithm to execute, and now I need a way to check if they are mathematically equal.

Examples:

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

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

The problems that I foresee with this approach are: precision problems, NaN situations and possible overflows.

All calculations are performed using the Java double type.

Any ideas? :)

Edit: since this is for a casual game, the solution does not have to be perfect, just good enough!

Answer 1

In the above examples, you can convert a function to create one polynomial divided by another, with the most significant divisor coefficient and without a common coefficient. This will give you a canonical form - if there was a difference, then the two functions would indeed be different. However, you will also need to represent the coefficients as arbitrary precision rationalities or problems with precision problems here, and by then you had written most of the basic computer algebra system, such as those listed at http://en.wikipedia.org/wiki/ List_of_computer_algebra_systems - which includes some free systems.

Answer 2

According to Wikipidea on this subject:

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

"There are two concepts of equality for mathematical expressions. Syntactic equality is the equality of expressions, which means that they are written (or represented on a computer) in the same way. As trivial, it is rarely considered by mathematicians, but it is the only equality that can be easily verified using programs: Semantic equality is when two expressions represent the same mathematical object, for example, in

It is known that no algorithm can exist that decides if two expressions representing numbers are semantically equal, if exponents and logarithms are allowed in the expressions. Therefore, (semantic) equality can only be verified on certain classes of expressions, such as polynomials and rational fractions.

To verify the equality of two expressions, instead, to construct a specific algorithm, usually put them in some canonical form or decompose them in normal form and check the syntactic equality of the result.

This seems to be the best practice.

Answer 3

I tried to write basically the same question when I ended up here. However, I found some ideas that are not mentioned here. Firstly, I agree with @nelshh that in some specific cases you can find canonical forms that allow you to check the equality of expressions.

I found some examples of canonical forms:

• The most famous is probably the minterm canonical form in Boolean algebra, which is used, for example, in the synthesis or verification of a circuit.
• Polynomial expressions also admit canonical form as the sum of monomials. This may solve your examples:
• The canonical form for rational numbers is an irreplaceable share .

Your examples:

• Both are already in canonical form, you just need to sort them in increasing order.
• 2*x is in its canonical form, x+x not (since both operands of addition have the same degree).
• Both are already in canonical form (monomials of degree -1), except that the coefficient is 4/(x/2) , which 4/(1/2) not in canonical forms for rational numbers.

If you are still interested in this, I would suggest that you experiment with a computer algebra system such as sympy for python (it probably also exists for java). However, I also believe that you should remove the java and floating-point tags (this has nothing to do with how the computer stores real numbers) and add the computer-science tag.

For example, sympy might say things like this:

 >>> Rational(3,4)*(x+y)**2 2 3⋅(x + y) ────────── 4 >>> Rational(3,4)*(x**2+y**2)+Rational(1,4)*2*x*y+Rational(4,8)*2*x*y 2 2 3⋅x 3⋅x⋅y 3⋅y ──── + ───── + ──── 4 2 4 >>> expand(Rational(3,4)*(x+y)**2)==expand(Rational(3,4)*(x**2+y**2)+Rational(1,4)*2*x*y+Rational(4,8)*2*x*y) True