Calculating integer overflow in C

Question

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
}

What is the size of `long`? What is the size of `long long`? Also, have you looked at and learned from [How to detect integer overflow in C or C++?](http://stackoverflow.com/questions/199333/)? — Jonathan Leffler, Aug 29 '15 at 01:52
Enable compiler warnings and fix the reported errors. And provide a [mcve] — too honest for this site, Aug 29 '15 at 01:56

score 2 · Answer 1 · answered Aug 29 '15 at 01:59

2

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 2⁶⁴). If we want x, we just solve for it; in particular, we have x ≡ arg1⁻¹ × arg2 (mod 2⁶⁴).

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

answered Aug 29 '15 at 01:59

icktoofay

126,289
21
250
231

In this question, arg1 is even, so is not relatively prime to 2^64, which means the inverse does not exist. That does not necessarily mean that there is no x that solves the equation -- you need reduce the range by lcm(arg1, 2^64) to get an invertable equation, or see that there is no solution. – Chris Dodd Aug 29 '15 at 02:15
Thanks. I tried to take these steps: 1. -3456345634563456 + 2^64 = 18443287728074988160 (call this arg2) 2. gcd(arg1, arg2) = 2 3. Since gcd != 1, no solution to problem. Also tried using an extended euclidian calculator but no results found. Am I missing something here? – qwerty3 Aug 29 '15 at 02:23
So you can divide both arg1 and arg2 by 2, giving you an odd arg1 that you can invert (mod 2^63) and solve (mod 2^63) giving you two x values (x and x + 2^63) that will both satisfy the equation. – Chris Dodd Aug 29 '15 at 02:27
If LCM(arg1, 2^64) does not give an integer result then no solution exists? – qwerty3 Aug 29 '15 at 02:29

Calculating integer overflow in C

1 Answers1