c++ - なぜ再帰モジュラーべき乗は反復と等しくないのですか?

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;
}

もう1つは再帰的です

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;
}

しかし、2 つのコードは正しい結果を生成しません。ウィキペディアの反復コードは正しい結果をもたらします。再帰バージョンで何が間違っていて、それを修正するにはどうすればよいですか?

Answer 1

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;

}