How to avoid overflow in expression (A - B * C) / D?-CodePudding

I need to compute an expression that looks like: (A - B * C) / D, where their types are: signed long long int A, B, C, D; Each number can be really big (not overflowing its type). While B * C could cause overflow, at same time expression (A - B * C) / D would fit in. How can I compute it correctly?

For example: In the equation (Ax By = C), assuming A * x is overflowing, but y = (C - A * x) / B could fit in. No need to use BigInteger or double data type.

CodePudding user response：

I think you could change the order of the operations so it will look like: A/D - (B/D)*C The result should remain the same.

CodePudding user response：

You can transform the equation to do the division first while accounting for the remainders:

Assume / is integer division and everything is infinite precision:

x == x / y * y   x % y

(A - B * C) / D
((A/D * D   (A%D)) - (B/D * D   (B%D)) * (C/D * D   (C%D))) / D
(A/D * D - B/D * D * C/D * D - (B/D * D * (C%D)   (B%D) * C/D * D)   (A%D) - (B%D) * (C%D)) / D
(A/D * D - B/D * D * C/D * D) / D - (B/D * D * (C%D)   (B%D) * C/D * D) / D   ((A%D) - (B%D) * (C%D)) / D
(A/D - B/D * C/D * D) - (B/D * (C%D)   (B%D) * C/D)   ((A%D) - (B%D) * (C%D)) / D
A/D - B/D * C - B/D * (C%D) - (B%D) * C/D)   ((A%D) - (B%D) * (C%D)) / D

Assuming D is not too small and not too big then x / D and x % D are small and we can do this:

using T = signed long long int;

T compute(T a, T b, T c, T d) {
    T a1 = a / d, a2 = a % d;
    T b1 = b / d, b2 = b % d;
    T c1 = c / d, c2 = c % d;
    T m1 = b1 * c, m2 = b1 * c2, m3 = b2 * c1, m4 = b2 * c2;
    T s1 = a1 - m1 - m2 - m3, s2 = a2 - m4;
    return s1   s2 / d;
}

The critical part is the multiplication for m1 through m4. The range of numbers b and c that overflow while the result should have fit is rather small I believe.

CodePudding user response：

Since you mentioned gcd lets try that as alternative answer:

using T = signed long long int;

T gcd(T a, T b);
T compute(T a, T b, T c, T d) {
    // use gcd for (b * c) / d
    T db = gcd(b, d);
    T dc = gcd(c, d / db);
    T dm = db * dc;
    
    // use gcd on a for (a - b*c) / dm
    T da = gcd(a, dm);
    
    // split da for use on (b * c) / da
    db = gcd(b, da);
    dc = da / db;
    T dr = d / da;
    
    return ((a / da) - (b / db) * (c / dc)) / dr;
}

Only works if d has enough factors in common with a, b and c.