#12142: Speed up Pari finite field operations
--------------------------------+-------------------------------------------
Reporter: johanbosman | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.8
Component: basic arithmetic | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
--------------------------------+-------------------------------------------
Let us perform a simple addition of finite field elements that are
represented using Pari.
{{{
sage: F.<a> = GF(3^11)
sage: x = F.random_element()
sage: y = F.random_element()
sage: %timeit x + y
625 loops, best of 3: 13.2 µs per loop
}}}
Let us now measure how much time the *actual* addition takes:
{{{
sage: vx = x._FiniteField_ext_pariElement__value
sage: vy = y._FiniteField_ext_pariElement__value
sage: %timeit vx + vy
625 loops, best of 3: 4.6 µs per loop
}}}
This means two thirds of the execution time is used to wrap a ribbon
around the result and only one third for the actual addition!
But in fact Pari has a faster implementation for finite fields than this!
This was already mentioned at http://groups.google.com/group/sage-
nt/browse_thread/thread/e2dbbc72caeb589a
{{{
sage: def pari_ffelt(x): parix=pari(x); return
parix.lift().subst(parix.variable(), "ffgen((%s).mod)"%parix)
sage: px = pari_ffelt(x)
sage: py = pari_ffelt(y)
sage: %timeit px + py
625 loops, best of 3: 2.43 µs per loop
}}}
For multiplication, we have the following timings:
{{{
sage: %timeit x * y
625 loops, best of 3: 18.2 µs per loop
sage: %timeit vx * vy
625 loops, best of 3: 8.4 µs per loop
sage: %timeit px * py
625 loops, best of 3: 3.33 µs per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12142>
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.
