Evaluating An Equation

[Shaggy Hiker]

Suppose you had an equation like this:

5X + 3Y * (4Sin(N)-Sqrt(T)) + 7 = V

And you also had 30 values for each of X, Y, N, and T. How would you evaluate the equation?

I have a technique to do this, and considered explaining it, but decided it just got in the way. For this simple example, my technique is very fast, but once the equations can include over two dozen variables, as opposed to just four as in this example, the performance starts to slow. In some cases, it slows greatly. I suspect, though I have no proof of this yet, that it might have to do with multiple nested parentheses in the equations.

So, what I'm looking for is whether or not there is some technique for evaluating equations of nearly arbitrary length, where there can be geometric, and some fairly simple exponential and logarithmic transformations of individual variables?

EDIT: Oh, yeah, I should also mention, there will be some 300 million of these equations to evaluate, so speed is crucial.

[Arnoutdv]

For speed I would precalculate a lot of the Sin() and Sqrt() and put them in a lookup table
What's the range for the Sin and Sqrt values?

.. there will be some 300 million of these equations to evaluate ..

Is it only this formula or are the formula's dynamic and coming from an external source?

[dbasnett]

Are we talking about evaluating the text?

[Niya]

Are we talking about evaluating the text?

I am also wondering this as well. Is he talking about talking his program taking an expression as text and evaluating it or is he talking about his actual program code?

In any case, assuming it's the former, you can actually compile these expressions at runtime and execute them as if it were compiled code in the program itself. You just have to parse it into an expression tree first.

Here is an example of using expression trees to evaluate expressions:-

        'Evaluate 5x + 2y
        '**********************************
        Dim x_param = Expression.Parameter(GetType(Double))
        Dim y_param = Expression.Parameter(GetType(Double))
        Dim const_5 = Expression.Constant(5.0R)
        Dim const_2 = Expression.Constant(2.0R)

        Dim mul_5x = Expression.Multiply(const_5, x_param)
        Dim mul_2y = Expression.Multiply(const_2, y_param)
        Dim add_5x2y = Expression.Add(mul_5x, mul_2y)

        Dim lambda = Expression.Lambda(add_5x2y, x_param, y_param)

        'Compile the expression as a function.
        'A delegate is returned
        Dim c = lambda.Compile()

        'Execute the delegate as you would any other.
        Debug.WriteLine(c.DynamicInvoke(10, 3))

Here's one for the expression provided in the OP:-

        '5X + 3Y * (4Sin(N)-Sqrt(T)) + 7
        '**********************************
        Dim x_param = Expression.Parameter(GetType(Double))
        Dim y_param = Expression.Parameter(GetType(Double))
        Dim n_param = Expression.Parameter(GetType(Double))
        Dim t_param = Expression.Parameter(GetType(Double))

        Dim const_5 = Expression.Constant(5.0R)
        Dim const_3 = Expression.Constant(3.0R)
        Dim const_4 = Expression.Constant(4.0R)
        Dim const_7 = Expression.Constant(7.0R)

        Dim mul_5x = Expression.Multiply(const_5, x_param)
        Dim mul_3y = Expression.Multiply(const_3, y_param)

        Dim sin_n = Expression.Call(GetType(Math).GetMethod("Sin"), n_param)
        Dim mul_4sin_n = Expression.Multiply(const_4, sin_n)

        Dim sqrt_t = Expression.Call(GetType(Math).GetMethod("Sqrt"), t_param)
        Dim sub_sqrt_t = Expression.Subtract(mul_4sin_n, sqrt_t)
        Dim mul_3y_sub = Expression.Multiply(mul_3y, sub_sqrt_t)

        Dim add_all = Expression.Add(Expression.Add(mul_5x, mul_3y_sub), const_7)

        Dim lambda = Expression.Lambda(add_all, x_param, y_param, n_param, t_param)

        Dim c = lambda.Compile()

        Debug.WriteLine(c.DynamicInvoke(10, 3, 1.5, 9)) ' Example values for x, y, n, t

[Shaggy Hiker]

