-
overflow problem
Hi there,
I have included code for a function called powermod which performs the following equation a^b mod(N), in which a, b and N are all defined as longs. However when I use large values for b, the function overflows and returns a wrong value. Does anyone know if there is a way around this?
// powermod function
// -----------------
// this function raises a number (value) to a power, under a given
// modulus.
long powermod(long value, long power, long modulus)
{
int temp;
long ret(1);
long t_value;
for(unsigned int i = 0;i < (sizeof(power)*8);++i)
{
if (i == 0)
{
t_value = value;
}
else
{
t_value *= t_value;
t_value %= modulus;
}
temp =((power >> i) & 1);
if ( temp == 1)
{
// the ith bit is 1, so we are going to
// need to include this t value in our
// answer.
ret *= t_value;
ret %= modulus;
}
}
return ret;
}
-
you can try using long doubles as the type instead of long. the long double type is the largest built in type. If you need something bigger than that, then you will have to create the type yourself. Unfortunately, the modulus operator is only defined for type int. You might be able to overload it for other types, but I've never done so.