/*
===============================================================
Modulo Multiplication (Slow and Fast Versions)
===============================================================
Purpose:
Demonstrate safe modulo multiplication using only JavaScript
Number arithmetic (IEEE‑754 double), which is limited to
53‑bit integer precision.
Important:
JavaScript/TypeScript Number cannot safely represent 64‑bit
integers. Therefore, this example uses smaller values that
remain within the safe integer range.
Versions:
1. Slow version:
- Adds b to result a times.
- Always correct within safe integer range.
- Very slow for large numbers.
2. Fast version:
- Uses the classic "double‑and‑add" technique.
- Runs in O(log b).
- Avoids overflow by reducing modulo each step.
*/
// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
function mulModSlow(a: number, b: number, mod: number): number {
/*
Computes:
(b + b + b + ... a times) % mod
Works safely only when all values are <= Number.MAX_SAFE_INTEGER.
*/
if (b < a) {
const tmp: number = a;
a = b;
b = tmp;
}
let result: number = 0;
for (let i: number = 0; i < a; i++) {
result = (result + b) % mod;
}
return result;
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
function mulModFast(a: number, b: number, mod: number): number {
/*
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.
Works safely only when all values are <= Number.MAX_SAFE_INTEGER.
*/
let result: number = 0;
a = a % mod;
while (b > 0) {
if (b & 1) {
result = (result + a) % mod;
}
a = (a << 1) % mod;
b >>= 1;
}
return result;
}
// ---------------------------------------------------------------
// MAIN PROGRAM (using safe 53‑bit values)
// ---------------------------------------------------------------
const x: number = 123456; // safe
const y: number = 987654321; // safe
const mod: number = 1_000_000_007; // safe
const slowResult: number = mulModSlow(x, y, mod);
const fastResult: number = mulModFast(x, y, mod);
console.log("Slow result:", slowResult);
console.log("Fast result:", fastResult);
/*
run:
Slow result: 259106092
Fast result: 259106092
*/
