упрощают выражение к/т% п

Question

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

(k/m)%n 

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

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

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

Спасибо

Answer 1

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

k/m=k*(1/m) 
x=(1<<16)/m 
k/m=(k*x)>>16 

Ответ может быть неточным в зависимости от входов.

Для деления с небольшим нечетным постоянным знаменателем вы можете использовать multiplicative inverse. К 32-разрядному делению применяются следующие константы.

3 2863311531  11 3123612579 
5 3435973837  13 3303820997 
7 3067833783  15 4008636143 
9 954437177  17 4042322161 

x/11 == x*3123612579 % 2^32 

The % 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

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

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

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

Если мы просто думаем о логике теории чисел, тогда это другое дело. Позвольте мне подумать об этом.

Answer 3

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

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

Answer 4

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

1. м == 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 5

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

0) Конечно м = 0 & & п = 0 являются предпосылками ...

1) К < м: Ответ всегда 0

2) к == м: ответ всегда 1 (если п не является также 1 см 5.)

3) к/т < n: Ответ k/m

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

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

5) м == 1: ответ будет только к% п.

6) п == 1: Ответ всегда 0.

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

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