Ticket #12177: toom.py

File toom.py, 779 bytes (added by malb, 10 years ago)

proof of concept

Line 
1def gen_matrix(p, k, n):
2    return [random_matrix(GF(p), n, n) for i in range(k)]
3
4def m_mul_pol_naive(A, B):
5    C = [matrix(A[0].base_ring(),A[0].nrows(),B[0].ncols()) for _ in range(len(A)+len(B)-1)]
6    for i in range(len(A)):
7        for j in range(len(B)):
8            C[i+j] += A[i]*B[j]
9    return C
10
11def m_mul_toom(A,B):
12    m = A[0].nrows()
13    n = B[0].ncols()
14    l = len(A)+len(B)-1
15    K = A[0].base_ring()
16
17    FWD = Matrix(K, l, l, [K(i**j) for i in range(l) for j in range(l)])
18    BCK = ~FWD
19
20    AY = [sum(FWD[i,j]*A[j] for j in range(len(A))) for i in range(l)]
21    BY = [sum(FWD[i,j]*B[j] for j in range(len(B))) for i in range(l)]
22
23    Y = [AY[i]*BY[i] for i in range(l)]
24
25
26
27    Y = [sum(BCK[i,j]*Y[j] for j in range(l)) for i in range(l)]
28
29
30    return Y
31