Math parser post

01/16/2013 with tags : c, math, xaos, fractals

I'm a fractal geek. To discover new Mandelbrot sets I needed to create a complex numbers math parser. So that I can just type in a set formula and quickly check if it is interesting or not. Because drawing of a single fractal (or its fragment) is always a computationally challenging task, parser had to be fast.

I have created easy to extend math parser, that is able to efficiently evaluate math formulas in complex number space. It also includes two complex number arithmetic implementations - nasm fpu (for x86) and GSL.

Parser is currently used in XaoS fast interactive fractal zoomer and create custom formulas.

Here are some notes and details on how it is build.

Basic assumptions

First step was to create a simple math parser for real numbers. Keeping in mind, that it has to be fast and will be used only for function evaluation I made these basic assumptions

  • ignore variables modification (assignment)

  • ignore all logical operations

  • set of numbers independent (ℝ, ℂ);

  • precision independent

  • easy to extend

  • make it fast

More assumptions

Basically speaking its all about transforming math expression

x * sin( 2 * x / y )

into corresponding stack notation of any kind (prefix or reverse Polish notation)

x y / 2 * sin 2 * (rpn)
x 2 x * y / sin * (prefix)

Arithmetic notations is then transformed into bytecode (or operators stack/tree) and expression value can be evaluated.

Problem with this simplified approach is that stack needs to be fixed (or even rebuild) every time we want to calculate expression value. Because parser is going to be used in loops, this is something we should avoid. Internal stack stucture should never be modified. There should be no extra steps before and after expression value is evaluated. Moreover there should be no memory operation during this operation.

The whole process can be divided into to two parts with two corresponding modules

  • parser - used only once to parse input expression and transform it into bytecode

  • evaluator - evaluate the value of the expression using input variables

I don't really care how fast parser is. I only need it to be reliable. To be honest it is slow, complicated and a bit memory consuming.

I have only focused on evaluator implementation. Its internal structure should fulfill this set of rules.

  • expession evaluation should be an in-situ operation.

  • evaluator should never change its state - in terms of its internal structure (no stack manipulation) and in terms of consumed memory.

  • changing the input variables should not result in any memory operations.

Implementation

Parser module

Parser is responsible for translating the input formula string into some kind of bytecode.

  • Lexical and syntactic analysis - use a simple context-free grammar for math expressions. Implementation depends on set of numbers we are working with (ℝ or ℂ)

  • Tokenization - covert input expression

    x * sin( 2 * x / y )
    

    into tokenized form and keep track of all tokens

    n * f( n * n / n )
    
  • Bytecode generator (eq. operation stack builder) - covert tokenized expression into bytecode

    +---+---+---+---+---+---+---+---+
    | n | n | n | * | n | / | f | * |
    +---+---+---+---+---+---+---+---+ 
    

Evaluator module

Evaluator is just a bytecode interpreter. It takes input variables and evaluates expression value. In this particular case bytecode is just a variation of operations stack rather that a typical bytecode. It cannot be saved and reused in compiled form.

( write about internal structure )

  • use prefix notation

  • use operation pipeline

  • don't include store operands on operations stack

Summary

  • parser can be used for any set of numbers and precision

  • parser is easy to extend (new functions, constants)

  • evaluator can be reused with different input variables

  • expression evaluation is an in-situ operation (in terms of structure and memory usage)

Code

Source code for both ℝ and ℂ is available on github.

For complex numbers implemetation details please read these posts

Finally the heart of math parser implementation.

sfNumber sffe_eval(sffe * const parser)
{
    register sfopr *optro;
    register sfopr *optr = parser->oprs;
    register sfopr *optrl = parser->oprs + parser->oprCount;
    optro = optr;
    for (optr = optr; optr != optrl; optr += 1, optro += 1) {
    optro->arg->parg = optro->arg - 1;
    optr->arg->parg = optr->f(optr->arg)->parg;
    };
    return *(parser->result);
};

Example

Parse debug trace

|-----------------------------------------
+ > lib/src/sffe.c[504] - parsing
|-----------------------------------------
| input (len.=30): |(-1+2*3(sin(x+1)-1/x))/(2*x+1)|
| check (len.=30): |(-1+2*3(SIN(X+1)-1/X))/(2*X+1)|
| compiled expr.: |(n+n*n*(f(n+n)-n/n))/(n*n+n)|
| operations: 10
| numbers,vars: 10
| stack not.: nnn*nn+fnn/-*+nn*n+/
| numbers:  -1 2 3 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 2 -1 -1 1 -1 -1
| functions fnctbl: [+] [*] [*] [SIN] [+] [-] [/] [/] [*] [+]
| functions used ptrs: __addr_dump__
| compiled in  0.000094 s
|-----------------------------------------
+ < lib/src/sffe.c[1020] - parsing
|-----------------------------------------