#c #overflow #modulus
#c #переполнение #модуль
Вопрос:
Как вычислить модуль вида (a *b)%c?
я хочу вычислить модуль умножения двух чисел int, где они находятся почти на стадии переполнения…
здесь c также является int
Ответ №1:
(a * b) % c == ((a % c) * (b % c)) % c
Комментарии:
1. 1 Только что прокомментировал это, но отсутствие кофе означало, что я не был уверен. 😉
2. Если a <= b < c, a % c и b % c ничего не сделают, поэтому мы все равно можем получить переполнение.
Ответ №2:
Как насчет ((a % c) * (b % c)) % c ? В зависимости от вашей архитектуры это может быть быстрее или медленнее, чем приведение к большему типу.
Комментарии:
1. Если a <= b < c, a % c и b % c ничего не сделают, поэтому мы все равно можем получить переполнение.
Ответ №3:
Вы можете привести a и c к long long , чтобы умножение не привело к переполнению.
((long long)a * (long long)b) % c
Комментарии:
1. мне нужен какой-нибудь оптимизированный метод
2. Я не думаю, что вы нашли бы более быстрое решение. На машинах x86 результат 32-разрядного умножения всегда 64-разрядный. Таким образом, вы просто уведомляете компилятор использовать 64-разрядный результат.
3. long long не всегда больше, чем int (особенно на современных машинах)