упростить выражение k / m% n

Question

Простой вопрос, возможно ли упростить (или заменить деление или по модулю менее дорогой операцией)

(k/m)%n

, где переменные являются целыми числами, а операторы - это операторы деления в стиле C и операторы по модулю.

позвольте мне немного перефразировать вопрос, за исключением случая, когда переменные являются base2, при каких условиях (например, некоторая переменная может быть постоянной) выражение может быть упрощено (или частично перефразировано с использованием операций base2) для удаления деления или по модулю?

для меня это способ изучения теории чисел, особенно трюков с base2, а не упражнения по оптимизации производительности

Спасибо

Answer 1

Для деления с маленьким постоянным знаменателем, вы можете использовать что-то вроде этого.

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

Answer 2

Для целых чисел произвольной точности я рекомендую посмотреть http://documents.epfl.ch/users/k/ka/kaihara/www/papers/ModMulDiv_Binary.pdf

Он представляет аппаратный подход, но дает псевдокод, который вы можете адаптировать.

Answer 3

Очевидная оптимизация:

1. m == 1: Ответ будет просто k % m.
2. n == 1: Ответ всегда 0.
3. m - это степень 2: например, если m равно 4, вы можете использовать (k >> 2) % n;
4. n - это степень 2: выражение становится (k / m) & (n - 1);

Проверка для № 1 и № 2. тривиальна.

Проверка для степеней двух выполняется с помощью:

void isPowerOfTwo(unsigned int x)
{
    return x & (x - 1) == 0;
}

Answer 4

Добавление к ответу Петра Александра

0) Конечно, m! = 0 && n! = 0 являются предварительными условиями ...

1) k

2) k == m: ответ всегда равен 1 (если n также не равно 1, см. 5).

3) к / м <п: Ответ к / м </p>

4) k <(m * n): ответ всегда k / m. Это конкретное условие не очень способствует оптимизации, так как m * n не будет использоваться повторно, и это не должно быть намного быстрее, чем по модулю если m и / или n не являются степенями 2, в этом случае вам все равно лучше использовать 7. и / или 8. </p>

Для справки добавление Петра Александра:

5) m == 1: ответом будет просто k% n.

6) n == 1: ответ всегда равен 0.

7) m - это степень 2: например, если m равно 4, вы можете использовать (k >> 2)% n;

8) n - это степень 2: выражение становится (k / m) & (n - 1);

Answer 5

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

edit На самом деле, если подумать, нужно больше думать, строго говоря, для отрицательного числа сдвиг со знаком не будет делиться на 2.

Если я правильно помню, поведение арифметического сдвига вправо не определено в стандарте C для отрицательных чисел (оно говорит о степенях 2) и поэтому зависит от компилятора.

Если мы просто думаем о логикеТеория чисел, это другое дело.Дай мне подумать.