CODEWITHSUNDEEP
cintegerinteger-overflow
qwerty3
qwerty3

Reputation: 23

Calculating integer overflow in C

I'm attempting to solve the following equation for x to make the if statement true. I have tried using a linear congruence equation however could not get the right answer.

I am using the assumptions that integer overflow occurs at 2^63-1, and x is of type long

Could someone give me a pointer with how to do this?

long arg1 = 1234123412341234;
long arg2 = -3456345634563456;
if(x * arg1 == arg2) {
    //true
}

Upvotes: 0

Views: 230

Answers (1)

icktoofay
icktoofay

Reputation: 129109

First, note that signed integer overflow is undefined. Unsigned integer overflow is, however, defined. I’m not sure how much that changes the problem, but I’m going to assume unsigned integers rather than signed integers.

The problem, again, is x × arg1 = arg2. To make the wrapping explicit, we have x × arg1 ≡ arg2 (mod 264). If we want x, we just solve for it; in particular, we have x ≡ arg1−1 × arg2 (mod 264).

The question then is how to find arg1−1. It happens that this is called a modular multiplicative inverse, and when it exists (it exists iff arg1 is relatively prime to 264), it can be found using the extended Euclidean algorithm.

Upvotes: 2

Related Questions