#9051: Fast function field arithmetic
------------------------+---------------------------------------------------
Reporter: robertwb | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.5
Component: algebra | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------+---------------------------------------------------
Comment(by was):
I did a benchmark on sage.math, comparing this code to Magma:
SAGE with your patch:
{{{
sage: R.<T> = GF(71)[]; K.<T> = FractionField(R); a=(T^3+T-1)*(T^2-2);
b=(3*T^5-T+7)*(T^2-2)
sage: timeit('a/b+b/a')
625 loops, best of 3: 26.3 µs per loop
sage: time v=[a/b+b/a for i in range(10^5)]
CPU times: user 2.94 s, sys: 0.02 s, total: 2.96 s
Wall time: 2.96 s
sage: time v=[a*b for i in range(10^5)]
CPU times: user 0.54 s, sys: 0.02 s, total: 0.56 s
Wall time: 0.56 s
sage: time v=[(1/a)*(1/b) for i in range(10^5)]
CPU times: user 1.80 s, sys: 0.00 s, total: 1.80 s
Wall time: 1.80 s
}}}
Before the patch, the same benchmark is massively slower, so this patch is
a very big improvement:
{{{
sage: sage: R.<T> = GF(71)[]; K.<T> = FractionField(R);
a=(T^3+T-1)*(T^2-2); b=(3*T^5-T+7)*(T^2-2)
sage: sage: timeit('a/b+b/a')
625 loops, best of 3: 776 µs per loop
}}}
In Magma:
{{{
sage: R.<T> = GF(71)[]; K.<T> = FractionField(R); a=(T^3+T-1)*(T^2-2);
b=(3*T^5-T+7)*(T^2-2)
sage: aa=magma(a); bb=magma(b)
sage: magma.eval('a:=%s;b:=%s;'%(aa.name(),bb.name()))
sage: magma.eval('time v := [a/b+b/a : i in [1..10^5]];')
'Time: 0.800'
sage: magma.eval('time v := [a*b : i in [1..10^5]];')
'Time: 0.320'
sage: magma.eval('time v := [(1/a) * (1/b) : i in [1..10^5]];')
'Time: 0.830'
}}}
Something surprising is that working in your rational function field is
much faster than working with polynomials!
{{{
sage: R.<T> = GF(71)[]; a=(T^3+T-1)*(T^2-2); b=(3*T^5-T+7)*(T^2-2)
sage: time v=[a*b for i in range(10^5)]
CPU times: user 2.02 s, sys: 0.00 s, total: 2.02 s
Wall time: 2.02 s
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9051#comment:14>
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.
