#7719: Improvements to complex AGM
--------------------------------+-------------------------------------------
Reporter: cremona | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.3.1
Component: basic arithmetic | Keywords: complex agm
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
--------------------------------+-------------------------------------------
Comment(by cremona):
Replying to [comment:2 was]:
> Watch out. The following is a much more accurate reflection of how fast
PARI is at this computation (and even then there is still a tiny bit of
overhead):
> {{{
> sage: timeit('pari("agm(-0.95-0.65*I,0.683+0.747*I)")')
> 625 loops, best of 3: 33.2 µs per loop
> }}}
> versus
> {{{
> sage: CC = ComplexField(200)
> sage: a = CC(-0.95,-0.65)
> sage: b = CC(0.683,0.747)
> sage: z = pari(a)
> sage: timeit('z.agm(b)')
> 625 loops, best of 3: 309 µs per loop
> }}}
If you instead do timeit('a.agm(b)') you'll see a vast slow-down. So the
difference in speed is mainly coming from conversion to pari. That is
still worth avoiding if we can write a fast native version.
>
> To avoid overhead from caching:
> {{{
> sage: time z = pari("for(i=1,10^5,agm(-0.95-I*0.65,0.683+I*0.747))")
> CPU times: user 2.49 s, sys: 0.00 s, total: 2.49 s
> Wall time: 2.49 s
> }}}
> which is about 25 microseconds.
>
> Conclusions:
>
> (1) How did you come up with an algorithm="pari" that takes 7ms?
That's really long.
I didn't come up with anything! That code just calls the version of agm
we have in Sage already which is two lines, calling pari after conversion.
>
> (2) What we do in Sage should hopefully take at most 25 microseconds
in just order to be competitive to PARI.
Agreed. But as I said on sage-devel, what's very important for me is to
get the correct ("optimal") value of the function. I hope that will not
mean having two versions of the function, one very fast but producing a
value which is useless for me (as with the existing pari function) and a
slower one I actually use.
By the way, this is not likely to be a function which is called many times
over and over.
>
> Here's some more to worry about. Magma evidently does not even have a
*complex* AGM. However, it has a real AGM, and it is an order of
magnitude faster than PARI's:
>
> {{{
> age: time z = pari("for(i=1,10^5,agm(-0.95,0.683))")
> CPU times: user 2.07 s, sys: 0.00 s, total: 2.07 s
> Wall time: 2.07 s
> sage: magma.eval("time for n in [1..10^5] do z := AGM(0.95,0.683); end
for;")
> 'Time: 0.170'
> sage: 2.07/0.170
> 12.1764705882353
> }}}
>
Good point -- that's what we have to try to beat/match!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7719#comment:3>
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.
