#7742: add a compose function to sage
------------------------------------------------+---------------------------
Reporter: was | Owner: AlexGhitza
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.6.1
Component: basic arithmetic | Keywords:
Author: Christopher Olah, Felix Lawrence | Upstream: N/A
Reviewer: Paul Zimmermann | Merged:
Work_issues: |
------------------------------------------------+---------------------------
Comment(by jrp):
Replying to [comment:19 flawrence]:
> With normal python functions (such as those in the doctest), the powers-
of-two provides a major speedup for large n over the other techniques I
tried, both for the function composition and for the evaluation of the
resulting function (benchmarked using "timeit"). In fact, without a
powers-of-two-type algorithm, the self_compose function regularly hit the
recursion limit and crashed for large n (above 500 or 1000). But I don't
know if anyone is interested in large n cases.
With normal python functions, I don't think there is any gain from powers
of two.
With the self_compose from adds-compose-etc.patch:
{{{
sage: f = lambda x: x + 1
sage: g = x + 1
sage: f1 = self_compose(f,10000)
sage: g1 = self_compose(g,10000)
sage: timeit('self_compose(f,10000)')
625 loops, best of 3: 66.6 µs per loop
sage: timeit('self_compose(g,10000)')
625 loops, best of 3: 66.9 µs per loop
sage: timeit('f1(0)')
25 loops, best of 3: 9.32 ms per loop
sage: timeit('g1(0)')
5 loops, best of 3: 375 ms per loop
sage: timeit('nest(f,10000,0)')
125 loops, best of 3: 6.46 ms per loop
sage: timeit('nest(g,10000,0)')
5 loops, best of 3: 379 ms per loop
sage: def new_self_compose(f,n):
....: return lambda a: nest(f,n,a)
....:
sage: timeit('new_self_compose(f,10000)')
625 loops, best of 3: 1.17 µs per loop
sage: timeit('new_self_compose(g,10000)')
625 loops, best of 3: 2.68 µs per loop
}}}
Since self_compose is implemented via {{{lambda x: f(g(x))}}}, we have to
eventually pass the argument through {{{f}}} the correct number of times.
Let's move the powers of two, and the symbolics handling, into a method of
symbolic functions. Then the compose tools for python functions can have
fast, dirt-simple implementations.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7742#comment:27>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
