Equations Equality test (in C++ or with Unix tools) (algebra functions isomorphism)

Question

I am looking for C++ open-source library (or just open-source Unix tool) to do: Equality test on Equations .

Equations can be build during runtime as AST Trees, string or other format.

Equations will mostly be simple algebra ones, with some assumptions about unknown functions. Domain, will be integer arithmetic (no floating point issues, as related issues are well known - Thanks @hardmath for stressing it out, I've assumed it's known).

Example: Input might contain function phi, with assumptions about it (most cases) phi(x,y)=phi(y,x) and try to solve :

equality_test( phi( (a+1)*(a+1) , a+b ) = phi( b+a, a*a + 2a + 1 )

It can be fuzzy or any equality test - what I mean is that, it does not have to always succeed (It may return "false" even if equations are equal).

If there would be problem with supporting assumptions like above about phi function, I can handle this, so just simple linear algebra equations equality testers are welcome as well.

• Could you recommend some C/C++ programming libraries or Unix tools ? (open-source)
• If possible, could you attach some example how such equality test, might look like in given library/tool ?

P.S. If such equality_test could (in case of success) return isomorphism - (what I mean, a kind of "mapping") - between two given equations, would be highly welcome. But tools without such capabilities are highly welcome as well.

P.S. By "fuzzy tester" I mean that in internals equation solver will be "fuzzy" in terms of looking for "isomorphism" of two functions, not in terms of testing against random inputs - I could implement this, for sure, but I try to find something with better precision.

P.P.S. There is another issue, why I need better performance solution, than brute-force "all inputs testing". Above equation is simplyfied form of my internal problem, where I do not have mapping between variables in equations. That is, I have eq1=phi( (a+1)*(a+1) , a+b ) and eq2=phi( l+k, k*k + 2k + 1 ) , and I have to find out that a==k and b==l. But this sub-problem I can handle with "brute-force" approach (even asymptotic complexity of this approach), case there is just a few variables, let it be 8. So I would need to do this equation_test for each possible mapping. If there is a tool that that whole job, I would be highly thankful, and could contribute to such project. But I don't require such functionality, simply equation_test() will be enough, I can handle rest easily.

To sum it up:

• equality_test() is only one of many subproblems I have to solve, so computational complexity matters.
• it does not have to be 100% reliable, but higher likelihood, than just testing equations with a few random inputs and variable mapping is highly welcome :).
• output of "yes" or "no" (all additional information might be useful but in future, at this stage I need "Yes"/"No")

Answer 1

Your topic is one of automated theorem proving, for which a number of free/open source software packages have been developed. Many of these are meant for proof verification, but what you ask for is proof searching.

Dealing with the abstract topic of equations would be the theories mathematicians call varieties. These theories have nice properties with respect to the existence and regularity of their models.

It is possible you have in mind equations that deal specifically with real numbers or other system, which would add some axioms to the theory in which a proof is sought.

If in principle an algorithm exists to determine whether or not a logical statement can be proven in a theory, that theory is called decidable. For example, the theory of real closed fields is decidable, as Tarski showed in 1951. However a practical implementation of such an algorithm is lacking and perhaps impossible.

Here are a few open source packages that might be worth learning something about to guide your design and development:

Tac: A generic and adaptable interactive theorem prover

Prover9: An automated theorem prover for first-order and equational logic

E(quational) Theorem Prover

Answer 2

I am not sure for any library but how about you do it yourself by generating a random set of inputs for your equation and substituting it in both equations which have to be compared. This would give you a almost correct result given you generate considerable amount of random data.

Edit: Also you can try http://www.wolframalpha.com/

with

 (x+1)*(y+1) equals x+y+xy+2

and

 (x+1)*(y+1) equals x+y+xy+1

Answer 3

I think you can get pretty far with using Reverse Polish Notation.

1. Write out your equation using RPN

2. Apply transformations to bring all expressions to the same form, e.g. *A+BC --> +*AB*AC (which is the RPN equivalent of A*(B+C) --> A*B+A*C), ^*BCA --> *^BA^CA (i.e. (B*C)^A --> B^A * C^A)

3. "Sort" the arguments of symmetric binary operator so that "lighter" operations appear on one side (e.g. A*B + C --> C + A*B)

4. You will have problem with dummy variables, for example sum indices. There is no other way, I think, but to try every combination of matching them on both sides of the equation.

In general, the problem is very complicated.

You can try a hack, though: use an optimizing compiler (C,Fortran) and compile both sides of the equation to optimized machine code and compare the outputs. It may work, or may not.

Answer 4

Opensource (GPL) project Maxima has tool simmilar to Wolfram Alpha's equals tool :

(a+b+c)+(x+y)**2 equals (x**2+b+c+a+2*x*y+y**2)

Which is is(equal()), that solves formulas :

(%i1) is(equal( (a+b+c)+(x+y)**2 , (x**2+b+c+a+2*x*y+y**2) ));
(%o1)                                true

For this purpose, it uses rational simplifier - ratsimp, in order to simplify the difference of two equations. When difference of two equations is simplified to zero, we know they are equal for all possible values:

(%i2) ratsimp( ((a+b+c)+(x+y)**2) - ((x**2+b+c+a+2*x*y+y**2)) );
(%o2)                                  0

This answer, just shows direction (like other answers). If you know about something similar, that can be used as a part of C++ Unix program - programming library ? Good C/C++ binding similar tool to this. Please, post new answer.