/*
===============================================================
Modulo Multiplication (Slow and Fast Versions)
===============================================================
Purpose:
Compute (a * b) % mod safely for large 64‑bit values.
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:
Rust u64 arithmetic wraps on overflow, so the fast version
reduces modulo at every step to keep values safe.
*/
// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
fn mul_mod_slow(a: u64, b: u64, modv: u64) -> u64 {
/*
Computes:
(b + b + b + ... a times) % modv
This avoids overflow because:
- result stays below modv
- b fits in u64
- addition is safe
But it is O(a), which is too slow for large inputs.
*/
let (mut a, mut b) = (a, b);
// Reduce loop count by ensuring the smaller number is used as counter
if b < a {
std::mem::swap(&mut a, &mut b);
}
let mut result: u64 = 0;
for _ in 0..a {
result = (result + b) % modv;
}
result
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
fn mul_mod_fast(mut a: u64, mut b: u64, modv: u64) -> u64 {
/*
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 mut result: u64 = 0;
a %= modv;
while b > 0 {
if b & 1 == 1 {
result = (result + a) % modv;
}
a = (a << 1) % modv;
b >>= 1;
}
result
}
// ---------------------------------------------------------------
// MAIN PROGRAM
// ---------------------------------------------------------------
fn main() {
let x: u64 = 798_345;
let y: u64 = 20_289_473_612_815;
let modv: u64 = 100_000_000_000_003;
let slow = mul_mod_slow(x, y, modv);
let fast = mul_mod_fast(x, y, modv);
println!("Slow result: {}", slow);
println!("Fast result: {}", fast);
}
/*
run:
Slow result: 99811422305238
Fast result: 99811422305238
*/
