package main
import (
"fmt"
)
/*
===============================================================
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:
Go uint64 arithmetic wraps on overflow, so the fast version
reduces modulo at every step to keep values safe.
*/
// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
func mulModSlow(a, b, mod uint64) uint64 {
/*
Computes:
(b + b + b + ... a times) % mod
This avoids overflow because:
- result stays below mod
- b fits in uint64
- addition is safe
But it is O(a), which is too slow for large inputs.
*/
if b < a {
a, b = b, a // reduce loop count
}
var result uint64 = 0
for i := uint64(0); i < a; i++ {
result = (result + b) % mod
}
return result
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
func mulModFast(a, b, mod uint64) uint64 {
/*
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
*/
var result uint64 = 0
a %= mod
for b > 0 {
if b&1 == 1 {
result = (result + a) % mod
}
a = (a << 1) % mod
b >>= 1
}
return result
}
// ---------------------------------------------------------------
// MAIN PROGRAM
// ---------------------------------------------------------------
func main() {
x := uint64(798345)
y := uint64(20289473612815)
mod := uint64(100000000000003)
slow := mulModSlow(x, y, mod)
fast := mulModFast(x, y, mod)
fmt.Println("Slow result:", slow)
fmt.Println("Fast result:", fast)
}
/*
run:
Slow result: 99811422305238
Fast result: 99811422305238
*/
