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

还有一个是递归的

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

但是这两个代码并没有产生正确的结果。来自维基百科的迭代代码给出了正确的结果。我在递归版本中做错了什么，我应该怎么做才能修复它？

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;

}