Calculating max long value using exponent overflows

Question

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.

With `unsigned int sLong = sizeof(short);` `printf("%ld\n", lResult);` prints 65536. I'd expect the max value for `short` to be 32767. (`char` --> 256) I disagree that "for char/short/int it works fine". Suggest to get code working for those max values and then attempt `long`. — chux - Reinstate Monica, Sep 25 '17 at 20:44
"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" - why would you expect that to give you the maximum value? — user2357112, Sep 25 '17 at 20:51
You should not use overflow for this. Shifting a 1 bit into the sign bit of a signed integer has undefined behavior. The only valid way to know these values is to use the constants `INT_MAX`, `LONG_MAX` etc. — Jens Gustedt, Sep 25 '17 at 20:51
those would be the max values for unsigned char and short, wouldn't they? Short: 255, short: 65535. I get those fine. However, long (and int as well...) don't compute correctly. — enamodeka, Sep 25 '17 at 20:59
@JensGustedt I'm going through exercises from Kernighan and Ritchie's The C Programming language book. One of the exercises there is to calculate the min and max value for the primitive types (apart from getting them throught the constants) as suggested. I did work those out by assigning -1 to an unsigned version of the integer types and that produces the max value, but I don't understand what I'm doing wrong with the above code. — enamodeka, Sep 25 '17 at 21:02
Try `unsigned long result = base;`, `i < exponent - 1` and `return result-1;` — David C. Rankin, Sep 25 '17 at 21:08
@JensGustedt Also, the subject might have been misunderstood. I'm not using the fact of the overflow to calculate the max value. I'm simply stating that the result of my function overflows and I'm trying to figure out why. — enamodeka, Sep 25 '17 at 21:10
@DavidC.Rankin when I do i < exponent - 1 all values get calculated at half the max. Nothing overflows. If I leave i < exponent; I get char and short correct and int and long overflowing and producing 0 as a result. — enamodeka, Sep 25 '17 at 21:18
If I change code to `unsigned int sLong = sizeof(unsigned short);` the result is 65536 and **not** the expected 65535. So code is still not fine. I am confident that once code computes the correct max for those, then the problem with `long` should become clear. — chux - Reinstate Monica, Sep 25 '17 at 21:18
What do you expect `exponential(10, 1)` to return? 10 as in 10-to-the-1-power or 100 as the posted code does? I'd use `long result = 1;` — chux - Reinstate Monica, Sep 25 '17 at 21:20
@chux That was it. Result variable should have been initialised to 1 at the beginning of the exponential function. Thanks for spotting this. And thanks everybody for your time. — enamodeka, Sep 25 '17 at 21:30
@enamodeka Code that tries to calculate the maximum _signed_ value on an arbitrary system can easily invoke _undefined behavior_. Heed the good advice of [@Jens Gustedt](https://stackoverflow.com/questions/46413665/calculating-max-long-value-using-exponent-overflows?noredirect=1#comment79785834_46413665) — chux - Reinstate Monica, Sep 25 '17 at 21:34
@enamodeka -- your return type is `long`, not `unsigned long` -- thus the problem. — David C. Rankin, Sep 25 '17 at 21:35
Conceptually it is easier to start with the range for `char` and `unsigned char`. Recall `char` has a range of `-128 to 127` (zero is always included on the high-side, so it is 1 less than the full range). `unsigned char` is `0 to 255` (same thing, you have to account for zero). — David C. Rankin, Sep 25 '17 at 21:42
@DavidC.Rankin thus overflowing by 1 when calculating exponent. Got it. — enamodeka, Sep 25 '17 at 22:14

score 2 · Accepted Answer · answered Sep 25 '17 at 21:38

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 b^e+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 -2⁶³ to 2⁶³-1. That is, the maximal power of 2 that the data type can represent is 2⁶²; if the code tries to calculate 2⁶³, 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 2⁶³. 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));

Thanks for taking time to explain it thoroughly. This whole exercise definitely gave me some solid understanding of how easy it is to mismatch unsigned and signed types to get wrong results. Also, not starting from 1 as the 0th power of base was a big error here. — enamodeka, Sep 25 '17 at 21:52

Calculating max long value using exponent overflows

1 Answers1