почему рекурсивное модульное возведение в степень не равно итеративному?

Question

почему рекурсивное модульное возведение в степень не равно итеративному?

Я реализовал нерекурсивное модульное возведение в степень

typedef long long uii;
uii modularExponentiation(uii base,uii exponent,uii p)
{
int result= 1;
base = base % p;
while( exponent > 0)
{
if (exponent % 2 == 1)
result = (result * base) % p;
exponent = exponent >> 1;
base = (base * base) % p;
}
return result;
}

а другой рекурсивный

uii modularExponentiation(uii base,uii exponent,uii p)
{
if(exponent == 0)
return 1;
int res= modularExponentiation(base,exponent/2,p);
if(exponent%2 == 0)
return (res * res)%p;
else
return ((res*res)*(base%p))%p;return res;
}

но два кода не дают правильный результат. Итерационный код из Википедии дает правильный результат. Что я сделал неправильно в рекурсивной версии, и что я должен сделать, чтобы это исправить?

1

algorithm c++exponentiation modular-arithmetic recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

я думаю, что использование int res вместо uii res это проблема есть шансы переполнения. Больше даже ((res*res)*base%p)%p может вызвать переполнение.

Улучшен код: —

uii modularExponentiation(uii base,uii exponent,uii p)
{
if(exponent == 0)
return 1;
uii res= modularExponentiation(base,exponent/2,p);
res = (res*res)%p;
if(exponent%2 == 0)
return res;
else
return (res*(base%p))%p;

}

1