pganssle/Magnetometer-Controller — Issue #28: Math library optimization and improvements
Author: pganssle
Created: 2012-02-08 02:36:01+00:00
State: open
Labels: Low

The math library is something I wrote that has a certain algorithm for processing mathematical commands. It works fine, but it could probably be optimized for speed. The way I have it working currently is with a recursive algorithm that works with order of operations. So the way +(5\*x+4\*us)\*9+log(4)+3^2+(3==5+4)\*2.9 would be processed this way, using the function parse_math(). Note that once parens and expressions are taken care of, this has to be parsed recursively with *reverse* order of operations.

1. **+(5\*x+4\*us)\*9+log(4)+3^2+(3==5+4)\*2.9** - Convert to pure numbers
This expression would first be checked for variables, whitespace and various detritus. In this case, us is a variable set to 1000 (results are in nanoseconds in this case) and the trailing + would simply be removed. Things like 4+-3++5+--3 would be reduced to 4-3+5+3 through an algorithm that just kinda counts special characters. Though x is probably a variable, the way variables are always treated is by just setting a constant named that and evaluating the whole expression a bunch of times. So for now, imagine that x = 4. This bit is the only non-recursive part, because it's really considered "cleanup".

2. **(5\*4+4\*1000)\*9+log(4)+3^2+(3==5+4)\*2.9** - Parens and expressions
The expression is first checked for, I think, expressions. log(4) would parse as 0.602059991. If it were log(4+3), you'd call parse_math("4+3") and evaluate the result. This is also where parentheses are evaluated. So it would detect the string "5\*4+4\*1000" and call parse_math("5\*4+4\*1000").

3. *New call:* **5\*4+4\*1000** --> Multiply/divide, Called with a flag saying to skip parens and expressions.
Order of operations goes ^, \*/%, +-, &| (bitwise operations). Since this is recursive, it's done in reverse. Algorithm detects no bitwise operations, but detects the + sign, so parse_math(5\*4) and parse_math(4\*1000) are called.

4. *New call:* **5\*4**, **4\*1000**:
Each of these will find that there is only a single operation left. The *only* time a return value is provided is when the input is of the form number-operator-number. So the function would detect that 5\*4 is 5, \*, 4 and return 20. Similarly for the second expression it returns 4000.

5. *Back to call in step 3*: **20+4000**:
Value returns 4020 to step 1.

6. *Back to step 1*: **4020\*9+3^2+0.602059991+3^2+(3==5+4)\*2.9** - Parens again.
Algorithm now detects (3==5+4) as being in parens as well and parse_math("3==5+4") is called:

7. *New call*: **3==5+4**
The first thing that happens is that a boolean operation is detected. Value returns (parse_math("3") == parse_math("5+4"))?1:0 (converting from boolean values to doubles). parse_math("3") will be recognized to contain no special characters and simply return the double 3. "5+4" will be recognized as number-operator-number and 9 is returned. In this case, 3!=9, so this returns 0.

8. *Back to original call*: **4020\*9+3^2+0.602059991+3^2+0\*2.9**
We now have something that is only of the form number-operator-number-operator. From this point on, parse_math just recursively evaluates in reverse order of operations. The sequence looks like this:

1. parse_math("4020\*9") + parse_math("0.602059991+3^2+0\*2.9"). Left-hand side evaluates as 36,180 (n-o-n, so it can return)
2. "0.602059991+3^2+0\*2.9" -> parse_math("0.602059991")+parse_math("3^2+0\*2.9"). Left-hand side evaluates as a number.
3. "3^2+0\*2.9" -> parse_math("3^2")+parse_math("0\*2.9") - both sides evaluate, result is 9, this is passed to 8.2, which then returns 9.602059991 to 8.1, which returns 36189.602059991, and the evaluation has completed.

Things that probably could be done to optimize this:

* Have a single check at the beginning to see if the value is a number. I think there are probably at least 8 needless operations per cycle just for testing things like parse_math("3")+parse_math("4"). This only applies when there's a plus sign.
* Allow multiple expressions to be passed as an array of arrays to optimize. In order of how realistic the implementation is, we could detect the following things:
* Determine if two expressions are the same and evaluate once.
* Determine if any expression is a subset of another. For example, 540/(2\*(x+1)) and (x+1), then combine evaluation.
* If it's easy enough, we may want to check to find common subsets or related evaluations, either within an expression or between expressions. So for example if many expressions have constants multiplied by (x < 4/t + 9), you want to evaluate that once for all expressions.

And the big optimization (more important than any of the earlier stuff), would be to change up the algorithm to something tokenized and not necessarily recursive like the one I designed. The key is to separate everything into constants and variables and evaluate as much as you can in a constrained manner. The algorithm would go like this:
1. Clean up input, trailing +, unnecessary parens, etc.
2. Build an array of inputs and an array of operators, as well as a third array indicating if the value at a given position is a variable. So "5+4-x\*9" would generate 3 arrays, vals = [5, 4, 0, 9], isvar = [0, 0, 1, 0], ops = ['+', '-', '\*']. You can also generate 2 more arrays containing paren positions. So for (5 + 9 - 3) + 4-6 + (9^8), your paren arrays would be p_start = [0, 5] and p_end = [2, 7], indicating that there are parens that start before the number at index 0 and end after the number at index 2, and another pair between (5, 7). If n is the number of numbers, you will then have 4 arrays of size n and one array of size 1.
3. Write a function which takes these vectors and reduces n as far as it goes without evaluating n. So in the above example of 5+4-x\*9, the result would be 9+x\*9 - this can be done in place as arrays in C are just pointers to memory.
4. Since constants and variables are distinguished now, the variable values will be stored in an array of arrays, so if there are 10 variables and there are 50 steps in the evaluation, you have a an array of 10 arrays of 50. When a variable name is detected, its index in this array is put in the "vals" array. So if there are 2 variables, x and y, the expression 4\*y + x-9 would be broken down into [4, 1, 0, 9], [0, 1, 1, 0], ['\*', '+', '-']. Where vars[0][1] is the value of variable x at step 1 and vars[1][1] is the value of y at step 1.

This will *massively* optimize the parsing stage, because right now if I try and evaluate 5 expressions for a 50-step experiment with 4 transients, you're actually *parsing* the ASCII in that recursive method, 250 times. It's not particularly slow, but if you do something like click the "up" button to change the number of steps, that triggers a re-calculation each time, to determine if there are errors at any step in the calculation, so if you click it 10 times quickly, now you have to do 2500 calculations very quickly and it can cause little UI problems.

* Make a distinction between variables and constants for generating arrays.
* Find a way to simplify as much as possible before generating an array. For example, (5*x + 4*us) should be broken