#13409: Addition of vectors over a finite field GF(q) with q>2^16 and q odd can
be
much faster
-----------------------------+----------------------------------------------
Reporter: mderickx | Owner: tbd
Type: PLEASE CHANGE | Status: new
Priority: major | Milestone: sage-5.4
Component: PLEASE CHANGE | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------------------------
The following example shows that adding two random vectors is more then a
factor 10 slower then adding polynomials of the same length. It should be
possible to achieve the same speed.
{{{
K=GF(47^4,'a')
for i in range(1,15):
deg=2^i
V=VectorSpace(K,deg)
L.<x>=K[]
a_vec,b_vec=V.random_element(),V.random_element()
a_pol,b_pol=L(a_vec.list()),L(b_vec.list())
print "add",deg
timeit("a_vec+b_vec")
timeit("a_pol+b_pol")
}}}
{{{
add 2
625 loops, best of 3: 17 µs per loop
625 loops, best of 3: 1.49 µs per loop
add 4
625 loops, best of 3: 33.6 µs per loop
625 loops, best of 3: 2.23 µs per loop
add 8
625 loops, best of 3: 63 µs per loop
625 loops, best of 3: 3.68 µs per loop
add 16
625 loops, best of 3: 128 µs per loop
625 loops, best of 3: 6.7 µs per loop
add 32
625 loops, best of 3: 257 µs per loop
625 loops, best of 3: 14 µs per loop
add 64
625 loops, best of 3: 503 µs per loop
625 loops, best of 3: 26.9 µs per loop
add 128
625 loops, best of 3: 1.03 ms per loop
625 loops, best of 3: 62.9 µs per loop
add 256
125 loops, best of 3: 2.05 ms per loop
625 loops, best of 3: 134 µs per loop
add 512
125 loops, best of 3: 4.19 ms per loop
625 loops, best of 3: 276 µs per loop
add 1024
25 loops, best of 3: 8.42 ms per loop
625 loops, best of 3: 559 µs per loop
add 2048
25 loops, best of 3: 16.9 ms per loop
625 loops, best of 3: 1.14 ms per loop
add 4096
25 loops, best of 3: 34.7 ms per loop
125 loops, best of 3: 2.13 ms per loop
add 8192
5 loops, best of 3: 72.1 ms per loop
125 loops, best of 3: 4.07 ms per loop
add 16384
5 loops, best of 3: 138 ms per loop
25 loops, best of 3: 9.23 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13409>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
