polynomial solution needed (3rd & 4th order)
Author
I need to write functions to solve 3rd and 4th order polynomials. The function proto types are as follows...
struct POLYRESULT3{
double Result[3];
bool Real[3];
};
struct POLYRESULT4{
double Result[4];
bool Real[4];
};
POLYRESULT3 SolveForT(double A,double B,double C,double D);
// solve At^3 + Bt^2 + Ct + D = 0
POLYRESULT4 SolveForT(double A,double B,double C,double D,double E);
// solve At^4 + Bt^3 + Ct^2 + Dt + E = 0
My problem with writing these two functions is that I don''t know how to solve these types of equations and haven''t been able to find any examples/tutorials anywhere.
Any help would be appreciated.
you may use Ruffini''s rule ( as we call in italy ) but this may yelds to complex solutions if you look in a algebra book you''ll find how to solve this equations
Well, perhaps you can write a trial''n''error based search algorithm. You can end it once it yields an answer to the correct precision.
Author
quote:Original post by CorsairK8
Well, perhaps you can write a trial''n''error based search algorithm. You can end it once it yields an answer to the correct precision.
Tried it, The problem is that it took about 10 min to get the answers for one problem. My program has to be able to solve the problem millions of times in a reasonable amount of time.
quote:Original post by narfidoo
http://mathforum.com/dr.math/faq/faq.cubic.equations.html
Thanks, that was very interesting. I still don''t understand how to solve the problems but that page has enough info for me to study that it''ll take me a while to go through it all.
Hi,
A little while ago I wrote a fairly fast polynomial solver. It only works with polynomials containing only positive integer powers of x, but it looks like that''s what you want. It just uses Newton-Raphson method. This means you can modify the accuracy at the expense of some speed. I used it while messing around with the collision detection code in the NeHe tutorial No. 31 (by Dimitrios Christopoulos) so I''m fairly confident that it will never fail to solve the equation. You should be able to optimise it further if you need to.
Only problem is that I never got round to wrapping it up in a simple method, it''s fairly integrated into my collision detection code at the moment. I''ll try and strip it out and post it later tonight if I can.
A little while ago I wrote a fairly fast polynomial solver. It only works with polynomials containing only positive integer powers of x, but it looks like that''s what you want. It just uses Newton-Raphson method. This means you can modify the accuracy at the expense of some speed. I used it while messing around with the collision detection code in the NeHe tutorial No. 31 (by Dimitrios Christopoulos) so I''m fairly confident that it will never fail to solve the equation. You should be able to optimise it further if you need to.
Only problem is that I never got round to wrapping it up in a simple method, it''s fairly integrated into my collision detection code at the moment. I''ll try and strip it out and post it later tonight if I can.
Ok, i''ve wrapped my polynomial solver up into a class. It seems to work (minimal testing ''cause it took longer than I expected). I won''t post it yet because a) I haven''t finished commenting it properly and b) it''s fairly big! If you want it, post back and I''ll e-mail it to you. Speedwise, a quick test shows it should be able to solve about 750,000 quartic equations per minute on a 933MHz Pentium III. I probably still have some error checking to do, but that shouldn''t bring the speed down drastically.
Author
quote:Original post by Enigma
Ok, i''ve wrapped my polynomial solver up into a class. It seems to work (minimal testing ''cause it took longer than I expected). I won''t post it yet because a) I haven''t finished commenting it properly and b) it''s fairly big! If you want it, post back and I''ll e-mail it to you. Speedwise, a quick test shows it should be able to solve about 750,000 quartic equations per minute on a 933MHz Pentium III. I probably still have some error checking to do, but that shouldn''t bring the speed down drastically.
That would be fast enough for a begining. I could research a faster way while I use that. my e-mail is avian@prairie.lakes.com
Look at the first gem in "Graphics Gems V", "Solving Quartics and Cubics for graphics" It covers this in a lot of detail, with calculation steps that would be easy to turn into code and duscussions of the many issues of doing this.
If I recall my college calculas, there is no formula that will always provide the right answer to those equations. Now I havn''t had a chance to look into this in depth, and that may have just been the professors and books way of putting off till later what they were too lazy to explain right now, but I remember a few examples of attempted formulas. Most of them worked most of the time, but there would always be some trivial example (ie E = sqrt[-1] ) that would cause it to fail.
Okay, so that example isn''t trivial, but I was trying to make a point. I don''t have my calc book next to me right now anyways.
Okay, so that example isn''t trivial, but I was trying to make a point. I don''t have my calc book next to me right now anyways.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
