# Algebra simplification

## Recommended Posts

morello    100
Slightly OT, but I am hoping someone here might know of some resources. I need to write something to rearrange algebraic equations automatically, ie to convert f(x, y) = g(x, y) into y = g(x) for example, given x/(y+1) = 3, produce y = x/3 - 1 I realise there is no general solution to this. I only need to handle quite basic stuff at the moment. But I would like an extensible solution. I think I probably need a production rule system for this. Does anyone know of anywhere I might find some examples to get me started, particularly - implementing production rules in Java - what the rules might be (I already have an expression parser, so the expressions exist in my code as a tree structure).

##### Share on other sites
Wow... I'm trying to decide whether this is AI or if I should move it to the math and physics forum. I suppose a general solver would be AI but the math guys might already know how to do this. *shrug*

##### Share on other sites
nullsquared    126
Hey, I can't really be of much help here, but this topic is very interesting because I'm working on a graphing calculator. What do you plan on doing with this rearranging? And what happens if you're given something like y^2=x or sin(y)=x which doesn't have a single solution? Also, look into computer algebra systems, there are many out there that are open source and do this sort of thing.

##### Share on other sites
KulSeran    3267
For really simple setups that only involve a single power of y.
Take your tree, split at the =Take the left side of the =, push the entire subtree under the left side of a "subtract" node. Put everything on the right of the equals under the right of the "subtract" node.Make the right side of the = contain only the node "0"Reduce the left subtree.let L be the node left of the =let R be the node right of the =while node L is not "y"  If only L->left contains Y then     create a new node N with the inverse operation of L     set N->right to L->right     set N->left to R     set R to N     set L to L->left  Else If only L->right contains "y" then     if L is communitive        swap L->right and L->left        continue loop     else       create a new node N with the inverse operation of L       set N->right to L->right       set N->left to R       set R to N       set L to L->left       swap L and R  else L->right and L->left contain "y" then     If L is reduceable, reduce it and try again. Else fail.    reduce tree

So, given your example, x/(y+1) = 3
you'd get
x/(y+1) - 3 = 0
x/(y+1) = 0 + 3
(0+3) * (y+1) = x
(y+1) * (0+3) = x
(y+1) = x / (0+3)
y = x / (0 + 3) + 1
y = x / 3 + 1

The hard part is the reduce. Unfortunately I don't know off the top of my head how to simply put that into steps. But without that step, you could end up with 1/(5*y) + 2/(3*y) that is better represented as 13/15 * 1/y. And without that, the simple steps above won't ever find a solution, since "y" will be on both the left and right of a tree node.

As nullsquared noted, the "inverse operation" node may have to be special in noting that it was created instead of part of the base problem.
Since you can have "y = 3^(1/2)" but "y^2 = 3" should yield "y = (+/-)(3^(1/2))".

[Edited by - KulSeran on April 28, 2010 8:10:45 PM]

##### Share on other sites
morello    100
Quote:
 Original post by nullsquaredHey, I can't really be of much help here, but this topic is very interesting because I'm working on a graphing calculator. What do you plan on doing with this rearranging? And what happens if you're given something like y^2=x or sin(y)=x which doesn't have a single solution? Also, look into computer algebra systems, there are many out there that are open source and do this sort of thing.

I am creating an educational tool which has some elements of a graphing calculator.

I have considered the types of problem you mention. For the y^2=x case, I think you need to plot both +ve and -ve root cases. Especially if you want to do nice things like x^2 + y^2 = 1 to draw a circle.

For x = sin(y) probably the easiest thing is to plot x against y, if your system allows it. I am sure there are lots of other more nasty cases I haven't considered yet. But I am not trying to

I will certainly look into open source CAS. The problem I have sometimes found with Java open source libraries is that they often have a lot of dependencies on other Java open source libraries, and you end up having to ship 50MB of Apache jars with your product.

Still, if anyone is aware of a simple CAS library which isn't too bloated, please post it.

##### Share on other sites
nullsquared    126
Quote:
 Original post by morelloI have considered the types of problem you mention. For the y^2=x case, I think you need to plot both +ve and -ve root cases. Especially if you want to do nice things like x^2 + y^2 = 1 to draw a circle.For x = sin(y) probably the easiest thing is to plot x against y, if your system allows it. I am sure there are lots of other more nasty cases I haven't considered yet.

Indeed, but when you get something like sin(x*y)=0 things get complicated. I am not solving anything analytically so none of these are an issue for me, but I just wanted to point them out since you want to solve for y analytically.

Quote:
 I will certainly look into open source CAS. The problem I have sometimes found with Java open source libraries is that they often have a lot of dependencies on other Java open source libraries, and you end up having to ship 50MB of Apache jars with your product.Still, if anyone is aware of a simple CAS library which isn't too bloated, please post it.

I don't have personal experience with any, but there is large comparison of many CAS here: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

##### Share on other sites
lmelior    325
A lot of those on Wikipedia seem to use Lisp and are quite old, so you might prefer checking out something newer like SymPy. You might also have some luck searching for "simple computer algebra system."