Addition of vectors over a finite field GF(q) with q>2^16 and q odd can be much faster

[koffie]

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

Component: linear algebra

Reviewer: Travis Scrimshaw

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

[mezzarobba]

comment:4

With Sage 6.2.beta3:

add 2
625 loops, best of 3: 1.09 µs per loop
625 loops, best of 3: 1.31 µs per loop
add 4
625 loops, best of 3: 1.54 µs per loop
625 loops, best of 3: 1.65 µs per loop
add 8
625 loops, best of 3: 2.63 µs per loop
625 loops, best of 3: 2.77 µs per loop
add 16
625 loops, best of 3: 4.83 µs per loop
625 loops, best of 3: 4.88 µs per loop
add 32
625 loops, best of 3: 9.41 µs per loop
625 loops, best of 3: 9.81 µs per loop
add 64
625 loops, best of 3: 18.2 µs per loop
625 loops, best of 3: 19.5 µs per loop
add 128
625 loops, best of 3: 36.6 µs per loop
625 loops, best of 3: 44 µs per loop
add 256
625 loops, best of 3: 82.5 µs per loop
625 loops, best of 3: 98.3 µs per loop
add 512
625 loops, best of 3: 157 µs per loop
625 loops, best of 3: 213 µs per loop
add 1024
625 loops, best of 3: 316 µs per loop
625 loops, best of 3: 412 µs per loop
add 2048
625 loops, best of 3: 661 µs per loop
625 loops, best of 3: 868 µs per loop
add 4096
625 loops, best of 3: 1.39 ms per loop
125 loops, best of 3: 1.83 ms per loop
add 8192
125 loops, best of 3: 2.94 ms per loop
125 loops, best of 3: 4.53 ms per loop
add 16384
125 loops, best of 3: 5.48 ms per loop
25 loops, best of 3: 8.79 ms per loop

[tscrim]

Reviewer: Travis Scrimshaw