How to simplify and code this? (math-related too)
Author
Hi,
Assuming this equation (and solution, sorry don't know how to put link or image here):
http://img94.imageshack.us/img94/1656/finalsp.png
I can code the equation part, but assuming I do not know X yet, and would like to simplify it (which, in the image, goes to 6x(squared)-11x+6 )
How does one go about it getting coefficient '6' as well as '-11' and '+6' coming from the original equation?
I googled and saw some guys programmed this:
http://www.algebra-test.com/algebra-help/3x3-system-of-equations/polynomial-calculator-c-source.html
How does one program simplification of polynomials?
Much help appreciated. thanks!
You might want to start by looking at http://en.wikipedia.org/wiki/Computer_algebra_system and http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems
Some of those implementations are open source, so you can look at how they work.
Some of those implementations are open source, so you can look at how they work.
Well there's no x on the denominator so all the program needs to do is divide each part by it's denominator and group terms. You could use floating point precision and hope for the best, but a proper equation solver will be storing exact representations of the values, so you'll need a library designed to do just that.
Author
@taz0010 - hi, i don't think I could program it to divide since i do not know x yet, how would one go about it?
for example, i can just type the whole equation into something like:
which would work well and fine, but how do i make another function that would take that equation, and transform it into: (6x[squared] - 11x + 6)?
basically:
-> how does one program it to get the degree of polynomial
-> get the coefficient (in this case, the 6, 11, and the other 6)
much help appreciated.
for example, i can just type the whole equation into something like:
void myFunction(x) { myVariableY = 1*(((x-2)/(1-2))*((x-3)/(1-3))) + 8*(((x-1)/(2-1))*((x-3)/(2-3))) + 27*(((x-1)/(3-1))*((x-2)/(3-2)));}which would work well and fine, but how do i make another function that would take that equation, and transform it into: (6x[squared] - 11x + 6)?
basically:
-> how does one program it to get the degree of polynomial
-> get the coefficient (in this case, the 6, 11, and the other 6)
much help appreciated.
It's not easy. You need to be able to represent equations symbolically. This usually means a tree-like structure, much the same way that a compiler would represent (x-1)*(x-4) when you type it into your source code file. If you don't have to worry about parsing textual representations of input then this becomes a little easier.
x-4 would be represented as:
(x+4)/(x-2) would be represented as:
Once you have things in this format, it's still a difficult problem but it becomes quite a bit easier to work with. What you do is look for various types of patterns that you know lead to simplifications. For example, if you have any node of type node::expr, and the left and right are both of type node::constant, you look at the operation, perform it on the left and right to end up with one number, delete the expr node from the tree, and replace it with a new node of type node::constant with the updated value. This would deal with situations like the (1 - 2) in the denominator of your picture.
There are plenty of simple simplifications you can do like this. If you see a node that looks like { type=expr, op=mult, left=constant(1), right=<anything> } you can delete the entire node and replace it with 'right'. Likewise if right=constant(1) and op=mult, or right=constant(1) and op=div. If either of the two nodes are 0 and op=mult you can delete the node and replace the entire thing with constant(0), and similarly if left=constant(0) and op=div you can also replace the node with constant(0).
Keep doing this over and over until all the basic simplifications have been exhausted and you can't find anything left to do. Then look for more complicated simplifications. For example, pow(var(), <x>) <op> pow(var(), <y>) op can be replaced if x == y and <op> is + or -. It can also be simplified if <op> is *, / or ^ but the logic becomes more compliacted.
Anyway I'm just trying to give you a basic idea. You probably shouldn't even use the struct I mentioned above because it's extremely crude. In a production quality system you would want a more robust / efficient tree AST implementation.
With a correct implementation you can even define overloaded operators on your node struct. This way you can actually write things like:
((x+4)*(x-2))^2 and it will build up an expression tree for you.
[Edited by - cache_hit on February 23, 2010 12:37:39 PM]
struct node{ typedef enum { plus, minus, div, times, power } op; typedef enum { expr, constant, var } type; node(type t, op o, node* left, node* right) : type_(t), op_(o), left_(left), right_(right) { } node(int value) : type_(constant), value_(value), left_(null), right_(null) { } node() : type_(var), left_(null), right_(null) { } op op_; type type_; int value_; node* left_; node* right_;};x-4 would be represented as:
node(node::expr, node::minus, new node(), //empty constructor is a variable new node(4)); //integer constructor is a constant(x+4)/(x-2) would be represented as:
node(node::expr, node::div, new node(node::expr, node::plus, new node(), new node(4)), new node(node::expr, node::minus, new node(), new node(2)));Once you have things in this format, it's still a difficult problem but it becomes quite a bit easier to work with. What you do is look for various types of patterns that you know lead to simplifications. For example, if you have any node of type node::expr, and the left and right are both of type node::constant, you look at the operation, perform it on the left and right to end up with one number, delete the expr node from the tree, and replace it with a new node of type node::constant with the updated value. This would deal with situations like the (1 - 2) in the denominator of your picture.
There are plenty of simple simplifications you can do like this. If you see a node that looks like { type=expr, op=mult, left=constant(1), right=<anything> } you can delete the entire node and replace it with 'right'. Likewise if right=constant(1) and op=mult, or right=constant(1) and op=div. If either of the two nodes are 0 and op=mult you can delete the node and replace the entire thing with constant(0), and similarly if left=constant(0) and op=div you can also replace the node with constant(0).
Keep doing this over and over until all the basic simplifications have been exhausted and you can't find anything left to do. Then look for more complicated simplifications. For example, pow(var(), <x>) <op> pow(var(), <y>) op can be replaced if x == y and <op> is + or -. It can also be simplified if <op> is *, / or ^ but the logic becomes more compliacted.
Anyway I'm just trying to give you a basic idea. You probably shouldn't even use the struct I mentioned above because it's extremely crude. In a production quality system you would want a more robust / efficient tree AST implementation.
With a correct implementation you can even define overloaded operators on your node struct. This way you can actually write things like:
((x+4)*(x-2))^2 and it will build up an expression tree for you.
[Edited by - cache_hit on February 23, 2010 12:37:39 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
