Есть ли способ сделать (A * B) мод M без переполнения для длинных без знака длинных A и B?
Я не хочу кошмар установки GMP на Windows.
У меня есть два номера A и B, unsigned long longс, порядка 10 ^ 10 или около того, но не более ((A%M)*(B%M))%MЯ получаю целочисленное переполнение.
Есть ли доморощенные функции для расчета (A*B)%M для больших чисел?
Решение
Если модуль M достаточно меньше, чем ULLONG_MAX (что имеет место, если он находится в области 10 ^ 10), вы можете сделать это в три этапа, разделив один из факторов на две части. Я предполагаю что A < M а также B < M, а также M < 2^42,
// split A into to parts
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1);
unsigned long long temp = (a1 * B) % M; // doesn't overflow under the assumptions
temp = (temp << 21) % M; // this neither
temp += (a2*B) % M; // nor this
return temp % M;
Для больших значений вы можете разделить коэффициент на три части, но если модуль становится очень близким к ULLONG_MAX становится некрасиво
Другие решения
Других решений пока нет …