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
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")