Opened 10 years ago
Last modified 5 years ago
#8109 needs_work enhancement
wrap NTL's lzz_pE and lzz_pEX and use them
Reported by: | ylchapuy | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | algebra | Keywords: | ntl |
Cc: | Merged in: | ||
Authors: | Yann Laigle-Chapuy | Reviewers: | roed |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This should fasten polynomial arithmetic over finite fields of small characteristic.
Attachments (5)
Change History (19)
Changed 10 years ago by
comment:1 follow-up: ↓ 2 Changed 10 years ago by
- Keywords ntl added
- Milestone changed from sage-wishlist to sage-4.3.2
Preliminary version.
note: this is mostly a copy of existing files for wrapping ZZ_pE and ZZ_pEX with 'sed s/ZZ/zz/g' applied.
warning: there is no test (yet) for checking that the modulus is < NTL_SP_BOUND
still, doctests pass and here are some results:
sage: c=ntl.zz_pEContext(ntl.zz_pX([1,1,1,1,1], 19800713)) sage: a = ntl.zz_pE([3,2], c); b = ntl.zz_pE([1,2], c) sage: f = ntl.zz_pEX([a, b, b]) sage: p = f**123 sage: q = p+f**77+f sage: sage: C=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1,1,1], 19800713)) sage: A = ntl.ZZ_pE([3,2], C); B = ntl.ZZ_pE([1,2], C) sage: F = ntl.ZZ_pEX([A, B, B]) sage: P = F**123 sage: Q = P+F**77+F sage: sage: %timeit p+q 625 loops, best of 3: 59.6 µs per loop sage: %timeit P+Q 625 loops, best of 3: 180 µs per loop sage: sage: %timeit p*q 125 loops, best of 3: 2.62 ms per loop sage: %timeit P*Q 125 loops, best of 3: 5.65 ms per loop sage: sage: %timeit p.gcd(q) 125 loops, best of 3: 7.28 ms per loop sage: %timeit P.gcd(Q) 5 loops, best of 3: 62.5 ms per loop sage: sage: %timeit p**17 5 loops, best of 3: 58 ms per loop sage: %timeit P**17 5 loops, best of 3: 129 ms per loop
comment:2 in reply to: ↑ 1 Changed 10 years ago by
- Status changed from new to needs_review
comment:3 Changed 10 years ago by
Finally, this is such a small patch that I add it here. With both patches applied, the default implementation for polynomial ring is now based on NTL, and uses type ZZ or lzz depending on the characteristic (tested against NTL_SP_BOUND).
comment:4 Changed 10 years ago by
- Reviewers set to roed
I'll review this. I'm working on multiple related things actually: improving finite fields (which I'm thinking of doing with a new templating class) and p-adic polynomials.
comment:5 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:6 follow-up: ↓ 7 Changed 10 years ago by
I see that you changed it to "needs work." One thing I noticed looking at the patch was that sage/libs/ntl/ntl_lzz_decl.pxd seems generally broken: shouldn't those be zz_p and lzz_p, not zz and lzz?
Changed 10 years ago by
comment:7 in reply to: ↑ 6 Changed 10 years ago by
Replying to roed:
I see that you changed it to "needs work." One thing I noticed looking at the patch was that sage/libs/ntl/ntl_lzz_decl.pxd seems generally broken: shouldn't those be zz_p and lzz_p, not zz and lzz?
It's even worse than that, this file just shouldn't exist :) The last patch replaces all previous ones and should be almost ready for review. I will just check and address the comments made on #7841 before.
Changed 10 years ago by
comment:8 Changed 10 years ago by
- Status changed from needs_work to needs_review
Apply only:
- trac_8109-lzz_pEX-all_in_one.patch
- trac_8109-lzz_pEX-copyrights.patch
in this order.
comment:9 Changed 10 years ago by
- Status changed from needs_review to needs_work
I get doctest failures on sage.math:
sage -t devel/sage/sage/graphs/graph_list.py # 0 doctests failed sage -t devel/sage/sage/schemes/elliptic_curves/ell_curve_isogeny.py # Killed/crashed sage -t devel/sage/sage/libs/ntl/ntl_lzz_pX.pyx # 5 doctests failed sage -t devel/sage/sage/libs/ntl/ntl_lzz_pEX_linkage.pxi # 3 doctests failed
Looks like a 64-bit thing?
sage -t devel/sage/sage/libs/ntl/ntl_lzz_pEX_linkage.pxi ********************************************************************** File "/mnt/usb1/scratch/malb/sage-4.3.3/devel/sage-main/sage/libs/ntl/ntl_lzz_pEX_linkage.pxi", line 178: sage: (1+a+a^2)*x - (1+x+x^2) Expected: 1152921504606847008*x^2 + (a^2 + a)*x + 1152921504606847008 Got: 1030*x^2 + (a^2 + a)*x + 1030 ********************************************************************** File "/mnt/usb1/scratch/malb/sage-4.3.3/devel/sage-main/sage/libs/ntl/ntl_lzz_pEX_linkage.pxi", line 189: sage: -x Expected: 1152921504606847008*x Got: 1030*x ********************************************************************** File "/mnt/usb1/scratch/malb/sage-4.3.3/devel/sage-main/sage/libs/ntl/ntl_lzz_pEX_linkage.pxi", line 308: sage: (a+1+x).xgcd(a+x) Expected: (1, 1, 1152921504606847008) Got: (1, 1, 1030) **********************************************************************
comment:10 Changed 8 years ago by
The patch needs to be rebased as well.
comment:11 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:12 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:13 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:14 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
needs #7841 (I guess)