Улучшение выражения с целыми умножениями и по модулю

Question

Есть ли способ, я могу написать следующую строку, более эффективную, чем текущее выражение?

Math.abs(((a*k + b) % P) % m); 

P является константой простое число
m не является отрицательной и мощностью 2
a и b являются случайными неотрицательное числа

Примечание: Для того, чтобы быть ясно, что это не горячее пятно, которое я обнаружил во время профилирования, и хочу улучшить. Я заинтересован в поиске, если есть способ написать выражение лучше (с точки зрения эффективности), которое может быть легко известно кому-то с лучшим фоном в битовых операциях, например.

Answer 1

Резюмируя комментарий цепь, вы могли бы написать

(a * k + b) % P & (m - 1) 

, который не эквивалентно исходному выражению, но отвечает тем же требованиям, в любом случае. Он обрабатывает случай, когда a * k + b отрицательный (либо потому, что k является отрицательным, либо из-за обертывания) по-разному, но таким образом, что все еще отлично подходит для хэш-функции.

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

Answer 2

Это получает аналогичный ответ («аналогичные» означает «тот же результат, когда выражение в скобках не является отрицательным, но отличается при отрицательном), но с использованием немного кунг-фу, чтобы избежать разделения модуль и вызов Math.abs():

(a*k + b) % P & ~-m 

Чтобы понять, что происходит, давайте предположим, m = 8 и посмотреть на 16-битных битовых комбинаций:

8 -> 0000 1000 
-8 -> 1111 1000 
~-8 -> 0000 0111 

Как вы можете видеть, ~-m производит бит mask вам нужно замаскировать все, кроме бит, необходимых для результата n % m - то есть высокий бит (бит отрицательного индикатора) и все, кроме бит справа от 1 бит, используемого для мощности 2-го номера.

На личной ноте, я совершенно очарован с выражением ~-m, который при операции AND с предыдущим расчетом достигает как abs() (путем битового маскирования старший бит) и эффективно делает модуль разделения, когда m является силой из двух.

Разница возникает, когда предыдущий результат отрицательный, из-за такого подхода относительный негатив, как если бы он был положительным.