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
-~----------~----~----~----~------~----~------~--~---
