Sage: Ticket #4302: [with patch, positive review] improve modular composition in GF(2)[x] and GF(2)[x]
https://trac.sagemath.org/ticket/4302
<p>
Here is a toy implementation of polynomial modular composition over GF(2). It implements
Brent-Kung's Algorithm 2.1 (Fast Algorithms for Manipulation Formal Power Series, JACM 1978).
</p>
<pre class="wiki"># compute f(g) mod h
def ModularComposition(f,g,h,k=None):
print "enter ModularComposition", f.degree(), g.degree(), h.degree()
t = cputime()
R = h.parent()
n = h.degree()
if k is None:
k = ceil(Integer(n+1).sqrt_approx())
l = ceil((f.degree() + 1) / k)
# first compute g^j mod h, 2 <= j < k
G = Matrix(GF(2),n,k)
gpow = R(1)
for j in range(0, k):
# gpow = g^j mod h
row = gpow.coeffs()
if len(row)<n:
row.extend([R(0) for _ in range(n - len(row))])
G.set_column(j, row)
gpow = (gpow * g) % h # we'll need g^k below
print "Creating G took", cputime(t)
t = cputime()
# split f in chunks of degree < k
F = Matrix(GF(2),k,l)
row = f.coeffs()
if len(row)<k*l:
row.extend([R(0) for _ in range(k*l - len(row))])
for j in range(0, l):
F.set_column(j, row[j*k:j*k+k])
print "Creating F took", cputime(t)
t = cputime()
H = G * F # this is the most time-computing step, but M4RI is fast!
print "Computing H took", cputime(t)
t = cputime()
# H is a n x l matrix
# now H[i,j] = sum(G[i,m]*F[m,j], m=0..k-1)
# = sum(g^m[i] * f[j*k+m], m=0..k-1)
# where g^m[i] is the coefficient of degree i in g^m
# and f[j*k+m] is the coefficient of degree j*k+m in f
# thus f[j*k+m]*g^m[i] should be multiplied by g^(j*k)
# gpow = (g^k) % h
x = h.variables()[0]
res = R(0)
j = l - 1
H = H.transpose()
while j >= 0:
res = (res * gpow) % h
# res = res + R([H[j,i] for i in range(0,n)])
res = res + R(H.submatrix(j,0,1,n).list())
j = j - 1
print "Forming result took", cputime(t)
sys.stdout.flush()
return res
# computes x^(2^r) mod f
def ModCompPower (f, r):
l = r.digits()
l.reverse()
n = len(l)
g = f.variables()[0]
for i in range(n):
g = ModularComposition(g,g,f)
if l[i] == 1:
g = (g * g) % f
return g
</pre><p>
The following benchmark gives on a 2.4Ghz Core 2:
</p>
<pre class="wiki">sage: r=1279
sage: time a = ModCompPower(R(x^r+x+1), r)
enter ModularComposition 1 1 1279
Creating G took 3.948399
Creating F took 0.00299900000005
Computing H took 0.000999999999976
Forming result took 0.0169980000001
enter ModularComposition 2 2 1279
Creating G took 3.896408
Creating F took 0.004999
Computing H took 0.0
Forming result took 0.018997
enter ModularComposition 4 4 1279
Creating G took 3.802422
Creating F took 0.00300000000004
Computing H took 0.000999999999976
Forming result took 0.018997
enter ModularComposition 16 16 1279
Creating G took 3.208512
Creating F took 0.00299900000005
Computing H took 0.0
Forming result took 0.0169979999999
enter ModularComposition 512 512 1279
Creating G took 2.413633
Creating F took 0.004999
Computing H took 0.00100000000009
Forming result took 0.307953
enter ModularComposition 1202 1202 1279
Creating G took 0.895864
Creating F took 0.00999899999999
Computing H took 0.0
Forming result took 0.787879
enter ModularComposition 1272 1272 1279
Creating G took 0.528921
Creating F took 0.009997
Computing H took 0.000999999999976
Forming result took 0.633905
enter ModularComposition 1275 1275 1279
Creating G took 0.474927
Creating F took 0.00899800000002
Computing H took 0.000999999999976
Forming result took 0.630905
enter ModularComposition 1278 1278 1279
Creating G took 0.533918
Creating F took 0.00799899999993
Computing H took 0.0
Forming result took 0.631904
enter ModularComposition 1277 1277 1279
Creating G took 0.482927
Creating F took 0.00599899999997
Computing H took 0.000999999999976
Forming result took 0.609907
enter ModularComposition 1277 1277 1279
Creating G took 0.563913
Creating F took 0.00899900000002
Computing H took 0.0
Forming result took 0.602908
CPU times: user 24.37 s, sys: 0.79 s, total: 25.16 s
Wall time: 27.67 s
</pre><p>
Several remarks:
</p>
<ul><li>the time spent in M4RI (Computing H) is negligible;
</li><li>the time spent in "Creating G" and "Forming result" is large,
and is even larger when the inputs have small degree! Something strange happens here.
</li></ul><p>
As a comparison, on the same machine, Magma V2.14-8 takes only 0.02s with the following code:
</p>
<pre class="wiki">R<x> := PolynomialRing(GF(2));
/* computes x^(2^r) mod f */
ModCompPower := function(f, r)
l := [];
t := r;
while t ne 0 do
l := Append(l, t mod 2);
t := t div 2;
end while;
g := x;
for i := #l to 1 by -1 do
g := ModularComposition(g,g,f);
if l[i] eq 1 then
g := Modexp(g,2,f);
end if;
end for;
return g;
end function;
> r:=1279; time a:=ModCompPower(x^r+x+1, r);
Time: 0.020
</pre><p>
The challenge is to do better than Magma within Sage.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/4302
Trac 1.1.6malbFri, 17 Oct 2008 01:00:25 GMTsummary changed
https://trac.sagemath.org/ticket/4302#comment:1
https://trac.sagemath.org/ticket/4302#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>[challenge] improve modular composition in GF(2)[x]</em> to <em>[with patch, needs review] improve modular composition in GF(2)[x]</em>
</li>
</ul>
TicketmalbFri, 17 Oct 2008 01:01:59 GMTcc set
https://trac.sagemath.org/ticket/4302#comment:2
https://trac.sagemath.org/ticket/4302#comment:2
<ul>
<li><strong>cc</strong>
<em>robertwb</em> added
</li>
</ul>
<p>
CCing Robert because the patch implements his template idea.
</p>
TicketmalbFri, 17 Oct 2008 01:05:42 GMT
https://trac.sagemath.org/ticket/4302#comment:3
https://trac.sagemath.org/ticket/4302#comment:3
<p>
This is what I sent to Paul earlier about the patch
</p>
<blockquote class="citation">
<p>
I've improved said implementation on my train ride after Sage Days. The result
is faster than Magma but only competitive with NTL. It seems NTL is already
faster than Magma for this problem and that the runtime is dominated by the
construction of the matrices (ntl.GF2X arithmetic mainly) and the recovery of
the result (ntl.GF2X arithmetic mainly). There is room for improvements
w.r.t. the conversion between ntl.GF2X and M4RI but I didn't bother yet
because ntl.GF2X arithmetic seems to be the main bottleneck for now. Note
that matrix multiplication takes up only a tiny fraction of the overall
runtime, it is almost negligible.
</p>
<p>
Maybe, once we switch to the GF2X library things will look different enough to
motivate a better tuned conversion routine?
</p>
</blockquote>
<pre class="wiki">f = R.random_element(30000)
g = R.random_element(30000)
h = R.random_element(30000*10)
</pre><pre class="wiki">%time
set_verbose(1)
_ = f.modular_composition(g,h)
verbose 1 (1: , <module>) G 548 x 299999 16.331 s
verbose 1 (1: , <module>) F 55 x 548 0.000 s
verbose 1 (1: , <module>) H 55 x 299999 0.230 s
verbose 1 (1: , <module>) Res 6.359 s
CPU time: 22.98 s, Wall time: 23.42 s
</pre><pre class="wiki">%time _ = f.modular_composition(g,h,'ntl')
verbose 1 (1: , <module>) NTL 23.998 s
CPU time: 24.07 s, Wall time: 24.72 s
</pre><pre class="wiki">fm = f._magma_()
gm = g._magma_()
hm = h._magma_()
t = magma.cputime()
_ = fm.ModularComposition(gm,hm)
magma.cputime(t)
83.810000000000002
</pre>
TicketzimmermaFri, 17 Oct 2008 06:33:55 GMTcc changed
https://trac.sagemath.org/ticket/4302#comment:4
https://trac.sagemath.org/ticket/4302#comment:4
<ul>
<li><strong>cc</strong>
<em>zimmerma@…</em> added
</li>
</ul>
<p>
Martin, I have problems trying your patch to 3.1.3:
</p>
<pre class="wiki">Building sage/rings/polynomial/polynomial_gf2x.cpp because it depends on sage/rings/polynomial/polynomial_gf2x.pyx.
python2.5 `which cython` --embed-positions --incref-local-binop -I/usr/local/sage-3.1.3/sage/devel/sage-main -o sage/rings/polynomial/polynomial_gf2x.cpp sage/rings/polynomial/polynomial_gf2x.pyx
Error converting Pyrex file to C:
------------------------------------------------------------
...
from sage.libs.ntl.ntl_GF2_decl cimport GF2_c
from sage.libs.ntl.ntl_ZZ_decl cimport ZZ_c
^
------------------------------------------------------------
</pre><p>
Should I apply other patches before?
</p>
TicketmalbFri, 17 Oct 2008 09:31:57 GMT
https://trac.sagemath.org/ticket/4302#comment:5
https://trac.sagemath.org/ticket/4302#comment:5
<p>
ooop, I forgot to mention that this patch depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/4304" title="defect: [with patch, positive review] split up NTL's decl.pxi (closed: fixed)">#4304</a>
</p>
TicketzimmermaFri, 17 Oct 2008 11:16:48 GMT
https://trac.sagemath.org/ticket/4302#comment:6
https://trac.sagemath.org/ticket/4302#comment:6
<p>
I have applied both patches, and done sage -br, but modular_composition is not defined (with sage-3.1.4):
</p>
<pre class="wiki">sage: R=PolynomialRing(GF(2),x)
sage: f=x^2+1
sage: f.modular_composition
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/users/cacao/zimmerma/.sage/temp/achille.loria.fr/7660/_users_cacao_zimmerma__sage_init_sage_0.py in <module>()
----> 1
2
3
4
5
AttributeError: 'SymbolicArithmetic' object has no attribute 'modular_composition'
</pre>
TicketmalbFri, 17 Oct 2008 11:28:33 GMT
https://trac.sagemath.org/ticket/4302#comment:7
https://trac.sagemath.org/ticket/4302#comment:7
<p>
Hi, you didn't declare 'x' to be a polynomial over GF(2). Try:
</p>
<pre class="wiki">sage: P.<x> = PolynomialRing(GF(2))
</pre>
TicketzimmermaFri, 17 Oct 2008 12:24:11 GMT
https://trac.sagemath.org/ticket/4302#comment:8
https://trac.sagemath.org/ticket/4302#comment:8
<p>
Yes I did (but did forget to copy/paste it):
</p>
<pre class="wiki">----------------------------------------------------------------------
| SAGE Version 3.1.4, Release Date: 2008-10-16 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: P.<x> = PolynomialRing(GF(2))
sage: f=x^2+1
sage: f.modular_composition()
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/users/cacao/zimmerma/.sage/temp/achille.loria.fr/8623/_users_cacao_zimmerma__sage_init_sage_0.py in <module>()
----> 1
2
3
4
5
</pre><p>
Maybe it is because I applied the current patch before that of <a class="closed ticket" href="https://trac.sagemath.org/ticket/4304" title="defect: [with patch, positive review] split up NTL's decl.pxi (closed: fixed)">#4304</a>. However, I just did "touch" on all
files from the current patch, then "sage -br" again, and I still get the above.
</p>
TicketmalbFri, 17 Oct 2008 12:33:29 GMT
https://trac.sagemath.org/ticket/4302#comment:9
https://trac.sagemath.org/ticket/4302#comment:9
<p>
Maybe you can start with vanilla 3.1.3 again (rm spkgs/installed/sage-3.1.3.spkg; make) and apply the patches again in order? Is there a file called polynomial_gf2x.pyx in sage/rings/polynomial ? I'll be afk for a couple of days btw.
</p>
TicketzimmermaFri, 17 Oct 2008 19:29:23 GMT
https://trac.sagemath.org/ticket/4302#comment:10
https://trac.sagemath.org/ticket/4302#comment:10
<p>
I did start from vanilla 3.1.3 again, applied the patches in the right order, but still get the
same error:
</p>
<pre class="wiki">----------------------------------------------------------------------
| SAGE Version 3.1.4, Release Date: 2008-10-16 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: P.<x> = PolynomialRing(GF(2), x)
sage: f = x^7 + x + 1
sage: f.modular_composition()
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/users/cacao/zimmerma/.sage/temp/achille.loria.fr/16284/_users_cacao_zimmerma__sage_init_sage_0.py in <module>()
----> 1
2
3
4
5
AttributeError: 'sage.rings.polynomial.polynomial_modn_dense_ntl.Po' object has no attribute 'modular_composition'
</pre><p>
In particular I don't see a "modular_composition" method for polynomial_modn_dense_ntl,
but only for Polynomial_GF2X, and polynomial_modn_dense_ntl, does not seem to inherit from
Polynomial_GF2X:
</p>
<pre class="wiki">sage: type(f)
<type 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_mod_p'>
</pre><p>
How can I define an object of type Polynomial_GF2X? Can someone reproduce Martin's results?
</p>
TicketzimmermaFri, 17 Oct 2008 19:45:46 GMTcc changed
https://trac.sagemath.org/ticket/4302#comment:11
https://trac.sagemath.org/ticket/4302#comment:11
<ul>
<li><strong>cc</strong>
<em>zimmerma</em> added; <em>zimmerma@…</em> removed
</li>
</ul>
TicketmabshoffFri, 17 Oct 2008 22:39:42 GMT
https://trac.sagemath.org/ticket/4302#comment:12
https://trac.sagemath.org/ticket/4302#comment:12
<p>
FYI: With this patch and its dependency applied I get the following failures:
</p>
<pre class="wiki"> sage -t -long devel/sage/sage/schemes/elliptic_curves/padics.py # 1 doctests failed
sage -t -long devel/sage/sage/schemes/elliptic_curves/ell_generic.py # 1 doctests failed
sage -t -long devel/sage/sage/modular/modform/j_invariant.py # 1 doctests failed
sage -t -long devel/sage/sage/libs/ntl/ntl_GF2X_linkage.pxi # 1 doctests failed
sage -t -long devel/sage/sage/libs/ntl/ntl_GF2X.pyx # 1 doctests failed
</pre><p>
I am now testing only <a class="closed ticket" href="https://trac.sagemath.org/ticket/4304" title="defect: [with patch, positive review] split up NTL's decl.pxi (closed: fixed)">#4304</a> to see if the problem is this or the other patch.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketmabshoffFri, 17 Oct 2008 22:41:24 GMTdescription changed
https://trac.sagemath.org/ticket/4302#comment:13
https://trac.sagemath.org/ticket/4302#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/4302?action=diff&version=13">diff</a>)
</li>
</ul>
TicketmabshoffFri, 17 Oct 2008 23:18:57 GMTsummary changed
https://trac.sagemath.org/ticket/4302#comment:14
https://trac.sagemath.org/ticket/4302#comment:14
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] improve modular composition in GF(2)[x]</em> to <em>[with patch, needs work] improve modular composition in GF(2)[x]</em>
</li>
</ul>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/4304" title="defect: [with patch, positive review] split up NTL's decl.pxi (closed: fixed)">#4304</a> by itself is fine, so this one needs work.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketmalbSat, 18 Oct 2008 01:15:38 GMT
https://trac.sagemath.org/ticket/4302#comment:15
https://trac.sagemath.org/ticket/4302#comment:15
<p>
Hi, I started from a vanilla 3.1.3 as follows
</p>
<pre class="wiki">malb@road:~/SAGE/devel/sage$ hg qinit
malb@road:~/SAGE/devel/sage$ hg qimport ntl_decl_refactor.patch
adding ntl_decl_refactor.patch to series file
malb@road:~/SAGE/devel/sage$ hg qpush
applying ntl_decl_refactor.patch
patching file sage/rings/polynomial/polynomial_modn_dense_ntl.pyx
Hunk #4 succeeded at 1277 with fuzz 2 (offset 0 lines).
Now at: ntl_decl_refactor.patch
malb@road:~/SAGE/devel/sage$ hg qimport polynomial_gf2x.patch
adding polynomial_gf2x.patch to series file
malb@road:~/SAGE/devel/sage$ hg qpush
applying polynomial_gf2x.patch
Now at: polynomial_gf2x.patch
malb@road:~/SAGE/devel/sage$ sage -b
</pre><p>
afterwars I do have the modular_composition function available. I'll address the doctest failures as soon as possible if noone else beats me to it.
</p>
TicketzimmermaSat, 18 Oct 2008 08:04:49 GMT
https://trac.sagemath.org/ticket/4302#comment:16
https://trac.sagemath.org/ticket/4302#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/4302#comment:15" title="Comment 15">malb</a>:
</p>
<blockquote class="citation">
<p>
Hi, I started from a vanilla 3.1.3 as follows [...]
</p>
</blockquote>
<p>
Martin, starting from 3.1.4 (which should be ok), I cannot reproduce what you did:
</p>
<pre class="wiki">achille% pwd
/usr/local/sage-3.1.4/sage/devel/sage-main
achille% hg qinit
hg: unknown command 'qinit'
Mercurial Distributed SCM
basic commands:
add add the specified files on the next commit
annotate show changeset information per file line
clone make a copy of an existing repository
commit commit the specified files or all outstanding changes
diff diff repository (or selected files)
export dump the header and diffs for one or more changesets
init create a new repository in the given directory
log show revision history of entire repository or files
merge merge working directory with another revision
parents show the parents of the working dir or revision
pull pull changes from the specified source
push push changes to the specified destination
remove remove the specified files on the next commit
serve export the repository via HTTP
status show changed files in the working directory
update update working directory
use "hg help" for the full list of commands or "hg -v" for details
achille% hg --version
Mercurial Distributed SCM (version 1.0.2)
Copyright (C) 2005-2008 Matt Mackall <mpm@selenic.com> and others
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
</pre>
TicketAlexGhitzaSat, 18 Oct 2008 08:17:21 GMT
https://trac.sagemath.org/ticket/4302#comment:17
https://trac.sagemath.org/ticket/4302#comment:17
<p>
Hi Paul,
</p>
<p>
It seems that Mercurial queues are not enabled on your machine. Try adding the following lines to the file .hgrc in your home directory:
</p>
<pre class="wiki">[extensions]
hgext.mq =
</pre>
TicketmalbSat, 18 Oct 2008 08:21:00 GMT
https://trac.sagemath.org/ticket/4302#comment:18
https://trac.sagemath.org/ticket/4302#comment:18
<p>
Or, this should be equivalent:
</p>
<pre class="wiki">malb@road:~/SAGE/devel/sage$ hg import ntl_decl_refactor.patch
malb@road:~/SAGE/devel/sage$ hg import polynomial_gf2x.patch
malb@road:~/SAGE/devel/sage$ sage -b
</pre>
TicketzimmermaSat, 18 Oct 2008 09:47:43 GMT
https://trac.sagemath.org/ticket/4302#comment:19
https://trac.sagemath.org/ticket/4302#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/4302#comment:18" title="Comment 18">malb</a>:
</p>
<blockquote class="citation">
<p>
Or, this should be equivalent:
</p>
<pre class="wiki">malb@road:~/SAGE/devel/sage$ hg import ntl_decl_refactor.patch
malb@road:~/SAGE/devel/sage$ hg import polynomial_gf2x.patch
malb@road:~/SAGE/devel/sage$ sage -b
</pre></blockquote>
<p>
this is basically what I had done before (but from within sage, and with sage -b inbetween).
Nevertheless, I did exactly that with 3.1.4:
</p>
<pre class="wiki">achille% pwd
/usr/local/sage-3.1.4/sage/devel/sage-main
achille% hg import /tmp/ntl_decl_refactor.patch
applying /tmp/ntl_decl_refactor.patch
patching file sage/rings/polynomial/polynomial_modn_dense_ntl.pyx
Hunk #4 succeeded at 1277 with fuzz 2 (offset 0 lines).
achille% hg import /tmp/polynomial_gf2x.patch
applying /tmp/polynomial_gf2x.patch
achille% sage -b
...
real 33m24.231s
user 32m25.750s
sys 0m37.831s
achille% sage
----------------------------------------------------------------------
| SAGE Version 3.1.4, Release Date: 2008-10-16 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: P.<x> = PolynomialRing(GF(2))
sage: f=x^7+x+1
sage: f.modular_composition()
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/users/cacao/zimmerma/.sage/temp/achille.loria.fr/11076/_users_cacao_zimmerma__\
sage_init_sage_0.py in <module>()
----> 1
2
3
4
5
AttributeError: 'sage.rings.polynomial.polynomial_modn_dense_ntl.Po' object has\
no attribute 'modular_composition'
</pre><p>
Is it possible that the problem happens because I am not in the original build directory,
but in the directory where I did "make install"? However I have successfully applied several
patches in this way before.
</p>
<p>
What else can I do to identify the problem on my side?
</p>
TicketzimmermaSat, 18 Oct 2008 15:42:49 GMT
https://trac.sagemath.org/ticket/4302#comment:20
https://trac.sagemath.org/ticket/4302#comment:20
<p>
After fixing my relocation problems (<a class="closed ticket" href="https://trac.sagemath.org/ticket/4317" title="defect: [with patch; positive review] Fix easy-install.pth after moving Sage (closed: fixed)">#4317</a>) I was able to reproduce Martin's timings.
</p>
<p>
The attached trac_4302_doctest1.patch fixes the doctest failure in ntl_GF2X_linkage.pxi.
Unfortunately I don't know how to fix the other ones.
</p>
TicketzimmermaSat, 18 Oct 2008 16:48:16 GMTattachment set
https://trac.sagemath.org/ticket/4302
https://trac.sagemath.org/ticket/4302
<ul>
<li><strong>attachment</strong>
set to <em>4302_speedup1.patch</em>
</li>
</ul>
TicketzimmermaSat, 18 Oct 2008 16:58:03 GMTcc changed
https://trac.sagemath.org/ticket/4302#comment:21
https://trac.sagemath.org/ticket/4302#comment:21
<ul>
<li><strong>cc</strong>
<em>malb</em> added
</li>
</ul>
<p>
The attached 4302_speedup1.patch should speed up the computation of the G matrix, however it does speed it down instead (I had previous timings similar to those of Martin above):
</p>
<pre class="wiki">sage: R.<x>=GF(2)[]
sage: f = R.random_element(30000)
sage: g = R.random_element(30000)
sage: h = R.random_element(30000*10)
sage: set_verbose(1)
sage: time _ = f.modular_composition(g,h)
verbose 1 (<module>) G 548 x 300000 33.128 s
verbose 1 (<module>) F 55 x 548 0.001 s
verbose 1 (<module>) H 55 x 300000 0.265 s
verbose 1 (<module>) Res 6.406 s
CPU times: user 39.79 s, sys: 0.07 s, total: 39.86 s
</pre><p>
Either GF2X_SqrMod_pre is slower than GF2X_MulMod_pre, or I did something stupid. Could somebody look at my patch?
</p>
TicketzimmermaSat, 18 Oct 2008 20:54:41 GMT
https://trac.sagemath.org/ticket/4302#comment:22
https://trac.sagemath.org/ticket/4302#comment:22
<p>
In fact with the following benchmark 4302_speedup1.patch gives a speedup (<a class="missing wiki">ModCompPower?</a> is defined
above).
</p>
<p>
Without 4302_speedup1.patch:
</p>
<pre class="wiki">sage: r=132049
sage: time a=ModCompPower(x^r+x+1, r)
100.6397
</pre><p>
With 4302_speedup1.patch:
</p>
<pre class="wiki">sage: time a=ModCompPower(x^r+x+1, r)
82.144512
</pre><p>
With NTL:
</p>
<pre class="wiki">sage: time a=ModCompPower(x^r+x+1, r, algorithm='ntl')
86.219893
</pre>
TicketmalbSun, 19 Oct 2008 14:45:26 GMT
https://trac.sagemath.org/ticket/4302#comment:23
https://trac.sagemath.org/ticket/4302#comment:23
<p>
I fixed most doctest failures except one:
</p>
<pre class="wiki">sage -t elliptic_curves/ell_generic.py
File "/home/malb/SAGE/tmp/ell_generic.py", line 2135:
sage: [ len(EllipticCurve(GF(q,'a')(0)).automorphisms()) for q in [2,4,3,9,5,25,7,49]]
Exception raised:
...
TypeError: unsupported operand parent(s) for '-': 'Univariate Polynomial Ring in x over Finite Field of size 2' and 'Finite Field of size 2'
</pre><p>
My trouble is, that it works from the command line:
</p>
<pre class="wiki">sage: [ len(EllipticCurve(GF(q,'a')(0)).automorphisms()) for q in [2,4,3,9,5,25,7,49]]
[2, 24, 2, 12, 2, 6, 6, 6]
</pre><p>
Robert, could that be related to some caching of coercion maps?
</p>
TicketmalbSun, 19 Oct 2008 14:46:07 GMT
https://trac.sagemath.org/ticket/4302#comment:24
https://trac.sagemath.org/ticket/4302#comment:24
<p>
The patch includes Paul's doctest fix but not his speed-improvement, so apply that after the <code>polynomial_gf2x.patch</code>.
</p>
TicketmalbSun, 19 Oct 2008 15:16:49 GMTattachment set
https://trac.sagemath.org/ticket/4302
https://trac.sagemath.org/ticket/4302
<ul>
<li><strong>attachment</strong>
set to <em>polynomial_gf2x.patch</em>
</li>
</ul>
<p>
fixes all known doctest failures
</p>
TicketmalbSun, 19 Oct 2008 15:18:59 GMTsummary changed
https://trac.sagemath.org/ticket/4302#comment:25
https://trac.sagemath.org/ticket/4302#comment:25
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] improve modular composition in GF(2)[x]</em> to <em>[with patch, needs review] improve modular composition in GF(2)[x] and GF(2)[x]</em>
</li>
</ul>
<p>
the updated patch fixes all known doctest failures. The failure was caused by the fact that two GF(2) objects existed such that <code>x.parent() is parent</code> wasn't true anymore. Apply Paul's performance patch after <code>polynomial_gf2x.patch</code>
</p>
TicketmabshoffMon, 20 Oct 2008 12:07:19 GMT
https://trac.sagemath.org/ticket/4302#comment:26
https://trac.sagemath.org/ticket/4302#comment:26
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/4328" title="defect: bug in roots (closed: worksforme)">#4328</a> seems to be caused by this patch.
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketmalbMon, 20 Oct 2008 13:24:29 GMT
https://trac.sagemath.org/ticket/4302#comment:27
https://trac.sagemath.org/ticket/4302#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/4302#comment:26" title="Comment 26">mabshoff</a>:
</p>
<blockquote class="citation">
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/4328" title="defect: bug in roots (closed: worksforme)">#4328</a> seems to be caused by this patch.
</p>
</blockquote>
<p>
I think that was caused by an older version of the patch.
</p>
TicketmalbMon, 20 Oct 2008 16:11:38 GMT
https://trac.sagemath.org/ticket/4302#comment:28
https://trac.sagemath.org/ticket/4302#comment:28
<p>
btw. Robert I think passing <code>object parent</code> to <code>celement_foo()</code> is not a good choice because it assumes structure on <code>parent</code>, e.g. what would one cast to for C attribute access? I'd say it should be a cparent which is some sort of C struct defined in the linkage pxi files? But this can wait until after this patch is applied (because GF2X ignores the parent anyway).
</p>
TicketrobertwbTue, 21 Oct 2008 15:12:43 GMT
https://trac.sagemath.org/ticket/4302#comment:29
https://trac.sagemath.org/ticket/4302#comment:29
<p>
Yep, perhaps something other than parent would be good to pass, though that would make writing the generic classes more complicated. It would also be handy to have generic wrap/unwrap methods that go to and from the native type to a Sage object.
</p>
TicketzimmermaThu, 23 Oct 2008 11:07:12 GMTsummary changed
https://trac.sagemath.org/ticket/4302#comment:30
https://trac.sagemath.org/ticket/4302#comment:30
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] improve modular composition in GF(2)[x] and GF(2)[x]</em> to <em>[with patch, positive review] improve modular composition in GF(2)[x] and GF(2)[x]</em>
</li>
</ul>
<p>
I did apply polynomial_gf2x.patch on a vanilla 3.1.4, after having applied the patch from <a class="closed ticket" href="https://trac.sagemath.org/ticket/4304" title="defect: [with patch, positive review] split up NTL's decl.pxi (closed: fixed)">#4304</a>.
I can reproduce Martin's timings, and I checked that all the doctests above are ok now. Thus I give
a positive review for that patch.
</p>
<p>
Of course somebody should review my own patch, or should we create a separate ticket, so that we can include
Martin's patch?
</p>
TicketmalbThu, 23 Oct 2008 13:48:51 GMT
https://trac.sagemath.org/ticket/4302#comment:31
https://trac.sagemath.org/ticket/4302#comment:31
<p>
Paul, I can review your patch. No need to open another ticket.
</p>
TicketmalbFri, 24 Oct 2008 23:26:03 GMT
https://trac.sagemath.org/ticket/4302#comment:32
https://trac.sagemath.org/ticket/4302#comment:32
<p>
Paul's patch applies cleanly and doctests pass in the rings subdirectory. <strong>positive review</strong>
</p>
TicketmabshoffSun, 26 Oct 2008 00:51:43 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/4302#comment:33
https://trac.sagemath.org/ticket/4302#comment:33
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Merged both patches in Sage 3.2.alpha1
</p>
Ticket