CODEWITHSUNDEEP
c++algorithmrecursionexponentiationmodular-arithmetic
Unbound
Unbound

Reputation: 345

why Recusrsive modular exponentiation not equals iterative?

I have implemented a non-recursive modular exponentiation

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

and another one is recursive

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

but the two code doesn't produce the correct result. The iterative code from Wikipedia gives the correct result. What have I done wrong in the recursive version, and what should I do to fix it?

Upvotes: 1

Views: 1491

Answers (1)

Vikram Bhat
Vikram Bhat

Reputation: 6246

i think the usage of int res instead of uii res is the problem there are chances of overflow. Moreove even ((res*res)*base%p)%p can cause overflow .

Improved code :- 

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;

}

Upvotes: 1

Related Questions