"""
===============================================================
Modulo Multiplication (Slow and Fast Versions)
===============================================================
Purpose:
Compute (a * b) % mod using two different approaches.
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 in languages with fixed-size integers.
- Produces the same result as the slow version.
Notes:
Python integers are arbitrary‑precision, so overflow is not a concern.
We still implement the algorithms faithfully for educational clarity.
"""
# ---------------------------------------------------------------
# SLOW VERSION (simple, correct, but extremely slow)
# ---------------------------------------------------------------
def mul_mod_slow(a: int, b: int, mod: int) -> int:
"""
Computes:
(b + b + b + ... a times) % mod
This avoids overflow in fixed-width languages because:
- result stays below mod
- b fits in the integer type
- addition is safe
But it is O(a), which is too slow for large inputs.
"""
# Reduce loop count by ensuring the smaller number is used as counter
if b < a:
a, b = b, a
result = 0
for _ in range(a):
result = (result + b) % mod
return result
# ---------------------------------------------------------------
# FAST VERSION (efficient and safe)
# ---------------------------------------------------------------
def mul_mod_fast(a: int, b: int, mod: int) -> int:
"""
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 in languages with fixed-size integers because:
- We never compute a * b directly.
- Doubling a is safe because we reduce modulo each step.
This makes the algorithm:
- Fast
- Safe
- Exact
"""
result = 0
a %= mod
while b > 0:
if b & 1:
result = (result + a) % mod
a = (a << 1) % mod
b >>= 1
return result
# ---------------------------------------------------------------
# MAIN PROGRAM
# ---------------------------------------------------------------
if __name__ == "__main__":
x = 798_345
y = 20_289_473_612_815
mod = 100_000_000_000_003
slow_result = mul_mod_slow(x, y, mod)
fast_result = mul_mod_fast(x, y, mod)
print("Slow result:", slow_result)
print("Fast result:", fast_result)
"""
run:
Slow result: 99811422305238
Fast result: 99811422305238
"""
