Equation solver

[hamsterman]

I made a little program to solve simple equations.

Code + compiled exe: http://www.mediafire.com/file/rwnmxp4zks2rgob/eqman.zip
http://www.mediafire.com/file/adpvqujpeu2d9x5/eqman.zip (update)

Code for the paranoid:
* polynomial.h: http://pastebin.com/HhCmW3Bn(removed)
* polynomial.cpp: http://pastebin.com/MF8tJj1m(removed)
* maths.h: http://pastebin.com/4USb8u3g
* maths.h: http://pastebin.com/2sScQDN6 (update)
* maths.cpp: http://pastebin.com/rDN4rt4t
* maths.cpp: http://pastebin.com/sFxQNi4C (update)
* op.cpp: http://pastebin.com/btfihG0m
* main.cpp: http://pastebin.com/C0BRvaiL

I even added some comments! Though in general the code could be better..

Enter an equation to get a list of its roots. Enter "quit" to quit.
Sample inputs could be "xxx - 1" or "x+1=2x-7"

There are sometimes mistakes due to FPU imprecision. Haven't noticed any others yet.

I'd appreciate any comments, suggestions and info about bugs.

[Seraphimsan]

QUICK post 3 more time D:

also well done, i've been working on the same for quite some time. Though I'm working with one that is to be used on a graphing calculator :3

[sohguanh]

Actually I was thinking what kind of business application require "heavy" maths operations like equation solving etc etc ? Can you list some examples ?

Most of the time, I am involved more on the business-centric aspect of software application and using maths equations are still not part of the requirements I have handled yet.

[4Gb4jE8b]

Aeronautic engineers (though I'd believe most engineers would in some way or another) and certain types of physicists are two that come to mind. Though I just use a calculator for my needs concerning this type of equation solving. Still, it would be a useful program to have if you can't find your calculator or are working specifically on the computer. So props to you OP.

[rapidcoder]

Any simulation software. Computer games with realistic physics (not only flight simulators). Crazy games like World Of Goo.

There are sometimes mistakes due to FPU imprecision.

FPU is imprecise by definition. If your algorithm doesn't control the level of round-off errors, than it is useless for any serious engineering application (but when coding for fun it is perfectly ok to ignore this problem).

[hamsterman]

sohguanh, apart form the actual solving algorithm (Durand–Kerner method) there is hardly any maths there at all. It's a problem of logic.

headlessgargoyle, can you find the complex roots of a 5'th degree polynomial with a calculator? I wish I had a calculator like that..

rapidcoder, yes, I understand that. It's a problem simple to fix. It's that if I have (x+2)(x+1)/(x+3)(x+1) one root of (x+2)(x+1) may be -1+epsilon and a root of (x+3)(x+1) may be -1-epsilon. So to check if -1-epsilon == -1+epsilon I need to use another, larger Epsilon. I wonder if it would be faster to check the roots of (x+2)(x+1) in polynomial (x+3)(x+1) to see if none return 0, than to solve (x+3)(x+1)..

[hamsterman]

A little update.
Removed that silly Polynomial class, fixed the mistakes of comparing floats (I think..)
Also, I now assume that a Base::simplify will fix the whole thing in one go.

[hamsterman]

I was thinking of how could I make it solve more complex equations (with logarithms, exponents and trigonometry). The problem is that I myself don't know how to solve some equations. Like ln(x)=x, for example. (A quick google search came up with someone saying this can't be solved, only approximated. Is that so?) Do you think it would make sense to expand ln to (several elements of) it's power series and then solve it as a normal polynomial? How do you think, how does wolfram alpha do this?

[Browni3141]

hamsterman said

headlessgargoyle, can you find the complex roots of a 5'th degree polynomial with a calculator? I wish I had a calculator like that..

It's impossible to write a formula to get the exact roots of a 5th degree polynomial using radicals. It can be done, however for degrees less than five.

