Opened 9 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)

trac_8109-lzz_pEX.patch (83.8 KB) - added by ylchapuy 9 years ago.
needs #7841 (I guess)
trac_8109-lzz_pEX-part2.patch (9.5 KB) - added by ylchapuy 9 years ago.
use both patches
trac_8109-lzz_pEX-part3.patch (20.9 KB) - added by ylchapuy 9 years ago.
trac_8109-lzz_pEX-all_in_one.patch (107.7 KB) - added by ylchapuy 9 years ago.
replacing all previous ones
trac_8109-lzz_pEX-copyrights.patch (7.4 KB) - added by ylchapuy 9 years ago.

Download all attachments as: .zip

Change History (19)

Changed 9 years ago by ylchapuy

needs #7841 (I guess)

comment:1 follow-up: Changed 9 years ago by ylchapuy

  • 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 9 years ago by ylchapuy

  • Status changed from new to needs_review

Replying to ylchapuy:

warning: there is no test (yet) for checking that the modulus is < NTL_SP_BOUND

I must be tired... there is a check, it's done in the lzz_p class.

I guess this one is ready for review then. I will open another ticket to do the same as #7841 latter.

Changed 9 years ago by ylchapuy

use both patches

comment:3 Changed 9 years ago by ylchapuy

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 9 years ago by roed

  • 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 9 years ago by ylchapuy

  • Status changed from needs_review to needs_work

comment:6 follow-up: Changed 9 years ago by 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?

Changed 9 years ago by ylchapuy

Changed 9 years ago by ylchapuy

replacing all previous ones

comment:7 in reply to: ↑ 6 Changed 9 years ago by ylchapuy

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 9 years ago by ylchapuy

comment:8 Changed 9 years ago by ylchapuy

  • Authors set to Yann Laigle-Chapuy
  • 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 9 years ago by malb

  • 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 johanbosman

The patch needs to be rebased as well.

comment:11 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.