Эффективно вычислить по модулю сумму двух чисел

У меня есть три N -битные номера, A, B и C. Я не могу легко вычислить (A + B) % C, но я могу легко вычислить A % C и B % C. Если операция modulo без знака и я заранее знаю, что A + B не обертывает N битов, тогда я могу рассчитать ((A % C) + (B % C)) % C. Однако можно ли что-либо сделать для случаев, когда операция по модулю подписана, или добавление A и B может привести к обертыванию.Эффективно вычислить по модулю сумму двух чисел

Похоже, что может возникнуть некоторая путаница относительно того, почему ((A % C) + (B % C)) % C нельзя полагаться на то, чтобы всегда работать. Вот беззнаковое пример:

unsigned A = 0x1U; 
unsigned B = 0xFFFFFFFFU; 
unsigned C = 0x3U; 
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == 0x0U

Вот подписанный пример:

int A = 0x1; 
int B = 0xE27F9803; 
int C = 0x3U; 
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == -2

источник

2014-12-02 user4315149

Я нахожусь под впечатлением, что ваша формула работает для подписанных номеров, а также для неподписанных. Может ли кто-нибудь, пожалуйста, предоставить встречный пример в противном случае? – SlySherZ

Просьба привести пример. – 2501

Кроме того, существует множество различных вариантов реализации mod(). Например, в JavaScript, -10% 3 = -1. В то время как математическая теория и R говорят -10 %% 3 = 2. – Dinesh

В математике целочисленное деление обычно закругленные вниз к отрицательной бесконечности, и знак по модулю такой же, как тот же «делителя» или равна нулю: -10 mod 3 = 2 и 10 mod -3 = -2 (коэффициент округляется до -4). В C/C++ целочисленное деление округляется к нулю, а знак% совпадает с знаком «дивиденд» или «числитель» или равен нулю, -10 mod 3 = -1 и 10 mod -3 = 1 (фактор округлен до нуля до -3). При выполнении математической модели конечного поля с C/C++ вам необходимо выполнить коррекцию по поправкам, чтобы результаты соответствовали математическому определению modulo. Например, если X% 3 = -1, добавьте 3 так, чтобы X mod 3 = +2.

Предполагая, что C положительно, то математическое поле по модулю C состоит из чисел {0, 1, ... C-1} без каких-либо отрицательных чисел. Если C отрицательный (это необычно для modulo), то поле является {0, -1, -2, ... C + 1}. Если предположить, что C положителен, то если A или B отрицательны, то по-прежнему можно использовать ((A% C) + (B% C))% C, а затем отправлять правильные ответы, если результат отрицательный, добавив C к результату ,

источник

2014-12-02 16:18:51 rcgldr

Проблема заключается в том, что целочисленное добавление вставляет неявный модуль из-за его усечения. – user4315149

@rcgldr Не могли бы вы привести ссылку на свое определение? Модул предположительно является положительным числом. – Dinesh

@Dinesh - ссылки: [wiki modulo] (http://en.wikipedia.org/wiki/Modulo_operation) - Обратите внимание на определение Knuth r = a - (floor (a/n) * n), где пол округляется к отрицательной бесконечности. [wiki prime field] (http://en.wikipedia.org/wiki/Finite_field#Prime_fields) - Обратите внимание, что элементами такого поля являются целые числа по модулю p, которые равны 0, ..., p-1 (без отрицательных чисел для положительного p). [wiki modular arithmetic] (http://en.wikipedia.org/wiki/Modular_arithmetic) Для языков, таких как APL (с 1960-х годов) и Python, результат работы модулятора имеет тот же знак, что и делитель (или он равен нулю). – rcgldr

Что вы хотите:

((a+b)%2^n)%c

Пусть

a+b = k 2^n + d

Где k = 0 or 1 и d < 2^n.

Подключение вы получите:

((k 2^n + d) % 2^n) % c = (d % 2^n) % c = d % c

Принимая предыдущее выражение по модулю c вы получите

(a + b) % c = (k 2^n + d) % c => d % c = a % c + b % c - k 2^n % c

С n = 32, в C:

unsigned myMod(unsigned a, unsigned b, unsigned c) 
{ 
    // k = 1 if the sum overflows 
    unsigned k = (a > UINT_MAX - b or b > UINT_MAX - a); 

    return (a % c + b % c - k*(UINT_MAX%c + 1))%c; 
} 

myMod(0x1U,0xFFFFFFFFU,0x3U) == 0

источник

2014-12-09 23:15:00 sbabbi

Эффективно вычислить по модулю сумму двух чисел

ответ

Смежные вопросы