Solving an equation for different variables

[daviddoria]

Hi all,

I am trying to write a function to solve an equation for one of its variables.

E.g.

X + Y + Z = 0

This equation would be represented by its parameters: parameters[0] is X, parameters[1] is Y, parameters[2] is Z.

If the user wants to solve for X, they would have to provide Y and Z. Likewise for solving for another parameter (if they want to solve Y, they must provide X and Z).

I am thinking of doing this by requiring them to pass an array of the values of X,Y, and Z, and the index of the one they want to solve for. For example, if they want to solve X, they would do:

parameters = {unused, 3.4, 5.6};
Solve(parameters, 0)

Is there some reasonable way of writing the internals of this function besides providing a giant switch statement?

if(paramToSolve == 0)
{
  X = -Y - Z;
}
else if(paramToSolve == 1)
{
 Y = -X - Z;
}
....

This gets really annoying when the model/equation gets bigger.

I am trying not to have to break out some big symbolic solver library or something like that, but it seems like that's basically what I'm asking for :)

Thoughts?

Thanks,

David

[nezachem]

> Is there some reasonable way of writing the internals of this function besides providing a giant switch statement?

Of course. Write a separate solver for each case, and keep them in a vector (or a map).

[L7Sqr]

I'm not sure I understand the problem. In the example you gave all you need to do to solve for any missing parameter is to sum the negative value of the values provided. It's the same equation, regardless of the missing parameter - for any number of parameters.
Are you looking to solve more complicated expressions?

[daviddoria]

L7Sqr, yes, a subclass will implement the Solve(params, paramToSolve) function, so some subclasses may have complicated equations. The best case is just to have the subclass specify the equation somehow and have the superclass do all of this business of solving for different variables, etc.

[mrnutty]

Is the equations always linear? Or polynomial? Assuming its linear equation then a good way to solve the problem is to first just add/subtract/multiply/divide all possible numbers in the equation, then all your left with is a equation of the form, AW + B = C where W is a variable, and A,B,C is some constant. Then you can go ahead and solve it. Thats a high level description.
How you add the numbers and ignore the variable is up to you. You can for example, first find the only variable in the equation, note it. Then proceed to compute the final values in the equations then solve it.

[mike_2000_17]

Well, first of all, lets get rid of the obvious solutions (that you have ruled out):
1) You can use a symbolic math library. Like GiNaC. Enter the formula as a string expressions, substitute the known variables and ask it to solve for the value of the unknown(s). But the engine will have to do its work at every query, and typically, symbolic math engines are very slow, because this type of work is hard for a computer to do (but pretty easy for a human).
2) You can use a simple root-finding method (like binary search, fixed-point, secant, Newton-Raphson, etc.). That is simple as hell to do, but it is iterative and thus, subject to all the issues of getting a good initial guess, divergence, etc.

Besides using one of the above, I think you are out-of-luck my friend. Unless you have some sort of predetermined structure (as suggested by firstPerson, e.g., you know it is linear or polynomial of some order), there are no general way of starting from an equation in terms of a few unknowns and automatically generating solved solutions from any possible unknown of the equation. I mean, if there was such a thing, there would be far less mathematicians in the Universities! There is no real way to avoid having to enter equations for each case (whether you enter them in a switch-case, as elements in a look-up table, or whatever, it will boil down to the same thing).

You could, however, develop a separate program that takes an equation, hands it over to a symbolic math engine, and spits out all the different solutions (embedded in some compilable C++ source file). At least, that will save you some manual labour.

There is one other possibility. Brace yourself. C++ is obviously not a symbolic math engine, it is just a normal programming language. However, you can program a symbolic math engine in C++ (e.g. GiNaC), which means, you can program a symbolic math engine in any Turing-complete programming language. And, template meta-programming is a Turing complete programming language whose "programs" run at compile-time. This means, it would be possible to program a symbolic math engine using template meta-programming, such that it generates, automatically, the solution to any solvable equation for any unknown. This "technique" is what mainly motivates "expression-templates", but, as far as I know, this is no more than an idea or a "dream", and expression templates are mainly used for lazy expression evaluations right now (see Boost.Proto) and a bit for expression simplifications (pre-compilation, aggressive optimizations) (see Blitz++).

[ravenous]

For simple equations of the form:

\begin{equation*}
0 = \sum_{i = 0}^N A_i x_i
\end{equation*}

I think you could solve for any of the x_i with something like:

#include <iostream>
#include <vector>

/* I made these typedefs to tidy things up. The first element of the */
/* pair is the coefficient, and the second is the variable value     */
typedef std::pair< double, double > LinearTerm;
typedef std::vector< LinearTerm > Equation;

/* equation solver */
double solveLinearSum( Equation& eqn, const size_t termToSolveFor );

int main()
{
   /* Make a simple equation */
    Equation eqn;
    eqn.push_back( LinearTerm(2, 5) );
    eqn.push_back( LinearTerm(9, 1) );
    eqn.push_back( LinearTerm(4, 2.3) );
    
    /* Solve for the second variable */
    std::cout << "Variable 2 = " << solveLinearSum( eqn, 1 ) << std::endl;

    return 0;
}

double solveLinearSum( Equation& eqn, const size_t termToSolveFor ){
    double solutionValue = 0;
    size_t numberOfTerms = eqn.size();

    for( size_t i = 1; i < numberOfTerms; ++i ){
        /* Use mod function and loop index range to exclude the chosen term */
        size_t currentTermIndex = (i + termToSolveFor + numberOfTerms) % numberOfTerms;
        solutionValue -= eqn[currentTermIndex].first * eqn[currentTermIndex].second;
    }

    /* scale and return the result */
    return solutionValue/eqn[termToSolveFor].first;
}

Using, the mod operator, you can sum all of the variables except the one of interest.

Hope that's useful :o)

[NathanOliver]

how complicated of an expression are you looking to solve?

[daviddoria]

They will all be geometric objects. The backstory is that this this for a generic Hough transform set of classes.

The most complicated functions would be trig functions.

[mike_2000_17]

>>The most complicated functions would be trig functions.

You mean like this: cos(x) - x == 0; . Even something as simple as that essentially requires a numerical, iterative root-finding method to solve for the single unknown x. Just put together a little Newton-Raphson root-finder and it should work quite fast. As mentioned before, you could use GiNaC too, and do as follows:

#include <ginac/ginac.h>
using namespace GiNaC;

class Foo {
  private:
    symbol x, y;
    ex expr;
  public:
    struct unknown { };

    Foo() : x("x"), y("y"), expr( cos(x*y) - x - y ) { };

    double solve(unknown aX, double aY) {
      return fsolve(subs(expr,y==aY),x,-3.14,3.14);
    };
    double solve(double aX, unknown aY) {
      return fsolve(subs(expr,x==aX),y,-3.14,3.14);
    };
};

Or something similar to that (I'm not so familiar with GiNaC). And, the solve functions will be the same for any derived class, so you probably won't need to re-implement it.

[mrnutty]

Yea I agree with mike, unless there is a really good compelling reason to do this from scratch, you should reuse other libraries that have been debugged and tested for years.