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

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^сдвиг). Есть ли сложный способ удалить этот фактор, работающий с десятичными цифрами? Даже с коэффициентом корректировки кажется, что это будет быстрее - почему бы стандартным библиотекам не использовать это против divide и mod?

Answer 1

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

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

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

Answer 2

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

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.
Разделить диапазон 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 

Затем разделить длинный номер к продуктам вместо деления на г. Каждая итерация даст остаток (меньше 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).