Chapter 128

Refactoring: Garner's Algorithm

Pairwise CRT works but needs coprime moduli and can overflow. Garner's algorithm solves the system incrementally, computing coefficients that avoid large intermediate numbers — ideal when moduli are small but the product is large.

Before: Pairwise CRT (handles overflow poorly)

C++

pairwise_crt(a1, m1, a2, m2);
// Need to keep combining — lcm grows fast

After: Garner's Algorithm

C++ — Garner's algorithm

long long garner(vector& rem, vector& mod) {
    int k = rem.size();
    vector coeff(k, 1), val(k, 0);

    for (int i = 0; i < k; i++) {
        // Compute x ≡ rem[i] (mod mod[i]) given previous constraints
        long long t = (rem[i] - val[i]) * mod_inv(coeff[i], mod[i]) % mod[i];
        if (t < 0) t += mod[i];

        for (int j = i + 1; j < k; j++) {
            val[j] = (val[j] + coeff[j] * t) % mod[j];
            coeff[j] = (coeff[j] * mod[i]) % mod[j];
        }
    }
    return val[k - 1];
}

// Avoids large intermediate products — works with 32-bit moduli.