Overflow Prevention Techniques

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns true if a*b overflows signed 64-bit, false otherwise.
5
bool mul_overflow_ll(long long a, long long b) {
6
    // Handle zero early
7
    if (a == 0 || b == 0) return false;
8
    // Check using division with careful sign handling.
9
    // We want to ensure that a*b is within [LLONG_MIN, LLONG_MAX].
10
    if (a > 0) {
11
        if (b > 0) {
12
            return a > LLONG_MAX / b;
13
        } else { // b < 0
14
            return b < LLONG_MIN / a;
15
        }
16
    } else { // a < 0
17
        if (b > 0) {
18
            return a < LLONG_MIN / b;
19
        } else { // b < 0
20
            // Product is non-negative; compare against LLONG_MAX
21
            return a < LLONG_MAX / b; // note: b<0, division truncates toward zero in C++11+, but comparisons still correct here
22
        }
23
    }
24
}
25
26
// Safe multiply with __int128 to compute then range-check.
27
// Throws if overflow; otherwise returns a*b as long long.
28
long long mul_checked(long long a, long long b) {
29
    __int128 prod = ( __int128 )a * ( __int128 )b; // full 128-bit product
30
    if (prod < ( __int128 )LLONG_MIN || prod > ( __int128 )LLONG_MAX) {
31
        throw overflow_error("long long multiplication overflow");
32
    }
33
    return (long long)prod;
34
}
35
36
int main() {
37
    ios::sync_with_stdio(false);
38
    cin.tie(nullptr);
39
40
    // Demo: read pairs and multiply safely
41
    vector<pair<long long,long long>> tests = {
42
        {1000000000LL, 5000000000LL/5}, // 1e9 * 1e9 fits? (no)
43
        {2000000000LL, 2000000000LL},   // definitely overflow for 64-bit? (no, 4e18 < 9.22e18)
44
        {LLONG_MAX, 2},                 // overflow
45
        {-3000000000LL, 4000000000LL}   // may overflow
46
    };
47
48
    for (auto [a,b] : tests) {
49
        bool willOverflow = mul_overflow_ll(a,b);
50
        cout << a << " * " << b << ": " << (willOverflow ? "overflow (check)" : "no overflow (check)") << '\n';
51
        try {
52
            long long c = mul_checked(a,b);
53
            cout << "  value = " << c << " (via __int128)\n";
54
        } catch (const overflow_error& ) {
55
            cout << "  value not representable in long long (via __int128)\n";
56
        }
57
    }
58
    return 0;
59
}
60

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
using int64 = long long;
5
const int64 MOD = 1000000007LL; // Example modulus
6
7
// Normalize x into [0, MOD-1]
8
inline int64 norm(int64 x) {
9
    x %= MOD;
10
    if (x < 0) x += MOD;
11
    return x;
12
}
13
14
// Safe modular multiply using __int128 to avoid overflow when MOD is large.
15
inline int64 mod_mul(int64 a, int64 b) {
16
    return (int64)(((__int128) a * b) % MOD);
17
}
18
19
int64 mod_pow(int64 a, long long e) {
20
    a = norm(a);
21
    int64 r = 1;
22
    while (e > 0) {
23
        if (e & 1LL) r = mod_mul(r, a); // reduce at every step
24
        a = mod_mul(a, a);
25
        e >>= 1LL;
26
    }
27
    return r;
28
}
29
30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    // Example: compute dot product under modulo safely
35
    int n; n = 5;
36
    vector<int64> x = { (int64)1e9, (int64)1e9, (int64)1e9, (int64)1e9, (int64)1e9 };
37
    vector<int64> y = { 2,3,5,7,11 };
38
39
    int64 dot = 0;
40
    for (int i = 0; i < n; ++i) {
41
        // Reduce operands early and multiply in 128-bit, then reduce again
42
        dot = (dot + mod_mul(norm(x[i]), norm(y[i]))) % MOD;
43
    }
44
45
    cout << "dot(mod 1e9+7) = " << dot << "\n";
46
47
    // Example: large exponent under modulo
48
    cout << "2^(1e18) mod 1e9+7 = " << mod_pow(2, (long long)1e18) << "\n";
49
    return 0;
50
}
51

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes lcm(a,b) safely in long long; returns -1 if it would overflow.
5
long long lcm_safe(long long a, long long b) {
6
    if (a == 0 || b == 0) return 0;
7
    long long g = std::gcd(a, b);
8
    long long a_reduced = a / g; // divide before multiply
9
    // Check overflow for a_reduced * b
10
    __int128 prod = ( __int128 )a_reduced * ( __int128 )b;
11
    if (prod > ( __int128 )LLONG_MAX) return -1; // would overflow signed 64-bit
12
    return (long long)prod;
13
}
14
15
int main() {
16
    ios::sync_with_stdio(false);
17
    cin.tie(nullptr);
18
19
    // Suppose constraints suggest the answer should fit into 64-bit.
20
    vector<long long> v = { 6, 8, 25, 49, 11, 13 };
21
    long long L = 1;
22
    for (long long x : v) {
23
        long long nxt = lcm_safe(L, x);
24
        if (nxt == -1) {
25
            cout << "Overflow computing LCM!\n";
26
            return 0;
27
        }
28
        L = nxt;
29
        // Optional extra bound check: stop if L exceeds a known limit
30
        if (L > (long long)9e18) { // problem-specific cap
31
            cout << "LCM exceeds 9e18 bound\n";
32
            return 0;
33
        }
34
    }
35
    cout << "LCM = " << L << "\n";
36
    return 0;
37
}
38