Algebra simplification
Author
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).
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*
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.
For really simple setups that only involve a single power of y.
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]
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 treeSo, 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]
Author
Quote:Original post by nullsquared
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.
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.
Quote:Original post by morello
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.
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
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."
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement