/*
===============================================================
Modulo Multiplication (Slow and Fast Versions)
===============================================================
Purpose:
Compute (a * b) % mod safely for large 64‑bit values.
Why BigInt?
TypeScript numbers are IEEE‑754 doubles and cannot safely
represent integers above 2^53. Your values exceed that limit,
so BigInt is required.
Versions:
1. Slow version:
- Adds b to result a times.
- Always correct.
- Very slow for large numbers.
- Useful as a correctness reference.
2. Fast version:
- Uses the classic "double‑and‑add" technique.
- Runs in O(log b).
- Avoids overflow.
- Produces the same result as the slow version.
*/
// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
function mulModSlow(a: bigint, b: bigint, mod: bigint): bigint {
/*
Computes:
(b + b + b + ... a times) % mod
This avoids overflow because:
- result stays below mod
- b fits in BigInt
- addition is safe
But it is O(a), which is too slow for large inputs.
*/
if (b < a) {
[a, b] = [b, a]; // reduce loop count
}
let result: bigint = 0n;
for (let i: bigint = 0n; i < a; i++) {
result = (result + b) % mod;
}
return result;
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
function mulModFast(a: bigint, b: bigint, mod: bigint): bigint {
/*
Uses the "double‑and‑add" method:
- If the lowest bit of b is set, add a to result.
- Double a each step.
- Shift b right each step.
This avoids overflow because:
- We never compute a * b directly.
- Doubling a is safe because we reduce modulo each step.
This makes the algorithm:
- Fast
- Safe
- Exact
*/
let result: bigint = 0n;
a = a % mod;
while (b > 0n) {
if (b & 1n) {
result = (result + a) % mod;
}
a = (a << 1n) % mod;
b >>= 1n;
}
return result;
}
// ---------------------------------------------------------------
// MAIN PROGRAM
// ---------------------------------------------------------------
const x: bigint = 798345n;
const y: bigint = 20289473612815n;
const mod: bigint = 100000000000003n;
const slowResult: bigint = mulModSlow(x, y, mod);
const fastResult: bigint = mulModFast(x, y, mod);
console.log("Slow result:", slowResult);
console.log("Fast result:", fastResult);
/*
run:
Slow result: 99811422305238n
Fast result: 99811422305238n
*/
