/**
================================================================
Modulo Multiplication (Slow and Fast Versions)
================================================================
Purpose:
Compute (a * b) % mod safely for large 64‑bit values
without using BigInteger.
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 by never multiplying large numbers.
- Produces the same result as the slow version.
Notes:
Java long is 64‑bit signed.
All intermediate values are kept within range using modulo.
The fast version is the recommended one for real use.
================================================================
*/
public class ModMul {
// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
public static long mulModSlow(long a, long b, long mod) {
/**
Computes:
(b + b + b + ... a times) % mod
This avoids overflow because:
- result stays below mod
- b fits in long
- addition is safe
But it is O(a), which is too slow for large inputs.
*/
if (b < a) {
long tmp = a;
a = b;
b = tmp;
}
long result = 0;
for (long i = 0; i < a; i++) {
result = (result + b) % mod;
}
return result;
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
public static long mulModFast(long a, long b, long mod) {
/**
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
*/
long result = 0;
a %= mod;
while (b > 0) {
if ((b & 1) == 1) {
result = (result + a) % mod;
}
a = (a << 1) % mod;
b >>= 1;
}
return result;
}
// ---------------------------------------------------------------
// MAIN PROGRAM
// ---------------------------------------------------------------
public static void main(String[] args) {
long x = 798_345L;
long y = 20_289_473_612_815L;
long mod = 100_000_000_000_003L;
long slowResult = mulModSlow(x, y, mod);
long fastResult = mulModFast(x, y, mod);
System.out.println("Slow result: " + slowResult);
System.out.println("Fast result: " + fastResult);
}
}
/*
run:
Slow result: 99811422305238
Fast result: 99811422305238
*/
