# ===============================================================
# 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 fixed‑width languages.
# - Produces the same result as the slow version.
#
# Notes:
# Ruby 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, b, mod)
# Reduce loop count by ensuring the smaller number is used as counter
a, b = b, a if b < a
result = 0
a.times do
result = (result + b) % mod
end
result
end
# ---------------------------------------------------------------
# FAST VERSION (efficient and safe)
# ---------------------------------------------------------------
def mul_mod_fast(a, b, 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 in fixed‑width languages 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
result = (result + a) % mod if (b & 1) == 1
a = (a << 1) % mod
b >>= 1
end
result
end
# ---------------------------------------------------------------
# MAIN PROGRAM
# ---------------------------------------------------------------
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)
puts "Slow result: #{slow_result}"
puts "Fast result: #{fast_result}"
=begin
run:
Slow result: 99811422305238
Fast result: 99811422305238
=end
