Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

LinaInverse2010

Math parser

This topic is 5667 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does anyone know where I can get code to parse a mathmatical polynomial like this: A*x^2 + B*y^2 + C*z^2 + D*x*y + E*y*z + F*x*z + G*x + H*y + I*z + J = 0 where: x = x0 + dx*t y = y0 + dx*t z = z0 + dx*t and give me an answer in the form of: C2*t^2 + C1*t + C0 = 0 Off course how I would enter the data doesn''t matter, I just want it to somehow give me C2, C1, C0 with given values for everything else. LinaInverse2010

Share this post


Link to post
Share on other sites
Advertisement
What do you want to do exactly?
Do you want to parse the string "A*x^2 + ... + J = 0"?
The string "A*x^2 + ... + J = 0 where: x = x0 + dx*t y = y0 + dx*t z = z0 + dx*t"?
Or do you just need a function like GetC012FromABCDEFGHIJ(someA,SomeB,...,SomeJ)

That last one shouldn''t be to hard, assuming the equation is static (i.e. only has an x, y and z):
A*x^2 + B*y^2 + C*z^2 + D*x*y + E*y*z + F*x*z + G*x + H*y + I*z + J = 0
=A*x0*dx*x0*dx * t^2
+B*y0*dy*y0*yx * t^2
+C*z0*dz*z0*zx * t^2
+D*x0*dx*y0*yx * t^2
+E*y0*dy*z0*zx * t^2
+F*x0*dx*z0*zx * t^2
+G*x0*dx * t
+H*y0*dy * t
+U*z0*dz * t
+J
=C2*t^2 + C1*t + C0,
C2 = A*x0*dx*x0*dx + B*y0*dy*y0*yx + C*z0*dz*z0*zx + D*x0*dx*y0*yx + E*y0*dy*z0*zx + F*x0*dx*z0*zx
C1 = G*x0*dx + H*y0*dy + U*z0*dz
C0 = J

Share this post


Link to post
Share on other sites
I want it to be able to parse an n-degree polynomial. The 2-nd degree I gave was just an example.

I''m going to use the coefficients given back to find the roots of the n-degree polynomial. This is for intersecting a ray with an nth degree polynomial. How I enter the polynomial is irrelevant to me.

LinaInverse2010

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A single variable polynomial of degree n can be represented by a single vector of size n. The vector {p0, p1, p2, ..., pn} could then represent the polynomial P(x) = p0 + p1*x + p2*x^2 + ... pn*x^n. Multiplying a polynomial P(x) with a constant c would give c * P(x) = {c*p0, c*p1, c*p2, ...}, adding two polynomials P(x) + Q(x) = {p0+q0, p1+q1, p2+q2, ...}, and multiplying two polynomials R(x) = P(x) * Q(x) would look something like this:


R = {0, 0, 0, ..., 0} (degree R = degree P + degree Q)
for j = 0 to degree P
for k = 0 to degree Q
R[j+k] += P[j] * Q[k]


Now all you have to do is to read the original polynomial one term at a time, substituting each x, y and z with the polynomials {x0, dx}, {y0, dy}, {z0, dz} respectively, and multiply them together with the coefficient. To make parsing simple, each term could be represented by four numbers, the coefficient and the multiplicities of x, y, and z. Thus, the string "5 4 3 2" would mean 5*x^4*y^3*z^2.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Should be: "A single variable polynomial of degree n can be represented by a single vector of size n+1."

Share this post


Link to post
Share on other sites
There is a symbolic math package for python so you could embed python and use that package.

Otherwise you are going to have to use an expression tree. I could get long winded explaining it, but I''ll try to keep this short. An expression tree is a tree of operators. The children of an operator is it''s operands and may be expressions themselves. There are no parentheses because precedence is implied by the position in the tree, i.e. the children are evaluated by the root.

Here you have a simple tree. f*g*h where f=A+B*x+C*x^2 using a second degree of three variables as an example. x in turn is also an expression. The expression at each stage is simple to parse and build although it doesn''t sound like you actually need to parse. You could use the vector suggestion with a simple loop to build the expression tree. So you build each expression tree with empty variable pools.

You then build from the bottom up. t is undefined so there is no reason to do substitution on the x, y and z expressions. You just place x in the variable pool to build f, y for g and z for h. The result of evaluation of those expressions with those variables goes into the variable pool for the top expression, i.e. f*g*h. When you evaluate that expression with those in the variable pool you get an expression tree representing what you would get if you did the substitutions by hand. Not simplified by any means.

First you have to expand it out and then you collect terms. Expansion is simple. You replace a product of sums with a sum of products. Sounds simple and is simple. Somewhere in your tree you have a product where at least one of the children is a sum. All you deal with at any single instance is (A+B)*(C+D). You simply covert that to A*C+A*D+B*C+B*D. A, B, C and D may well be expressions, but you just proceed down the tree after performing the substituion. If they are expressions of the correct form they will be substituted in turn.

Now you rotate your variable right. So say you had (A+B*t)*(C+D*t) which became A*C + A*D*t + B*t*C + B*t*D*t so you make it A*C + A*D*t + B*C*t + B*D*t*t. Now A*C, A*D, B*C and B*D are all constants so replace those expressions with their values. t*t=t^2 so you make that substitution as well. All you have at this point is a sum of products of some constant and some power of t. So you rotate again by the power of t. Now way down at the bottom right most position you have A*t^B+C*t^D. If B=D then that can be replaced by (A+C)*t^B. Replace A+C by its value, back out one level and do it all again. Eventually B!=D. So now you are checking the left subtree of the right subtree against the left subtree. You end up with basically a linked list. The left side of the tree is some coefficent and power of t and the right hand side is the higher order terms. You can convert that into a vector where the position in the vector is the power and the value at that position is the coefficent.

You could also just evaluate that expression tree with some value of t in the variable pool. I assume you actually need the coefficents for some reason other than to evaluate the polynomial. If all you need is to evaluate the polynomial then skip the entire simplification. If you stick f, g, h, x, y, z and t into the variable pool you can just evaluate f*g*h. For that matter you can just make the coefficents variables and life gets a whole lot easier.

Overall stick the expression tree in a tree view as you are doing it. It is complex only in everything that is going on and not in any individual thing you are doing. When you can see what is going on there is less to track in your head.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!