On Jun 28, 2008, at 1:55 PM, Carl Witty wrote:
> 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.
As the author of the original fast_float stuff, I want to give a big
+1 to this project. I've been wanting to do something like this for
some time but it's never gotten high enough on my priority list to
actually code up. One caveat is that you go with a more general
instruction set, I would like to see benchmarks to make sure that
there isn't any speed regression.
> ------
>
> 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)
the keyword "over" sound odd to me, maybe "domain."
> 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.
I think common subexpressions should be (loosely) checked for
equality, *not* restricting to the same Python instance only.
The question of unpickling old fast_float objects has come up. These
may have gotten attached to pickled symbolic expressions or
polynomials, so should be unpicklable. However, if one writes a
compatible _unpickle_FastDoubleFunc then one doesn't need to care
they whole old implementation around.
- Robert
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