Like ln(x)=x, for example. (A quick google search came up with someone saying this can't be solved, only approximated. Is that so?)

e^ln(x) = e^x
x = e^x
0 = e^x -x
I don't know if you can go anywhere from here except using Newton's Method as an approximation.
Nevermind, the equation has no real roots. I'm not sure how to even approximate complex roots for this.

Edit: Agh, the strikethrough didn't work. Just ignore the Newton's Method stuff.

[rapidcoder]

It's impossible to write a formula to get the exact roots of a 5th degree polynomial using radicals

It is impossible to write a formula working for ANY possible 5th degree polynomials. However, this doesn't mean you cannot find symbolically exact roots of SOME 5th degree polynomials.

I'm not sure how to even approximate complex roots for this.

Just use the Newton's method. Works the same for complex numbers.
For polynomials it is advisable to work in the complex domain, because then you know how many roots you have to find.

[Null]

I have two suggestions:
1. Check the user input. If the input is invalid, it allocates >800 MB of memory and still tries to solve it.
2. Code portability. gcc doesn't accept this:

struct Base{
	virtual enum Type{ number, x, mono, poly } type() = 0; // error when compiling with gcc
        // ..
};

To make it work I had to move the enum definition outside the function definition

struct Base{
    enum Type{ number, x, mono, poly };
    virtual Type type() = 0;
  // ..
};

I'm not sure whether it's gcc's fault or your code uses some kind of compiler extension.

[hamsterman]

1. Apie ką tu?
2. umm. keista. (aš naudoju VC++)

beje, ar enum E{A, B, C} e; irgi meta errora? Tai legalu su klasėm, tai logiška būtų ir kad enumeracijoms leistų.. Gal problemos dėl to 'virtual' kyla..

[Null]

1. Jei įvedu ką nors ne taip ar šiaip kokią nesąmonę (pvz. "hgjghj") tada tavo programa pradeda naudoti labai daug atminties.
edit:

beje, ar enum E{A, B, C} e; irgi meta errora?

Ne. Beje, pamėgink sukompiliuoti

class C
{
enum E{A, B, C} e; // ok

// this is not a valid in C++, right?
enum B{ X,Y,Z} e(); // error: new types may not be defined in a return type

};

[hamsterman]

a. nu jo. Aš nesu labai entuziastingas apie error handlinimo kodo rašymą.. (tinginys)
Bet kodėl ta programa vis tiek turėtų bandyti išspręsti tą nesąmonę?

[Null]

Bet kodėl ta programa vis tiek turėtų bandyti išspręsti tą nesąmonę?

Žinau kad ji ne nesąmonėms skirta, bet ir netyčia galima kažką neteisingai įvest.. Bet nekreipk į tai dėmesio dėmesio (be reikalo užvedžiau ant šitos temos)

[hamsterman]

Ne. Beje, pamėgink sukompiliuoti <...>

veikia (išskyrus akivaizdžias klaidas).
oh well..

[tition]

A note on the compiled .exe:
it doesn't run under linux, because it has a dependency on some Microsoft run-time dll, namely:

MSVCP90.dll

Since possibly all people on this forum have this .dll installed, nobody has seen this dependency problem so far. Your program will highly likely fail to run on *another Windows machine* if it does not have the microsoft development .dll's installed.

I had a similar problem when I started doing stuff with Visual studio. In order to fix it you need to set up your compiler (are you using the Microsoft visual studio?) to statically link your .exe. To do that you need to look at the linker options, and choose the option to statically compile (the default option was "Multithreaded debug dll" or something similar: instead, you need "Multithreaded debug static" or something similar).

[Edit:] @ rapidcoder:

It is impossible to write a formula working for ANY possible 5th degree polynomials. However, this doesn't mean you cannot find symbolically exact roots of SOME 5th degree polynomials.

Argh, the english word "ANY" always creates troubles... This is not a clean mathematical statement mate... (but I get your point: there is no solution in radicals for the roots of a generic 5^th degree polynomial).

[rapidcoder]

Argh, the english word "ANY" always creates troubles...

Right, I should have written "ALL".

[hamsterman]

Thanks tition, I'll take a look at those options.