Для деления по модулю на степени двойки достаточно взять соответствующие младшие биты числа. А существуют ли приемы для быстрого (то есть без циклов и т.п.) нахождения остатка на некоторые константы?
Интересуют алгоритмы для делителей в диапазоне от 16 до 32, например остаток от деления на 20, 24, 28. В общем все равно на что, главное чтобы это было просто, желательно даже без умножений и делений. Делимое — любое целое число в диапазоне unsigned int32.
Здравствуйте, watch-maker, Вы писали:
Здравствуйте, include2h, Вы писали:
I>>Для деления по модулю на степени двойки достаточно взять соответствующие младшие биты числа. А существуют ли приемы для быстрого (то есть без циклов и т.п.) нахождения остатка на некоторые константы?
Например, относительно просто считаются остатки при делении на числа вида 2
k±1.
I>>Интересуют алгоритмы для делителей в диапазоне от 16 до 32, например остаток от деления на 20, 24, 28. В общем все равно на что, главное чтобы это было просто, желательно даже без умножений и делений. Делимое — любое целое число в диапазоне unsigned int32.
В общем случае остаток при делении на константу считается плохо. Обычно сначала вычисляется результат деления нацело, а затем уже он используется для вычисления остатка. Спасает тут то, что деление на небольшую наперёд известную константу обычно можно сделать быстро (собственно, без деления, одним умножением или, если повезёт, несколькими сдвигами). Хорошее описание дано в книге
"Hacker's Delight".
Пример:
unsigned remu20(const unsigned n) {
unsigned q = (n * 0xCCCCCCCDull) >> 36;
return n - 20 * q;
}
В этой же книге можно
подсмотреть некоторые другие методы, которые иногда позволяют найти остаток без предварительного нахождения частного. Вот пример для числа 20:
unsigned remu20(unsigned n) {
static const unsigned map[32] = {0,1,-1,2,3,3,4,5,5,6,-1,7,8,8,9,10,10,11,-1,12,13,13,14,15,15,16,-1,17,18,18,19,0};
unsigned v = (n >> 4) * 13;
unsigned a = (n * 0xCCCCCCCull + v) >> 27;
return map[a % 32];
}
Тут, к сожалению, уже появляются более сложные конструкции, чем если бы предварительно было бы найдено честное. Что говорит о том, что число 20 не очень подходящая константа для этого метода. Но всё равно этот код работает быстрее на моём компьютере чем наивное вычисление остатка соответствующей инструкцией процессора.
WM>В этой же книге можно подсмотреть некоторые другие методы, которые иногда позволяют найти остаток без предварительного нахождения частного. Вот пример для числа 20:
WM>unsigned remu20(unsigned n) {
WM> static const unsigned map[32] = {0,1,-1,2,3,3,4,5,5,6,-1,7,8,8,9,10,10,11,-1,12,13,13,14,15,15,16,-1,17,18,18,19,0};
WM> unsigned v = (n >> 4) * 13;
WM> unsigned a = (n * 0xCCCCCCCull + v) >> 27;
WM> return map[a % 32];
WM>}
Тут, к сожалению, уже появляются более сложные конструкции, чем если бы предварительно было бы найдено честное. Что говорит о том, что число 20 не очень подходящая константа для этого метода.
Вообще, такой метод работает плохо из-за необходимости вносить поправку (переменная v) в силу ограниченной точности умножения. Если, например, взять не всю область определения uint32_t, а лишь какой-то участок, то для него поправка может стать константой, что сразу же уберёт из вычислений множество тяжелых операций по её учёту.
Чтобы уметь вычислять остаток не для одного участка, а для всех чисел типа uint32_t, можно либо отображать исходный аргумент функции в нужную область преобразованиями, которые не меняют искомый остаток, либо покрыть диапазон uint32_t несколькими областями и в каждой вычислять свою формулу.
Если следовать первому варианту, то получается, например, такой код:
unsigned remu20(unsigned n) {
const static unsigned char rem[32] = {0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,13,13,14,14,15,16,16,17,18,18,19,19};
n = (n & 0x3ffff) + (n >> 18 << 2); // сужение диапазона значений n без изменения остатка при делении
unsigned index = (n * 214748365u) >> 27;
return rem[index];
}
Тут ещё можно заметить, что проведя подобную операцию сужения диапазона несколько раз (с разными константами), можно найти остаток от деления с использованием только побитовых операций, операций сдвига и сложения (т.е. без умножений, без ветвлений и без чтений из памяти). Правда, такой подход работает хорошо только для делителей, которые находятся недалеко от степеней двойки. Для далёких же от степени двойки чисел в худшем случае требуется слишком много итераций. Например, для того же делителя 20 требуется 6 операций:
unsigned remu20(unsigned n) { // очень медленный метод с очень простыми операциями
n = (n & 0x3ffff) + (n >> 18 << 2); // n ∈ [0, 327675]
n = (n & 0x3ff) + (n >> 10 << 2); // n ∈ [0, 2295]
n = (n & 0x3f) + (n >> 6 << 2); // n ∈ [0, 199]
n = (n & 0x3f) + (n >> 6 << 2); // n ∈ [0, 71]
n = (n & 0x1f) + (n >> 5 << 2) * 3; // n ∈ [0, 43]
n = (n & 0x1f) + (n >> 5 << 2) * 3; // n ∈ [0, 31]
int r = n - 20;
return (r < 0) ? n : r; // cmov
}
Если же строить для каждой области свою функцию, следуя второму варианту, то получается нечто такое:
unsigned remu20(unsigned n) {
const static unsigned char rem[8][32] = {
{0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,13,13,14,14,15,16,16,17,18,18,19,19},
{0,0,1,1,2,3,3,4,5,5,6,6,7,8,8,9,10,10,11,11,12,13,13,14,15,15,16,16,17,18,18,19},
{19,0,0,1,2,2,3,3,4,5,5,6,7,7,8,8,9,10,10,11,12,12,13,13,14,15,15,16,17,17,18,18},
{19,19,0,0,1,2,2,3,4,4,5,5,6,7,7,8,9,9,10,10,11,12,12,13,14,14,15,15,16,17,17,18},
{18,19,19,0,1,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12,12,13,14,14,15,16,16,17,17},
{18,18,19,19,0,1,1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,13,13,14,14,15,16,16,17},
{17,18,18,19,0,0,1,1,2,3,3,4,5,5,6,6,7,8,8,9,10,10,11,11,12,13,13,14,15,15,16,16},
{17,17,18,18,19,0,0,1,2,2,3,3,4,5,5,6,7,7,8,8,9,10,10,11,12,12,13,13,14,15,15,16}};
unsigned index = (n * 214748365u) >> 27;
unsigned bank = n >> 29;
return rem[bank][index];
}
При тестировании на нескольких intel-процессорах как раз последний подход показал наибольшую производительность из остальных методов (с отрывом от ближайшего конкурента этак на 15-20%). Ну и недостаток тут, конечно, тоже очевиден — функции для эффективной работы требуется 256 байт в L1-кеше для хранения хеш-таблицы.
Ну и разумеется, для других делителей все эти методы воспроизводятся с заменой константы ⌊2³²/20⌋ на ⌊2³²/d⌋ и пересчётом таблиц.
