enamodeka enamodeka - 28 days ago 8
C Question

Calculating max long value using exponent overflows

I'm trying to figure out maximum value for type

long
by calculating an exponential of base
2
to the power of the bit number.

Unfortunately the calculation overflows at step 61 and I don't understand why.

long exponential(int base, int exponent)
{
long result = (long)base;
for (int i = 0; i < exponent; i++) {
result *= base;
}
return result;
}

unsigned int sLong = sizeof(long);

long lResult = exponential(2, (sLong * 8) - 1);


lResult
is
0
after running the function.

What's odd is that when I do this for
char
,
short
and
int
it works fine.

Answer Source

The code here has an off-by-one error.

Consider the following: what is the result of exponential(10, 2)? Empirical debugging (use a printf statement) shows that it's 1000. So exponential calculates the mathematical expression be+1.

The long type usually has 64 bits. This seems to be your case (seeing that the overflow happens around step 64). Seeing that it's a signed type, its range is (typically) from -263 to 263-1. That is, the maximal power of 2 that the data type can represent is 262; if the code tries to calculate 263, then overflow happens (you probably want to avoid it).

So, because of the off-by-one error, the code will cause an overflow for exponent greater or equal to 62.


To fix the off-by-one error, start multiplying from 1:

long power_of(int base, int exponent)
{
    long result = (long)1; // 0th power of base is 1
    for (int i=0; i<exponent;i++) {
        result*=base;
    }
    return result;
}

However, this will not get rid of the overflow, because the long data type cannot represent the number 263. Fortunately, you can use unsigned long long, which is guaranteed to be big enough for the type of calculations you are doing:

unsigned long long power_of(int base, int exponent)
{
    unsigned long long result = 1ULL; // 0th power of base is 1
    for (int i=0; i<exponent;i++) {
        result*=base;
    }
    return result;
}

Print it with the llu format:

printf("%llu", power_of(2, 63));