Opened 10 years ago
Closed 8 years ago
#12142 closed enhancement (fixed)
Speed up PARI finite field operations
Reported by: | johanbosman | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-5.12 |
Component: | basic arithmetic | Keywords: | |
Cc: | mderickx, jpflori | Merged in: | sage-5.12.beta3 |
Authors: | Peter Bruin | Reviewers: | Jean-Pierre Flori |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14817, #14818, #14832, #14833 | Stopgaps: |
Description (last modified by )
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:
Attachments (6)
Change History (30)
comment:1 Changed 10 years ago by
- Cc pbruin added
comment:2 Changed 9 years ago by
- Cc mderickx added
comment:3 Changed 9 years ago by
- Cc jpflori added
comment:4 Changed 8 years ago by
- Cc pbruin removed
I have been working on an interface to PARI's implementation of finite fields (t_FFELT
). Like for the other interfaces (except the existing PARI polmod implementation), the field class is written in Python and the element class in Cython. I hope to upload a patch soon after cleaning up the documentation and fixing a minor problem.
The speed improvement for addition and multiplication relative to the current implementation appears to vary roughly from a factor 3 to a factor 12, depending on the size of the field.
For small fields, this PARI interface is (of course) much slower than Givaro (a factor 4-6 for F_{3^{10}}). For fields of characteristic 2, it is slower than NTL+gf2x, but the difference is not that dramatic.
comment:5 Changed 8 years ago by
- Dependencies set to #14817, #14818, #14832, #14833
This ticket led to several other patches, which I put into separate tickets; see the list of dependencies. The dependence on #14817 is optional.
A patch for this ticket is now practically ready.
comment:6 Changed 8 years ago by
- Work issues set to conversion from/to Singular
The attached patch implements a new class FiniteField_pari_ffelt
and associated element class FiniteFieldElement_pari_ffelt
. There is currently one doctest failure, related to conversion from and to Singular.
Changed 8 years ago by
comment:7 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
- Work issues conversion from/to Singular deleted
OK, converting between FiniteFieldElement
and Singular was an easy generalisation of existing code. I will try to make a small table comparing the performance of the various implementations. In the meantime this is ready to be reviewed.
comment:8 Changed 8 years ago by
Here are some timings for addition and multiplication in the various implementations:
x, y random elements of a field of p^n elements all times in microseconds Addition: %timeit -c -r 1 x + y (p, n) ntl/gf2e givaro pari_ffelt pari_mod (2, 15) 0.85 0.45 0.95 15.1 (2, 5000) 1.06 ---- 1.84 3300 (3, 10) ---- 0.47 1.14 12.5 (3, 80) ---- ---- 1.75 44 (251, 2) ---- 0.51 1.30 9.0 Multiplication: %timeit -c -r 1 x * y (p, n) ntl/gf2e givaro pari_ffelt pari_mod (2, 15) 1.11 0.61 1.51 22 (2, 1000) 5.0 ---- 61 1060 (3, 10) ---- 0.57 4.0 19 (3, 80) ---- ---- 36 99 (251, 2) ---- 0.56 1.69 12.1
comment:9 Changed 8 years ago by
- Status changed from needs_review to needs_work
Initialisation of finite field elements is too slow, and computing a/b raises a ZeroDivisionError
if a = 0... A fix will be ready soon.
comment:10 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:11 Changed 8 years ago by
- Description modified (diff)
comment:12 Changed 8 years ago by
- Description modified (diff)
comment:13 Changed 8 years ago by
- Description modified (diff)
- Reviewers set to Jean-Pierre Flori
- Status changed from needs_review to positive_review
Patches look fine, doctests pass and there is indeed a very nice speedup.
comment:14 Changed 8 years ago by
For patchbot:
Apply trac_12142-FiniteField_pari_ffelt.improved.patch, trac_12142-singular_conversion.patch, trac_12142-reviewer.patch
comment:15 Changed 8 years ago by
Apply trac_12142-FiniteField_pari_ffelt.improved.patch, trac_12142-singular_conversion.patch, trac_12142-reviewer.patch
comment:16 Changed 8 years ago by
- Description modified (diff)
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.
Changed 8 years ago by
comment:17 Changed 8 years ago by
- Status changed from positive_review to needs_work
comment:18 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:19 follow-up: ↓ 23 Changed 8 years ago by
- Status changed from needs_review to positive_review
This change looks ok to me, and is very well documented.
I did not really pay attention to the doctests missing as you were copying from a large previous Sage file. Maybe we could take this opportunity to fix it as well and so increase coverage.
comment:20 Changed 8 years ago by
- Description modified (diff)
- Milestone changed from sage-5.11 to sage-5.12
- Summary changed from Speed up Pari finite field operations to Speed up PARI finite field operations
comment:21 Changed 8 years ago by
comment:22 Changed 8 years ago by
Yes, it works and there are doctests. Finite field elements are not implemented as type gen
(as in libs/pari/gen.pyx
), so the fact that pickling does not work for a gen
that happens to be a t_FFELT
does not affect this ticket.
comment:23 in reply to: ↑ 19 Changed 8 years ago by
Replying to jpflori:
I did not really pay attention to the doctests missing as you were copying from a large previous Sage file. Maybe we could take this opportunity to fix it as well and so increase coverage.
Actually the doctest coverage of all files in sage/rings/finite_rings
is 100%, except integer_mod.pyx
, which has a coverage of only 99/150 functions. Apart from that, I think I saw one or two colons that should be double colons. I don't think it is really worth the trouble to spend time on that in this ticket.
comment:24 Changed 8 years ago by
- Merged in set to sage-5.12.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
Just a reminder for myself, it would also be nice to have a common cython interface to deal with finite fields elements, surely using templates as for polynomials.