Наиболее оптимизированный способ расчета модуля в C

Question

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

когда n == 65536 (что составляет 2 ^ 16):

mod = x% n (11 инструкций по сборке от GCC) или
mod = x & 0xffff, что равно mod = x & 65535 (4 инструкции по сборке)

Итак, GCC не оптимизирует его до такой степени.

В моем случае n - это не x ^ (int), но наибольшее простое число меньше 2 ^ 16, то есть 65521

как я показал для n == 2 ^ 16, побитовые операции могут оптимизировать вычисления. Какие побитовые операции я могу выполнить, когда n == 65521 для вычисления модуля.

Answer 1

Сначала убедитесь, что вы смотрите на оптимизированный код, прежде чем делать вывод о том, что производит GCC (и убедитесь, что это конкретное выражение действительно необходимо оптимизировать). Наконец - не считайте инструкции, чтобы сделать свои выводы; может случиться так, что последовательность из 11 команд может работать лучше, чем более короткая последовательность, включающая инструкцию div.

Кроме того, вы не можете сделать вывод, что, поскольку x mod 65536 можно рассчитать с помощью простой битовой маски, то любая операция мода может быть реализована таким образом. Подумайте, насколько легко делить на 10 в десятичном виде в отличие от деления на произвольное число.

Со всем этим вы можете использовать некоторые приемы "магического числа" из книги Восхищения Хакера Генри Уоррена:

• http://www.hackersdelight.org/
• http://www.hackersdelight.org/magic.htm

На сайте есть добавленная глава *1017*, которая содержит «два метода вычисления остатка от деления без вычисления фактора!», Которые вы можете найти для себя полезным. 1-й метод применяется только к ограниченному набору делителей, поэтому он не будет работать для вашего конкретного экземпляра. На самом деле я не читал онлайн-главу, поэтому не знаю точно, насколько применимая другая техника может быть для вас.

Answer 2

x mod 65536 эквивалентно только x & 0xffff, если x без знака - для x со знаком он дает неверный результат для отрицательных чисел. Для x без знака gcc действительно оптимизирует x % 65536 до побитового значения и с 65535 (даже при -O0, в моих тестах).

Поскольку 65521 не является степенью 2, x mod 65521 не может быть рассчитан так просто. gcc 4.3.2 on -O3 вычисляет его, используя x - (x / 65521) * 65521; целочисленное деление на константу выполняется с использованием умножения целых чисел на связанную константу.

Answer 3

Если вам не нужно полностью уменьшать свои целые числа по модулю 65521, тогда вы можете использовать тот факт, что 65521 близка к 2 ** 16. То есть если x - это беззнаковое целое число, которое вы хотите уменьшить, тогда вы можете сделать следующее:

unsigned int low = x &0xffff;
unsigned int hi = (x >> 16);
x = low + 15 * hi;

При этом используется 2 ** 16% 65521 == 15. Обратите внимание, что это не полное сокращение. То есть начиная с 32-битного ввода, вам гарантируется, что результат будет не более 20 бит и, конечно, он будет соответствовать входному модулю 65521.

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

например. Одним из приложений является реализация Adler-32, в которой используется модуль 65521. Эта хеш-функция выполняет много операций по модулю 65521. Для ее эффективной реализации можно было бы выполнять модульные сокращения только после тщательно рассчитанного числа добавлений. Приведенного выше сокращения достаточно, и только для вычисления хэша потребуется полная операция по модулю.

Answer 4

Побитовая операция работает хорошо, только если делитель имеет форму 2^n. В общем случае такой побитовой операции не существует.

Answer 5

Если x является возрастающим индексом, и известно, что приращение i меньше n (например, при итерации по круговому массиву длины n ), полностью избегайте модуля , Цикл идет

x += i; if (x >= n) x -= n;

намного быстрее, чем

x = (x + i) % n;

который вы, к сожалению, найдете во многих учебниках ...

Если вам действительно нужно выражение (например, потому что вы используете его в выражении for), вы можете использовать уродливый, но эффективный

x = x + (x+i < n ? i : i-n)

Answer 6

В качестве подхода, когда мы имеем дело со степенями 2, можно рассмотреть этот вариант (в основном C):

.
.

#define THE_DIVISOR    0x8U;  /* The modulo value (POWER OF 2). */
.
.
uint8 CheckIfModulo(const sint32 TheDividend)
{
    uint8 RetVal = 1; /* TheDividend is not modulus THE_DIVISOR. */

    if (0 == (TheDividend & (THE_DIVISOR - 1)))
    {
        /* code if modulo is satisfied */
        RetVal = 0; /* TheDividend IS modulus THE_DIVISOR. */
    }
    else
    {
        /* code if modulo is NOT satisfied */
    }
    return RetVal;
}

Answer 7

Если константа, с которой вы хотите взять модуль, известна во время компиляции и у вас есть приличный компилятор (например, gcc), обычно лучше всего разрешить компилятору твори свою магию. Просто объявите по модулю const.

Если вы не знаете константу во время компиляции, но вы собираетесь взять - скажем - миллиард модулей с тем же номером, затем используйте это http://libdivide.com/

Answer 8

Реализация модуля наименьшей стоимости в C

---

Как насчет реализации MOD следующим образом:

Найти: y = X mod n

y = X-(X/n)*n

(при условии, что X и n являются целыми числами)

ПРИМЕЧАНИЕ: Для оптимизации уровня сборки используйте iDiv , как объяснено выше Krystian.

Answer 9

idiv - Целочисленное деление

Инструкция idiv делит содержимое 64-битного целого числа EDX: EAX (созданного путем просмотра EDX как старших четырехзначных байтов и EAX как младших четырёх байтов) на указанное значение операнда. Коэффициент деления сохраняется в EAX, а остаток помещается в EDX .

.

источник: http://www.cs.virginia.edu/~evans/cs216/guides/x86.html