#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:
--------------------------------------------------+-------------------------
Changes (by jpflori):
* status: needs_review => positive_review
* reviewer: => Jean-Pierre Flori
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]
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].
--
Comment:
Patches look fine, doctests pass and there is indeed a very nice speedup.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12142#comment:13>
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.
