Fast Loop с умножением NTL
Я программирую с использованием C ++ и библиотеки NTL, но с помощью профиля код ниже медленно, когда поле galois $GF(2^q)$ иметь q>= 8,
Как я смогу ускорить этот код без использования параллельного программирования.
void modKeyGenPrs(list<mat_GF2E>& Prs, list<mat_GF2E> Lst, mat_GF2E L1, mat_GF2E L2)
{
mat_GF2E L1_trans = transpose(L1);
for (int i=0; i<m; i++)
{
mat_GF2E sum;
sum.SetDims(n, n);
list<mat_GF2E>::const_iterator i_lst;
int j=0;
for( i_lst = Lst.begin(); i_lst != Lst.end(); i_lst++)
{
sum = sum + (L2[i][j]*(L1_trans*(*i_lst)*L1));
j = j + 1;
}
Prs.push_back(sum);
}
}
Решение
Я вижу два момента:
- Похоже, ваши списки имеют постоянный размер
n, так что вы можете использовать вектор (как уже упоминалось).
Это тоже хорошо, так как вы не можете выйти за пределы индексаjи код становится более читабельным. Но я не думаю, что это сильно ускорит работу. - Вы делаете матричное умножение с 3 матрицами, и вы делаете это
n^2раз. Но вы получаете толькоnразличные продукты, так что вы можете использовать это снова. Это должно выглядеть следующим образом
void modKeyGenPrs(list<mat_GF2E>& Prs, list<mat_GF2E> Lst, mat_GF2E L1, mat_GF2E L2)
{
// Precompute here
mat_GF2E L1_trans = transpose(L1);
Vec<mat_GF2E> prods;
prods.SetLenght(n);
for( i_lst = Lst.begin(); i_lst != Lst.end(); i_lst++)
{
prod[i_lst] = (L1_trans*(*i_lst)*L1);
}
// compute the rest here
for (int i=0; i<m; i++)
{
mat_GF2E sum;
sum.SetDims(n, n);
list<mat_GF2E>::const_iterator i_lst;
int j=0;
for( i_lst = Lst.begin(); i_lst != Lst.end(); i_lst++)
{
sum = sum + (L2[i][j]*(prod[i_lst]);
j = j + 1;
}
Prs.push_back(sum);
}
}
уведомление: Я использовал переменную n, как вы делаете в своем коде, но я не знаю, откуда он. также переменная m,
Другие решения