binomial_coefficients_mod.js

const testSolution = (f, n, r, mod) => {
    iterations = 0;
    const start = process.hrtime();
    const result = f(n, r, mod);
    const diff = process.hrtime(start);
    console.log(`${n}C${r} = ${result}, iterations: ${iterations}, duration: ${diff[1]/1000}μs`);
};

// More verbose and integer caching
// O(n^2) first call, best case in subsequent calls: O(1)
let iterations = 0;
const nCr = (n, r, mod) => {
    if (r == 0 || r == n) {
        return 1;
    }
    nCr[n] = nCr[n] || [];
    if (!nCr[n][r]) {
        nCr[n][r] = (nCr(n-1, r-1, mod) + nCr(n-1, r, mod)) % mod;
        iterations++;
    }
    return nCr[n][r];
};
console.log("Recursive, caching:");
testSolution(nCr, 1000, 500, 1e9 + 7);
testSolution(nCr, 1000, 500, 1e9 + 7);

const nCrSingleIndex = (n, r, mod) => {
    if (r == 0 || r == n) {
        return 1;
    }
    const o = n + 1/r;
    //nCr[n] = nCr[n] || [];
    if (!nCrSingleIndex[o]) {
        nCrSingleIndex[o] = (nCrSingleIndex(n-1, r-1, mod) + nCrSingleIndex(n-1, r, mod)) % mod;
        iterations++;
    }
    return nCrSingleIndex[o];
};


console.log("\nRecursive, caching, single index:");
testSolution(nCrSingleIndex, 1000, 500, 1e9 + 7);
testSolution(nCrSingleIndex, 1000, 500, 1e9 + 7);

const xgcd = (a , b) => {
    if (a==0) {
        return [b, 0, 1];
    }
    let ans = xgcd(b%a , a);
    return [ans[0], (ans[2] - (Math.floor(b/a) * ans[1])) , ans[1]];
}

const inverseMod = (a, mod) => {
    const xgcdResult = xgcd(a, mod);
    if (xgcdResult[0] !== 1) {
        throw new Error("Not invertible" + String(xgcdResult));
    }
    if (xgcdResult[1] < 0) {
        xgcdResult[1] += mod;
    }
    return xgcdResult[1];
}

// Simple non-caching iterative.
// exactly O(r), always. mod has to be prime
const nCrIterative = (n, r, mod) => {
    let nominator = 1;
    let denominator = 1;
    for (let i = 1; i <= r; i++) {
        nominator = ((n + 1 - i) * nominator) % mod;
        denominator = (i * denominator) % mod;
        iterations++;
    }
    const denomInverse = inverseMod(denominator, mod);
    return (nominator * denomInverse) % mod;
}

console.log("\nIterative, non-caching, xgcd:")
testSolution(nCrIterative, 1000, 500, 1e9 + 7);
testSolution(nCrIterative, 1000, 500, 1e9 + 7);

/*
Recursive, caching:
1000C500 = 159835829, iterations: 250000, duration: 26670.098μs
1000C500 = 159835829, iterations: 0, duration: 3.017μs

Recursive, caching, single index:
1000C500 = 159835829, iterations: 250000, duration: 418900.937μs
1000C500 = 159835829, iterations: 0, duration: 2.48μs

Iterative, non-caching, xgcd:
1000C500 = 159835829, iterations: 500, duration: 225.164μs
1000C500 = 159835829, iterations: 500, duration: 64.909μs
*/