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

Я минимизирую стоимость расчета модуля в C. скажем, у меня есть число x и n - число, которое будет делить x

когда 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 для вычисления модуля.

Ответ 1

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

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

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

Там есть добавленная глава на веб-сайте, которая содержит "два метода вычисления остатка деления без вычисления частного!", которые вы можете найти какое-то использование. Первый метод применяется только к ограниченному набору делителей, поэтому он не будет работать для вашего конкретного экземпляра. Я на самом деле не читал онлайн-раздел, поэтому я не знаю, насколько применим другой метод для вас.

Ответ 2

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

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

Ответ 3

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

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. Чтобы эффективно реализовать его, только после модульного сокращения количество добавлений будет только модульным сокращением. Сокращения, показанного выше, достаточно, и только вычисление хеша будет нуждаться в полной модульной операции.

Ответ 4

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

Ответ 5

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

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

Ответ 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;
}

Ответ 7

idiv - Integer Division

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

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

Ответ 8

Наименее затратная реализация модуля в C

Как реализовать MOD следующим образом:

Чтобы найти: y = X mod n

y = X-(X/n)*n

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

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