During Developer Days 1, I announced that I wanted to rewrite fast_float to support evaluation over more types, to handle common subexpressions, and to handle conditional expressions. I've started this project by writing a new version of the fast_eval.pyx module docstring, and I'm wondering if anybody has any comments on it.
Note that I haven't written any code yet... only the docstring. Carl ------ Fast Numerical Evaluation. For many applications such as numerical integration, differential equation approximation, plotting a 3d surface, optimization problems, monte-carlo simulations, etc., one wishes to pass around and evaluate a single algebraic expression many, many times at various floating point values. Other applications may need to evaluate an expression many times in interval arithmetic, or in a finite field. Doing this via recursive calls over a python representation of the object (even if maxima or other outside packages are not involved) is extremely inefficient. This module provides a function, \function{fast_callable}, to transform such expressions into a form where they can be evaluated quickly. sage: f = sin(x) + 3*x^2 sage: ff = fast_callable(f) sage: ff(3.5) 36.3992167723104 sage: ff(RIF(3.5)) [36.399216772310374 .. 36.399216772310382] By default, \function{fast_callable} only removes a bit of interpretive overhead from the evaluation, but all of the individual arithmetic operations are done using standard \sage arithmetic. You can specify a particular domain for the evaluation using \code{over=}: sage: ff = fast_callable(f, over=RR) For most \sage rings, this will be slightly faster, because the coercion model is bypassed. However, for some types, this will get a large speedup, because we have special-purpose interpreters for those types. One example is RDF: sage: ff = fast_callable(f, over=RDF) By default, \function{fast_callable} uses the same variable names in the same order that the \method{__call__} method on its argument would use; for instance, on symbolic expressions, the variables are used in alphabetical order. sage: var('y,z,x') (y, z, x) sage: f = 10*y + 100*z + x sage: f(1,2,3) 321 sage: ff = fast_callable(f) sage: ff(1,2,3) 321 However, this can be overridden with \code{vars=}: sage: ff = fast_callable(f, vars=('x','w','z','y')) sage: ff(1,2,3,4) 341 This should be enough for normal use of \function{fast_callable}; let's discuss some more advanced topics. Sometimes it may be useful to create a fast version of an expression without going through symbolic expressions or polynomials; perhaps because you want to describe to \function{fast_callable} an expression with common subexpressions. Internally, \function{fast_callable} works in two stages: it constructs an expression tree from its argument, and then it builds a fast evaluator from that expression tree. You can bypass the first phase by building your own expression tree and passing that directly to \function{fast_callable}, using an \class{ExpressionTreeBuilder}. sage: from sage.ext.fast_eval import ExpressionTreeBuilder sage: etb = ExpressionTreeBuilder(vars=('x','y','z')) An \class{ExpressionTreeBuilder} has four interesting methods: \method{constant}, \method{var}, \method{call}, and \method{choose}. All of these methods return \class{ExpressionTree} objects. The \method{var} method takes a string, and returns an expression tree for the corresponding variable. sage: x = etb.var('x') sage: y = etb.var('y') sage: z = etb.var('y') Expression trees support Python's numeric operators, so you can easily build expression trees representing arithmetic expressions. sage: v1 = (x+y)*(y+z) + (y//z) The \method{constant} method takes a \sage value, and returns an expression tree representing that value. sage: v2 = etb.constant(3.14159) * x + etb.constant(1729) * y The \method{call} method takes a \sage/Python function and zero or more expression trees, and returns an expression tree representing the function call. sage: v3 = etb.call(sin, v1+v2) Many \sage/Python built-in functions are specially handled; for instance, when evaluating an expression involving \function{sin} over \code{RDF}, the C math library function \function{sin} is called. Arbitrary functions are allowed, but will be much slower since they will call back to Python code on every call; for example, the following would work. sage: my_sqrt = lambda x: pow(x, 0.5) sage: _ = etb.call(my_sqrt, v1) The final interesting method of \class{ExpressionTreeBuilder} is \method{choose}. This produces conditional expressions, like the C \code{COND ? T : F} expression or the Python {T if COND else F}. This lets you define piecewise functions using \function{fast_callable}. sage: v4 = etb.choose(v3 >= etb.constant(0), v1, v2) The arguments are \code{(COND, T, F)} (the same order as in C), so the above means that if \variable{v3} evaluates to a nonnegative number, then \variable{v4} will evaluate to the result of \variable{v1}; otherwise, \variable{v4} will evaluate to the result of \variable{v2}. Let's see an example where we see that \function{fast_callable} does not evaluate common subexpressions more than once. We'll make a \function{fast_callable} expression that gives the result of 16 iterations of the Mandelbrot function. sage: etb = ExpressionTreeBuilder('c') sage: z = etb.constant(0) sage: c = etb.var('c') sage: for i in range(16): ... z = z*z + c sage: mand = fast_callable(z, over=CDF) Now \variable{ff} does 32 complex arithmetic operations on each call (16 additions and 16 multiplications). However, if \code{z*z} produced code that evaluated \variable{z} twice, then this would do many thousands of arithmetic operations instead. Note that the handling for common subexpressions only checks whether expression trees are the same Python object; for instance, the following code will evaluate \code{x+1} twice: sage: etb = ExpressionTreeBuilder('x') sage: x = etb.var('x') sage: (x+1)*(x+1) but this code will only evaluate \code{x+1} once: sage: v = x+1; v*v To provide \function{fast_callable} for your own class (so that \code{fast_callable(x)} works when \variable{x} is an instance of your class), implement a method \code{_fast_callable_(self, etb)} for your class. This method takes an \class{ExpressionTreeBuilder}, and returns an expression tree built up using the methods described above. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---