Sign in to follow this  
morello

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
morello    100
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.

Share this post


Link to post
Share on other sites
nullsquared    126
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

Share this post


Link to post
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."

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this