алгоритм — модульное умножение больших чисел в переполнении стека
У меня три целых числа А, Б (менее 10 ^ 12) и С (менее 10 ^ 15). Я хочу посчитать (A * B)% C. я знаю это
(A * B) % C = ((A % C) * (B % C)) % C
но скажи если A = B = 10 ^ 11 тогда приведенное выше выражение вызовет целочисленное переполнение. Есть ли простое решение для вышеупомянутого случая, или я должен использовать быстрые алгоритмы умножения.
Если мне нужно использовать алгоритм быстрого умножения, то какой алгоритм мне следует использовать.
РЕДАКТИРОВАТЬ: Я пробовал выше проблемы в C ++ (который не вызывает переполнения, не уверен почему), но ответ не должен быть нуль?
Заранее спасибо.
Решение
Учитывая вашу формулу и следующий вариант:
(A + B) mod C = ((A mod C) + (B mod C)) mod C
Вы можете использовать подход «разделяй и властвуй» для разработки простого и быстрого алгоритма:
#include <iostream>
long bigMod(long a, long b, long c) {
if (a == 0 || b == 0) {
return 0;
}
if (a == 1) {
return b;
}
if (b == 1) {
return a;
}
// Returns: (a * b/2) mod c
long a2 = bigMod(a, b / 2, c);
// Even factor
if ((b & 1) == 0) {
// [((a * b/2) mod c) + ((a * b/2) mod c)] mod c
return (a2 + a2) % c;
} else {
// Odd exponent
// [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c
return ((a % c) + (a2 + a2)) % c;
}
}
int main() {
// Use the min(a, b) as the second parameter
// This prints: 27
std::cout << bigMod(64545, 58971, 144) << std::endl;
return 0;
}
Который O(log N)
Другие решения
Вы можете решить это, используя Schrage-х метод. Это позволяет умножить два подписанный чисел a а также z оба с определенным модулем m без генерации промежуточного числа больше этого.
Он основан на приблизительной факторизации модуля m,
m = aq + r
то есть
q = [m / a]
а также
r = m mod a
где [] обозначает целую часть. Если r < q а также 0 < z < m − 1тогда оба a(z mod q) а также r[z / q] лежать в диапазоне 0,...,m − 1 а также
az mod m = a(z mod q) − r[z / q]
Если это отрицательно, то добавьте m,
Этот метод часто используется в линейных конгруэнтных генераторах случайных чисел.
ОБНОВЛЕНО: Исправлена ошибка, когда старший бит a % c установлено. (подсказка: Кевин Хоппс)
Если вы ищете просто над быстро, тогда вы можете использовать следующее:
typedef unsigned long long u64;
u64 multiplyModulo(u64 a, u64 b, u64 c)
{
u64 result = 0;
a %= c;
b %= c;
while(b) {
if(b & 0x1) {
result += a;
result %= c;
}
b >>= 1;
if(a < c - a) {
a <<= 1;
} else {
a -= (c - a);
}
}
return result;
}
Извините, но алгоритм godel9 выдаст неверный результат, когда переменная «a» содержит значение, для которого установлен старший бит. Это потому что <<= 1 «теряет информацию. Вот исправленный алгоритм, который работает для любого целочисленного типа, со знаком или без знака.
template <typename IntType>
IntType add(IntType a, IntType b, IntType c)
{
assert(c > 0 && 0 <= a && a < c && 0 <= b && b < c);
IntType room = (c - 1) - a;
if (b <= room)
a += b;
else
a = b - room - 1;
return a;
}
template <typename IntType>
IntType mod(IntType a, IntType c)
{
assert(c > 0);
IntType q = a / c; // q may be negative
a -= q * c; // now -c < a && a < c
if (a < 0)
a += c;
return a;
}
template <typename IntType>
IntType multiplyModulo(IntType a, IntType b, IntType c)
{
IntType result = 0;
a = mod(a, c);
b = mod(b, c);
if (b > a)
std::swap(a, b);
while (b)
{
if (b & 0x1)
result = add(result, a, c);
a = add(a, a, c);
b >>= 1;
}
return result;
}В этом случае A и B — это 40-битные числа, а C — это 50-битные числа, что не является проблемой в 64-битном режиме, если у вас есть встроенный код или вы можете написать код сборки, чтобы использовать умножение 64 на 64 бита. это дает 128-битный результат (продукт на самом деле 80 бит), после чего вы делите 128-битный дивиденд на 50-битный делитель для получения 50-битного остатка (по модулю).
В зависимости от процессора может быть быстрее реализовать деление на 50-битную константу путем умножения на 81-битную (или менее) константу. Опять-таки, предполагая, что 64-битный процессор потребует 4 умножения и некоторых добавлений, а затем сдвиг старших бит 4-кратного произведения, чтобы получить частное. Затем для умножения 50-битного остатка используется умножение на частное 50 кратное по модулю число и вычитание (из 80-битного произведения).