ускорение «базового преобразования» для больших целых чисел

Question

Я использую алгоритм базового преобразования для генерации перестановки из большого целого числа (разбитого на 32-битные слова).

Я использую для этого относительно стандартный алгоритм:

/* N = count,K is permutation index (0..N!-1) A[N] contains 0..N-1 */
i = 0;
while (N > 1) {
   swap A[i] and A[i+(k%N)]
   k = k / N
   N = N - 1
   i = i + 1
}

К сожалению, деление и модуль каждой итерации складываются, особенно переходя к большим целым числам - но, похоже, я мог бы просто использовать умножение!

/* As before, N is count, K is index, A[N] contains 0..N-1 */
/* Split is arbitrarily 128 (bits), for my current choice of N */
/* "Adjust" is precalculated: (1 << Split)/(N!) */
a = k*Adjust; /* a can be treated as a fixed point fraction */
i = 0;
while (N > 1) {
   a = a*N;  
   index = a >> Split;         
   a = a & ((1 << Split) - 1);  /* actually, just zeroing a register */       
   swap A[i] and A[i+index]
   N = N - 1
   i = i + 1
}

Это лучше, но делать большие целочисленные умножения все еще вяло.

Вопрос 1:
Есть ли способ сделать это быстрее?

Например. Поскольку я знаю, что N * (N-1) меньше 2 ^ 32, могу ли я вытащить эти числа из одного слова и объединить их в «остатки»?
Или есть способ модифицировать аритетический декодер, чтобы вытащить индикаторы по одному?

Вопрос 2:
Ради любопытства - если я использую умножение, чтобы преобразовать число в основание 10 без корректировки, то результат умножается на (10 ^ цифр / 2 ^ смещение). Есть ли хитрый способ удалить этот фактор, работая с десятичными цифрами? Даже с учетом поправочного коэффициента кажется, что это будет быстрее - почему бы стандартным библиотекам не использовать этот метод против разделения и мода?

Answer 1

Видя, что вы говорите о числах, таких как 2 ^ 128 / (N!), Кажется, что в вашей задаче N будет довольно маленьким (N <35 согласно моим расчетам).Я предлагаю взять оригинальный алгоритм в качестве отправной точки;Сначала переключите направление цикла: </p>

i = 2;
while (i < N) {
    swap A[N - 1 - i] and A[N - i + k % i]
       k = k / i
       i = i + 1
}

Теперь измените цикл, чтобы сделать несколько перестановок за одну итерацию.Я предполагаю, что скорость деления одинакова независимо от числа i, при условии, что i <2 ^ 32. <br>Разделить диапазон 2 ... N-1 на поддиапазоны так, чтобы произведение чисел в каждомподдиапазон меньше 2 ^ 32:

2, 3, 4, ..., 12: product is 479001600
13, 14, ..., 19:  product is 253955520
20, 21, ..., 26:  product is 3315312000
27, 28, ..., 32:  product is 652458240
33, 34, 35:       product is 39270

Затем разделите длинное число k на произведения вместо деления на i.Каждая итерация даст остаток (менее 2 ^ 32) и меньшее число k.Когда у вас есть остаток, вы можете работать с ним во внутреннем цикле, используя оригинальный алгоритм;который теперь будет быстрее, потому что он не требует длинного деления.
Вот некоторый код:

static const int rangeCount = 5;
static const int rangeLimit[rangeCount] = {13, 20, 27, 33, 36};
static uint32_t rangeProduct[rangeCount] = {
    479001600,
    253955520,
    3315312000,
    652458240,
    39270
};

for (int rangeIndex = 0; rangeIndex < rangeCount; ++rangeIndex)
{
    // The following two lines involve long division;
    // math libraries probably calculate both quotient and remainder
    // in one function call
    uint32_t rangeRemainder = k % rangeProduct[rangeIndex];
    k /= rangeProduct[rangeIndex];

    // A range starts where the previous range ended
    int rangeStart = (rangeIndex == 0) ? 2 : rangeLimit[rangeIndex - 1];

    // Iterate over range
    for (int i = rangeStart; i < rangeLimit[rangeIndex] && i < n; ++i)
    {
        // The following two lines involve a 32-bit division;
        // it produces both quotient and remainder in one Pentium instruction
        int remainder = rangeRemainder % i;
        rangeRemainder /= i;
        std::swap(permutation[n - 1 - i], permutation[n - i + remainder]);
    }
}

Конечно, этот код можно расширить до более чем 128 бит.
Другая оптимизацияможет включать извлечение степеней 2 из произведений диапазонов;это может добавить небольшое ускорение, увеличив дальность.Не уверен, стоит ли это (возможно, для больших значений N, например, N = 1000).

Answer 2

Не знаю об алгоритмах, но те, которые вы используете, кажутся довольно простыми, поэтому я не понимаю, как можно оптимизировать алгоритм.

Вы можете использовать альтернативные подходы:

• использовать ASM (ассемблер) - из моего опыта, после долгого времени, пытавшегося выяснить, как должен быть написан определенный алгоритм в ASM, он оказался медленнее, чем версия, сгенерированная компилятором :) Возможно, потому что компилятор также знает, как расположить код так, чтобы кэш ЦП был более эффективным, и / или какие инструкции на самом деле быстрее и в каких ситуациях (это было в GCC / Linux).
• использовать мультиобработку:
  • сделайте ваш алгоритм многопоточным и убедитесь, что вы используете то же количество потоков, что и количество доступных ядер процессора (в настоящее время большинство процессоров имеют несколько ядер / многопоточность)
  • сделает ваш алгоритм способным работать на нескольких машинах в сети и придумать способ отправки этих чисел на машины в сети, чтобы вы могли использовать их мощность процессора.