Overflow check on integer multiplication in C ?
-
Hello, I need to multiply integer value with a factor and want to do an overflow check with INT_MAX, INT_MIN for this. Integer contains 4 bytes on my machine an this is the max variable-size. I need to do this check for signed integer and unsigned integer. Only integer math/variables allowed. The factor always comes as fraction with a nominator and denominator. The denominator always is 10 Factor might be greater 1 or less than 1
So for example fraction is 25/10, varible a is signed integer
a = (a * 25)/10 -> may cause overflow, because (a * 25) can be > INT_MAX ( or < INT_MIN )
Overflow checks:
if (a > (INT_MAX * 10)/25 -> not possible because of overflow, INT_MAX is the maximum number the compiler can store.
if (a > INT_MAX * (10/25) -> not possible because 10/25 is 0.4 which will be 0 in integer math.So any idea how to solve my problem?
Thanks for any hint!
-
Hello, I need to multiply integer value with a factor and want to do an overflow check with INT_MAX, INT_MIN for this. Integer contains 4 bytes on my machine an this is the max variable-size. I need to do this check for signed integer and unsigned integer. Only integer math/variables allowed. The factor always comes as fraction with a nominator and denominator. The denominator always is 10 Factor might be greater 1 or less than 1
So for example fraction is 25/10, varible a is signed integer
a = (a * 25)/10 -> may cause overflow, because (a * 25) can be > INT_MAX ( or < INT_MIN )
Overflow checks:
if (a > (INT_MAX * 10)/25 -> not possible because of overflow, INT_MAX is the maximum number the compiler can store.
if (a > INT_MAX * (10/25) -> not possible because 10/25 is 0.4 which will be 0 in integer math.So any idea how to solve my problem?
Thanks for any hint!
One way would be to perform the multiplication as a double-precision operation, and then examine the high word. For unsigned values (in pseudocode):
// HI_HALF - returns the upper N/2 bits of an N-bit integer
// LO_HALF - returns the lower N/2 bits of an N-bit integer
// MAKE_DIGIT - combines two N/2-bit values to make an N-bit integer// multiply a DIGIT a by a DIGIT b, returning a two-DIGIT result
// a, b must be unsignedDIGIT alow = LO_HALF(a)
DIGIT ahigh = HI_HALF(a)
DIGIT blow = LO_HALF(b)
DIGIT bhigh = HI_HALF(b)
DIGIT carry
DIGIT accumulator
DIGIT result[4]accumulator = alow * blow
carry = HI_HALF(accumulator)
result[0] = LO_HALF(accumulator)accumulator = alow * bhigh + carry
result[1] = LO_HALF(accumulator)
result[2] = HI_HALF(accumulator)accumulator = ahigh * blow + result[1]
result[1] = LO_HALF(accumulator)
carry = HI_HALF(accumulator)accumulator = ahigh * bhigh + result[2] + carry
result[2] = LO_HALF(accumulator)
result[3] = HI_HALF(accumulator)// combine result[3] and result[2] into 1 DIGIT
// combine result[1] and result[0] into 1 DIGIT
return MAKE_DIGIT(result[3], result[2]), MAKE_DIGIT(result[1], result[0])Note that many optimizations may be performed on the above code; it is laid out like this for easy comprehension. For the operation a * b, if the high digit is non-zero, the result has overflowed For the operation a * b / c, if the high DIGIT of (a * b) >= c, then the entire operation will overflow. Signed values are left as an exercise for the student.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
-
Hello, I need to multiply integer value with a factor and want to do an overflow check with INT_MAX, INT_MIN for this. Integer contains 4 bytes on my machine an this is the max variable-size. I need to do this check for signed integer and unsigned integer. Only integer math/variables allowed. The factor always comes as fraction with a nominator and denominator. The denominator always is 10 Factor might be greater 1 or less than 1
So for example fraction is 25/10, varible a is signed integer
a = (a * 25)/10 -> may cause overflow, because (a * 25) can be > INT_MAX ( or < INT_MIN )
Overflow checks:
if (a > (INT_MAX * 10)/25 -> not possible because of overflow, INT_MAX is the maximum number the compiler can store.
if (a > INT_MAX * (10/25) -> not possible because 10/25 is 0.4 which will be 0 in integer math.So any idea how to solve my problem?
Thanks for any hint!
All that matters is if a * factor overflows, so the /10 can be ignored. I believe you just need to check if (a <= (INTMAX / factor)).
-
Hello, I need to multiply integer value with a factor and want to do an overflow check with INT_MAX, INT_MIN for this. Integer contains 4 bytes on my machine an this is the max variable-size. I need to do this check for signed integer and unsigned integer. Only integer math/variables allowed. The factor always comes as fraction with a nominator and denominator. The denominator always is 10 Factor might be greater 1 or less than 1
So for example fraction is 25/10, varible a is signed integer
a = (a * 25)/10 -> may cause overflow, because (a * 25) can be > INT_MAX ( or < INT_MIN )
Overflow checks:
if (a > (INT_MAX * 10)/25 -> not possible because of overflow, INT_MAX is the maximum number the compiler can store.
if (a > INT_MAX * (10/25) -> not possible because 10/25 is 0.4 which will be 0 in integer math.So any idea how to solve my problem?
Thanks for any hint!
It will take more effort and cpu cycles to pick off the overflow than simply move it to next size up integer, do the mult on a that type and look at the result for overflow So for 16 bit int and 32bit long as an example
long b = a;
b *=25
b /=10
if (b & 0x7FFF0000 != 0)
{
// error result in b is larger than an int
}
a = (int) b;If you want to do it proper anal uses standard ints
#include
int16_t a = ????;
int32_t b = a;
b *=25
b /=10
if (b & 0x7FFF0000 != 0)
{
// error result in b is larger than an int
}
a = (int16_t) b;In vino veritas
-
It will take more effort and cpu cycles to pick off the overflow than simply move it to next size up integer, do the mult on a that type and look at the result for overflow So for 16 bit int and 32bit long as an example
long b = a;
b *=25
b /=10
if (b & 0x7FFF0000 != 0)
{
// error result in b is larger than an int
}
a = (int) b;If you want to do it proper anal uses standard ints
#include
int16_t a = ????;
int32_t b = a;
b *=25
b /=10
if (b & 0x7FFF0000 != 0)
{
// error result in b is larger than an int
}
a = (int16_t) b;In vino veritas
