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

Question

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.

Answer 1

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.