Большая часть оптимизированного способа вычислить модуль в C
Я имею, минимизируют стоимость вычисления модуля в C., говорят, что у меня есть номер x и n, число, которое разделит x
когда n == 65536 (который, оказывается, 2^16):
модификация = x % n (11 инструкций по сборке, как произведено GCC) или
модификация = x и 0xffff, который равен модификации = x и 65535 (4 инструкции по сборке)
таким образом GCC не оптимизирует его до этой степени.
В моем случае n не является x^ (интервал), но является самыми большими главными меньше, чем 2^16, который является 65521
когда я показал для n == 2^16, битовые операции могут оптимизировать вычисление. Что битовые операции могут я формовать когда n == 65521 для вычисления модуля.
6 ответов
Реализация модуля с наименьшей стоимостью в C
Как насчет реализации MOD следующим образом:
Чтобы найти: y = X mod n
y = X-(X/n)*n
(Предполагая, что оба X и n являются целыми числами)
ПРИМЕЧАНИЕ: Для оптимизации уровня сборки используйте iDiv , как объяснил Кристиан выше.
Побитовая операция работает хорошо, только если делитель имеет вид 2 ^ n . В общем случае такой побитовой операции нет.
rЕсли вам не нужно полностью уменьшать целые числа по модулю 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. Чтобы реализовать ее эффективно, можно выполнять модульные сокращения только после тщательно рассчитанного числа добавлений. Показанного выше сокращения достаточно, и только для вычисления хэша потребуется полная операция по модулю.
x mod 65536 эквивалентен x & 0xffff, только если x беззнаковый - для знака x он дает неправильный результат для отрицательных чисел. Для беззнакового x gcc действительно оптимизирует x% 65536 до побитового и с 65535 (даже на -O0, в моих тестах).
Поскольку 65521 не является степенью двойки, x mod 65521 не может быть вычислен так просто. gcc 4.3.2 на -O3 вычисляет его с использованием x - (x / 65521) * 65521 ; целочисленное деление на константу выполняется с использованием целочисленного умножения на соответствующую константу.
idiv - Целочисленное деление
Инструкция idiv делит содержимое 64-битного целого числа EDX: EAX (созданного путем просмотра EDX как четырех старших байтов и EAX как четырех младших байтов) на указанное значение операнда. Результат деления сохраняется в EAX, а остаток помещается в EDX .
источник: http://www.cs.virginia.edu/~evans/cs216/guides/x86.html
Во-первых, убедитесь, что вы смотрите на оптимизированный код, прежде чем делать выводы о том, что производит GCC (и убедитесь, что это конкретное выражение действительно нуждается в оптимизации) . Наконец - не считайте инструкций, чтобы делать выводы; может случиться так, что можно ожидать, что последовательность из 11 инструкций будет работать лучше, чем более короткая последовательность, которая включает инструкцию div.
Кроме того, вы не можете сделать вывод, что, поскольку x mod 65536 может быть вычислено с простой битовой маской, любая операция mod может быть реализована таким образом. Подумайте, насколько легко разделить десятичное число на 10 по сравнению с делением на произвольное число.
Со всем этим, возможно, вы сможете использовать некоторые техники «магических чисел» из книги Генри Уоррена «Хакерское наслаждение»: