Быстрый цикл с умножением NTL

Я программирую, используя C++ и библиотеку ntl, но используя профиль, приведенный ниже код работает медленно, когда поле Галуа $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);
    }
}

c++ performance ntl
person user46060    schedule 25.06.2014    source источник
comment
Первым шагом было бы избавиться от std::list и заменить его на std::vector.   -  person filmor    schedule 25.06.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я вижу два момента:

  1. Похоже, ваши списки имеют постоянный размер n, поэтому вы можете использовать вектор (как уже упоминалось). Это тоже хорошо, так как с индексом j нельзя выйти за пределы и код становится более читабельным. Но я не думаю, что это сильно ускорит работу.
  2. Вы делаете матричное умножение с 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.

person AbcAeffchen    schedule 25.06.2014