views:

2270

answers:

10

I need to solve a few mathematical equations in my application. Here's a typical example of such an equation:

a + b * c - d / e = a

Additional rules:

  • b % 10 = 0
  • b >= 0
  • b <= 100
  • Each number must be integer
  • ...

I would like to get the possible solution sets for a, b, c, d and e.

Are there any libraries out there, either open source or commercial, which I can use to solve such an equation? If yes, what kind of result do they provide?

A: 

Pretty sure Numerical Recipes will have something

Simon
+1  A: 

You want a computer algebra system.

See http://stackoverflow.com/questions/160911/symbolic-math-lib, the answers to which are mostly as relevant to c++ as to c.

dmckee
A: 

You're looking for a computer algebra system, and that's not a trivial thing.

Lot's of them are available, though, try this list at Wikipedia:

http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

Adam Davis
A: 

This looks like linear programming. Does this list help?

andreas buykx
this looks almost nothing like linear programming.
David Nehme
A: 

In addition to the other posts. Your constraint sets make this reminiscent of an integer programming problem, so you might want to check that kind of thing out as well. Perhaps your problem can be (re-)stated as one.

You must know, however that the integer programming problems tends to be one of the harder computational problems so you might end up using many clock cycles to crack it.

jlouis
+2  A: 

You're venturing into the world of numerical analysis, and here be dragons. Seemingly small differences in specification can make a huge difference in what is the right approach.

I hesitate to make specific suggestions without a fairly precise description of the problem domain. It sounds superficiall like you are solving constrained linear problems that are simple enough that there are a lot of ways to do it but "..." could be a problem.

A good resource for general solvers etc. would be GAMS. Much of the software there may be a bit heavy weight for what you are asking.

simon
+1  A: 

I know it is not your real question, but you can simplify the given equation to:

d = b * c * e with e != 0

quinmars
That doesn't work for d=0, b=1, c=1. The best I came up with is b * c = d / e
dummy
Argh, just ignore this.
dummy
+3  A: 

Solving linear systems can generally be solved using linear programming. I'd recommend taking a look at Boost uBLAS for starters - it has a simple triangular solver. Then you might checkout libraries targeting more domain specific approaches, perhaps QSopt.

ceretullis
A: 

Looking only at the "additional rules" part it does look like linear programming, in which case LINDO or a similar program implementing the simplex algorithm should be fine.

However, if the first equation is really typical it shows yours is NOT a linear algebra problem - no 2 variables multiplying or dividing each other should appear on a linear equation!

So I'd say you definitely need either a computer algebra system or solve the problem using a genetic algorithm.

Since you have restrictions similar to those found in linear programming though you're not quite there, if you just want a solution to your specific problem I'd say pick up any of the libraries mentioned at the end of Wikipedia's article on genetic algorithms and develop an app to give you the result. If you want a more generalist approach, then you've got to simulate algebraic manipulations on your computer, no other way around.

Joe Pineda
A: 

The TI-89 Calculator has a 'solver' application. It was built to solve problems like the one in your example. I know its not a library. But there are several TI-89 emulators out there.

Jason