#12142: Speed up Pari finite field operations
--------------------------------------------------+-------------------------
Reporter: johanbosman | Owner: AlexGhitza
Type: enhancement | Status:
positive_review
Priority: major | Milestone: sage-5.11
Component: basic arithmetic | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: Jean-Pierre
Flori
Authors: Peter Bruin | Merged in:
Dependencies: #14817, #14818, #14832, #14833 | Stopgaps:
--------------------------------------------------+-------------------------
Old description:
> 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
> }}}
>
> This ticket implements an interface to PARI's FFELT type for non-prime
> finite fields. It can be tested by constructing finite fields as
> follows, for ''p'' prime and ''n'' >= 2:
> {{{
> sage: F.<a> = FiniteField(p^n, impl='pari_ffelt')
> }}}
> This implementation should probably become the default for non-prime
> finite fields of characteristic > 2 and cardinality > 2^16^, superseding
> the existing PARI polmod implementation. This switch is the goal of
> ticket #14888.
>
> Apply:
> * [attachment:trac_12142-FiniteField_pari_ffelt.improved.patch],
> * [attachment:trac_12142-singular_conversion.patch],
> * [attachment:trac_12142-reviewer.patch].
New description:
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
}}}
This ticket implements an interface to PARI's FFELT type for non-prime
finite fields. It can be tested by constructing finite fields as follows,
for ''p'' prime and ''n'' >= 2:
{{{
sage: F.<a> = FiniteField(p^n, impl='pari_ffelt')
}}}
This implementation should probably become the default for non-prime
finite fields of characteristic > 2 and cardinality > 2^16^, superseding
the existing PARI polmod implementation. This switch is the goal of
ticket #14888.
Apply:
* [attachment:trac_12142-FiniteField_pari_ffelt.improved.patch]
* [attachment:trac_12142-singular_conversion.patch]
* [attachment:trac_12142-reviewer.patch]
* [attachment:trac_12142-doctest.patch]
* [attachment:trac_12142-remove_cinit.patch]
--
Comment (by pbruin):
The next patch removes the Cython constructor `__cinit__()`, which is
unnecessary since it just sets an attribute to NULL which is already
guaranteed to be NULL. Actually, it just comments it out with an
explanation for future reference. This should fix the remaining doctest
failure and may give another slight speed improvement.
(I'm leaving this as "positive_review" since I can't set it back to
"needs_review" immediately. The change is not entirely trivial, though.)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12142#comment:16>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
