Calculating big numbers with mod and pow

Question

i was trying to solve the big mod problem using the following code.

#include<iostream>
#include<cmath>

using namespace std;

typedef long int li;

li m;
li mod(li b,li p)
{
    if(p==0)
        return 1;
    if(p%2==0)
    {
        return ((mod(b,p/2)%m)*mod(b,p/2)%m)%m;
        //return (li)pow(mod(b,p/2)%m,2)%m;
    }
    return (b%m*mod(b,p-1)%m)%m;
}

main()
{
    li b,p;
    while(cin>>b>>p>>m)
    {
        cout<<mod(b,p)<<endl;
    }
}

but it gives different output for ((mod(b,p/2)%m)*mod(b,p/2)%m)%m and pow(mod(b,p/2)%m,2)%m.i want to know are they not the same and if they are why are the giving different outputs.

sample input: 3 18132 17

17 1765 3

2374859 3029382 36123

output without pow function: 13 2 13195

output with pow function: 1 2 31329

test code with pow function

#include<iostream>
#include<cmath>
using namespace std;

typedef long int li;

li m;
li mod(li b,li p)
{
    if(p==0)
        return 1;
    if(p%2==0)
    {
        //return ((mod(b,p/2)%m)*mod(b,p/2)%m)%m;
        return (li)pow(mod(b,p/2)%m,2)%m;
    }
    return (b%m*mod(b,p-1)%m)%m;
}

main()
{
    li b,p;
    while(cin>>b>>p>>m)
    {
        cout<<mod(b,p)<<endl;
    }
}

Answer 1

The answers you report "without pow function" are correct answers, and your code looks OK to me. So I think your problem is in the test you're applying, not in your modular exponentiation function.

The pow function operates on (double-precision) floating-point numbers, and is not guaranteed to give exact results even when both its inputs are small integers. What is happening to you is that at some point pow is returning a value that is just a tiny bit smaller than an integer, and then you cast it to long int and get a value 1 less than you "should", and after that everything is wrong.

For instance, if you compute 3^6 mod 17 with your code, then at one point it gets 3^3 mod 17 = 10 (OK so far), then computes pow(10,2) ... and, at least on my machine with my compiler, this comes out to just a little bit less than 100. So the cast to li yields 99 instead of 100, and then we're dead.

I have tried to verify this in more detail by instrumenting your code to output intermediate values, but amusingly this typically fails because of subtleties in floating-point arithmetic. (Saving an intermediate value in a variable can cause it to be subject to an extra floating-point rounding which turns the just-less-than-an-integer value into an exact integer value.)