Добрый вечер, возникла следующая проблема при возведении в степень. На одной из итераций возникает такая ситуация что r =70579 a= 30733 и результате их перемножения получается 2 169 104 407. Следовательно мы выходим за диапазон типа int. И следовательно дальнейшие вычисления не верные. Так вот подскажите идею как можно усовершенствовать алгоритм, не изменяя типы переменных с int на __int64?
int r = 1, a = 2, b = 40423, n = 71273;
for (int i = 1; i <= b; i++) {
r = r * a;
r = r % n;
}
Memo1->Lines->Add(IntToStr(r));
P.S. ещё раз повторюсь, менять тип переменных с int на long long или же на __int64 в моём случае не катит т.к. планирую переносить впоследствии на arduino. Помогите, уже 4 часа бьюсь голова уже пухнет.
P.S.S. была идейка делить r пополам, потом делить n пополам, брать от каждой части r1 % n1 и r2 и n2 а потом результат складывать, но мне кажется что это не есть гуд.
a=2
, но никак не 30733. Покажите реальный пример. Если r или a больше n, то берите модуль до умножения. Если меньше, то возможны варианты. Не исключено, что придётся мудрить с умножением (в avr8 умножение int32 всё равно программное)