переполнение — поиск остатка большого умножения в переполнении стека
Я хотел бы попросить некоторую помощь относительно следующей проблемы. Мне нужно создать функцию, которая будет умножать два целых числа и извлекать остаток от этого умножения, деленный на определенное число (короче, (x * y)% A).
Я использую unsigned long long int для этой проблемы, но A = 15! в этом случае и x, и y были вычислены по модулю A ранее. Таким образом, x * y может быть больше 2 ^ 64 — 1, поэтому переполняется.
Я не хотел использовать внешние библиотеки. Может ли кто-нибудь помочь мне разработать короткий алгоритм для решения этой проблемы?
Заранее спасибо.
Решение
Если у вас уже есть мод A из x и y, почему бы не использовать их? что-то вроде,
если,
x = int_x*A + mod_x
y = int_y*A + mod_y
затем
(x*y)%A = ((int_x*A + mod_x)(int_y*A + mod_y))%A = (mod_x*mod_y)%A
mod_x*mod_y должно быть намного меньше, верно?
РЕДАКТИРОВАТЬ:
Если вы пытаетесь найти модуль по большому 10e11Я думаю, вам придется использовать другой метод. Но пока не очень эффективно, что-то вроде этого будет работать
const int MAX_INT = 10e22 // get max int
int larger = max(mod_x, mod_y) // get the larger number
int smaller = max(mod_x, mod_y)
int largest_part = floor(MAX_INT/smaller)
if (largest_part > larger):
// no prob of overflow. use normal routine
else:
int larger_array = []
while(largest_part < larger):
larger_array.append(largest_part)
larger -= largest_part
largest_part = floor(MAX_INT/smaller)
// now use the parts array to calculate the mod by going through each elements mod and adding them etc
Если вы понимаете этот код и настройки, вы сможете выяснить остальные
Другие решения
Других решений пока нет …