The equations will almost never be the same, and yes, I'm talking about essentially evaluating the text. Back when I originally wrote this, back in VB6 in...probably around 2002, I was explicitly using strings and parsing them. The performance of that was horrible, as you would expect. I then came up with a better way to represent the equations as a List(of SomeClass), where SomeClass was an object that could be either a constant ( the 5 in 5X), an element (the X in 5X, and I didn't want to use the term 'variable', as that would have multiple meanings in programming), or an operator (the + in 5X + 7).

Parentheses are the pain.

I'll have to look into that Expression approach. I hadn't seen that. It does seem like it could have an advantage, as compiling the equation might allow it to be sped up. I'm doing something like that already, just rolling my own, and it's pretty quick. Building the equation will probably be equally painful either way, but the compiled lambda might outperform the approach I'm taking.

[Niya]

No matter what you do, parsing expressions will always be quite costly. If it's somehow possible for all your expressions to be pre-compiled and cached then the cost of actually executing them would go down dramatically.

Also note in the examples I posted, performance can be improved further by avoiding DynamicInvoke and using a strongly typed delegate. You would sacrifice flexibility though as you would have to know the parameters of the delegate at compile time. DynamicInvoke allows you to call any delegate at runtime with knowing it's parameters or their types.

[Shaggy Hiker]

Yeah, lots of options are unavailable due to all the equations being known only at the time they are evaluated, effectively.

[digitalShaman]

I then came up with a better way to represent the equations as a List(of SomeClass), where SomeClass was an object that could be either a constant ( the 5 in 5X), an element (the X in 5X, and I didn't want to use the term 'variable', as that would have multiple meanings in programming), or an operator (the + in 5X + 7).

Parentheses are the pain.

what you did with SomeClass could be done via a list of delegate functions in .net.
you can get around the parenteses if you convert your formula to RPN

N Sin 4 * T Sqrt - Y * 3 * 5 X * + 7 +

[Shaggy Hiker]

Quite possibly, but they are the way they are for a reason. Whether the cost of converting to RPN would be justified is debatable, as it would have to be done on the fly, just prior to evaluating each one.

[Arnoutdv]

Are there millions of unique formulas/ equations?

[Niya]

Yeah, lots of options are unavailable due to all the equations being known only at the time they are evaluated, effectively.

If you don't mind, can I see the code that parses these expressions?

[Shaggy Hiker]

I don't think it would be all that descriptive. There's no equation and a whole lot of unrolling, so you'd just see a mass of code that would require a bit too much explanation. I had written an explanation of what it is doing, but decided it wasn't helpful. I don't think the code would be much better.

Essentially, almost every equation can be simplified into what amounts to Constants, Elements, and Operators. Elements would normally be called variables, but since that word has a different meaning in coding, I used the term "elements" to avoid that conflict. So, if you have an equation like 4X * 3X + 5Y + 6, it can be seen as CEOCEOCEOC. Parentheses can appear in only certain places in the equation, but there can be any number of them. Each of those items (C, E, O, open parentheses, and close parentheses) are just a certain type of object, which means that an equation is a List(of Items).

There are equations that can't quite be described in this fashion, though, so I cheated a little bit, a long time ago, and have stuck with it. Evaluating the equation is just a matter of evaluating every (CE) pair for all inputs. This is super fast (it's never more than a simple calculating in a loop), but also a giant double case statement, so it would look horrible. This results in a List(of Double()) and a List of Operators. Those then get tied together by a second operation.

And if you're wondering what the point is, it's that when you can write out equations as CEO triplets, then you can also evolve equations, which is the point behind the whole thing. Create random equations, see how well they match the desired pattern, rank them, mate them, and repeat.

[Zvoni]

Have you thought about bringing your "Text"-Equation into "polish" notation? of course honoring precedence of paranthesis etc.

[digitalShaman]

