search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.22k stars 424 forks source link

wrap NTL's lzz_pE and lzz_pEX and use them #8109

Open 2c00b582-cfe9-43b9-8124-fec470060704 opened 14 years ago

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago

This should fasten polynomial arithmetic over finite fields of small characteristic.

Component: algebra

Keywords: ntl

Author: Yann Laigle-Chapuy

Reviewer: roed

Issue created by migration from https://trac.sagemath.org/ticket/8109

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago

Attachment: trac_8109-lzz_pEX.patch.gz

needs #7841 (I guess)

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago
comment:1

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
2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago

Changed keywords from none to ntl

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago
comment:2

Replying to @sagetrac-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.

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago

use both patches

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago
comment:3

Attachment: trac_8109-lzz_pEX-part2.patch.gz

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).

roed314 commented 14 years ago

Reviewer: roed

roed314 commented 14 years ago
comment:4

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.

roed314 commented 14 years ago
comment:6

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?

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago

Attachment: trac_8109-lzz_pEX-part3.patch.gz

replacing all previous ones

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago
comment:7

Attachment: trac_8109-lzz_pEX-all_in_one.patch.gz

Replying to @roed314:

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.

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago

Author: Yann Laigle-Chapuy

2c00b582-cfe9-43b9-8124-fec470060704 commented 14 years ago
comment:8

Attachment: trac_8109-lzz_pEX-copyrights.patch.gz

Apply only:

in this order.

malb commented 14 years ago
comment:9

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)
**********************************************************************
1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago
comment:10

The patch needs to be rebased as well.