упростите выражение k/m%n
Простой вопрос, это возможный упростить (или подразделение замены или по модулю менее - дорогая операция)
(k/m)%n
где переменные являются целыми числами, и операторы являются подразделением стиля C и операторами по модулю.
позвольте мне перефразировать вопрос немного, за исключением случая, где переменные являются base2, при каких условиях (например, некоторая переменная может быть постоянным) выражение может быть упрощено (или перефразировано частично с помощью base2 операции) удалить подразделение или по модулю?
это - способ для меня изучить теорию чисел, особенно base2 приемы, вместо того, чтобы тренироваться в оптимизации производительности
Спасибо
5 ответов
Для деления с малым постоянным знаменателем вы можете использовать что-то вроде этого.
k/m=k*(1/m)
x=(1<<16)/m
k/m=(k*x)>>16
Ответ может быть неточным в зависимости от входных данных.
Для деления с малым нечетным постоянным знаменателем можно использовать обратный мультипликатив . Следующие константы применяются к 32-битному делению.
3 2863311531 11 3123612579
5 3435973837 13 3303820997
7 3067833783 15 4008636143
9 954437177 17 4042322161
x/11 == x*3123612579 % 2^32
% 2 ^ 32 , конечно, свободен для 32-битных целых чисел. Чтобы применить это к четным числам, вычтите двойки и примените их позже.
x/44 == (x*3123612579 % 2^32) >> 2
В Hackers Delight есть глава о целочисленном делении.
Простой модуль и деление на степени двойки.
x%m == x&(m-1)
x/m == x>>log2(m) // assumes log2(m) is known, not calculated
Для целых чисел произвольной точности я рекомендую посмотреть http://documents.epfl.ch/users/k/ka/kaihara/www/papers/ModMulDiv_Binary.pdf
Он представляет собой аппаратный подход, но дает псевдокод, который вы можете адаптировать.
Очевидные оптимизации:
- m == 1: Ответ будет просто
k% m. - n == 1: ответ всегда
0. - m - степень двойки: например, если m равно 4, вы можете использовать
(k >> 2)% n; - n - степень двойки: выражение становится
(k / m) & (n - 1);
Проверка № 1 и № 2 тривиальна.
Проверка степени двойки выполняется с помощью:
void isPowerOfTwo(unsigned int x)
{
return x & (x - 1) == 0;
}
Я полагаю, это зависит от обстоятельств. Правый арифметический сдвиг даст вам деление на 2, а с помощью некоторой дополнительной арифметики вы можете превратить это в деление на любое число. Точно так же я думаю, что вы можете сделать то же самое с оператором по модулю. На самом деле, если в вашем процессоре нет необходимого оборудования, я бы не подумал, что вы что-то выиграете.
редактировать На самом деле, размышляя об этом, здесь необходимо больше подумать, поскольку, строго говоря, для отрицательного числа знаковый сдвиг не будет работать как деление на 2.
Если я правильно помню, поведение арифметического сдвига вправо не определено в C стандарт для отрицательных чисел (в нем говорится о степени двойки) и поэтому зависит от компилятора.
Если мы просто думаем о логике теории чисел, то это другое дело. Дай мне подумать.
Добавление к ответу Питера Александра
0) Конечно, m != 0 & & n != 0 являются предварительными условиями...
1) k < m : Ответ всегда 0
2) k == m : Ответ всегда 1 (если только n не равно 1, см. 5.)
3) k / m < n: Ответ - k / m
4) k < ( m * n ): Ответ всегда k / m. Это конкретное условие не очень способствует оптимизации, поскольку m*n не будет использоваться повторно, и это не должно быть намного быстрее, чем modulo если только m и/или n не являются целыми числами 2, в этом случае вам все равно будет лучше использовать 7. и/или 8.
Для справки добавлю слова Питера Александера:
5) m == 1 : Ответом будет k % n.
6) n == 1 : Ответом всегда будет 0.
7) m - степень 2 : например, если m равно 4, можно использовать (k >> 2) % n;
8) n - степень 2 : выражение становится (k / m) & (n - 1);