a lazy method. this will not perform fast to compile but should be ok to execute. so if you need a different formula for each of the population items, and only once, this will be bad. if you apply the same formula on all individuals, this should be ok.

    Private Sub CompileDelegate()
        Dim sParameters As String = "X,Y,N,T"
        Dim sFormula As String = "5*X + 3*Y * (4*Math.Sin(N)-Math.Sqrt(T)) + 7"

        Dim oParams As New CodeDom.Compiler.CompilerParameters
        oParams.GenerateInMemory = True
        oParams.TreatWarningsAsErrors = False
        oParams.WarningLevel = 4
        Dim sAssemblies() As String

        sAssemblies = "mscorlib.dll,System.dll".Split(","c)
        oParams.ReferencedAssemblies.AddRange(sAssemblies)
        Dim oVBProvider As CodeDom.Compiler.CodeDomProvider = CodeDom.Compiler.CodeDomProvider.CreateProvider("VisualBasic")
        Dim sImports As String = "Imports System"

        Dim sb As New System.Text.StringBuilder
        With sb
            .AppendLine(sImports)
            .AppendLine("Public Module Job")
            .AppendLine($"Public Function Execute({sParameters}) as Double")
            .AppendLine("Return " & sFormula)
            .AppendLine("End Function")
            .AppendLine("End Module")
        End With

        Dim oCompilerResults As CodeDom.Compiler.CompilerResults = oVBProvider.CompileAssemblyFromSource(oParams, sb.ToString)

        If oCompilerResults.Errors.Count > 0 Then
            Throw New Exception(oCompilerResults.Errors(0).ErrorText)
        Else
            Dim oJob As Reflection.MethodInfo = oCompilerResults.CompiledAssembly.GetType("Job").GetMethod("Execute")
            Dim v As Double = oJob.Invoke(Nothing, {10, 2, 3, 4})
            MessageBox.Show(v)
        End If
    End Sub

[Shaggy Hiker]

The "equations" can be represented as equations as we might write them. I overloaded ToString for both genes and the whole genome, such that they appear as strings, but they are not inherently strings, so anything that turns them into strings then evaluates them as strings, seems like it would be worse.

Interpreting them into RPN is something I'll have to consider in more depth. That would be the evaluation step, and it may well have an advantage, but it would have to be an advantage that outweighed the cost of transforming them into RPN. It's an interesting idea, but I have a different route to pursue. I realized last night, that I had left something quite bad in the code. I was using exception handling to catch certain cases that will arise routinely in some datasets. It never arose in my test data, so it wasn't an issue, but it does arise, and would mean that some equations will throw exceptions. That will destroy performance, of course. What is being caught is correct, but certainly not exceptional, so exception handling is not the way to handle it.

I also realized that I need to get a particularly troublesome equation in isolation so that I can compare different approaches. Since the equations are all ephemeral, I'll have to modify the code a bit to identify and isolate certain test candidates. That will be a fun pursuit for today.

[Shaggy Hiker]

I added a few features to the program, but along the way, I also realized that there's no good way for me to study different approaches to evaluating the equations. They live ephemeral lives of very short duration with no good way to ever make them sufficiently permanent to study effectively.

An unstudied program isn't worth writing, so I'm going to change the design around a bit such that I can pluck pieces out, put them on a workbench, and use them to explore alternatives.

[OptionBase1]

Have you looked at Math.NET Symbolics? It seems like it would do what you are looking for. No idea what performance is like for a large number of evaluations.

https://symbolics.mathdotnet.com/

[Shaggy Hiker]

Hmmm, I changed the serialization from binary to JSON, and the performance went up by more than a factor of 10x. Now, the serialization pretty much couldn't be doing that. The file only serializes once every 200 generations, so it would have been pretty noticeable if every 200 generations the program just hung for a very long time (to get a tenfold increase in performance due to something that runs every 200 generations, would require that event to have taken a pretty obvious amount of time in the past, which it did not). Far more likely is that some other change I made caused this. I did make other changes.

Back when I originally wrote this, I was using DoEvents, which is so slow in itself that I could be pretty sloppy with some other things without having any negative impact. I was abusing exception handling to catch actions that were bad, rare, but not really exceptions. However, rare events start becoming pretty common once you get into millions of samples. If they were one in 10,000 events, they would still be terribly common.

We'll see. All this was done to get to the point where I could isolate the evaluation so that I could meaningfully test different alternatives in a replicable fashion. Now...well, I still might do that, but mostly just for fun. People made some good suggestions in this thread, in that they were novel approaches to the evaluation, which were radically unrelated to what I was doing, so they would be good to test out.