/*
================================================================
Modulo Multiplication (Slow and Fast Versions)
================================================================
Purpose:
Compute (a * b) % $mod safely for large 64‑bit values
without using GMP or BC Math.
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:
PHP integers are 64‑bit on most systems.
All intermediate values are kept safe using modulo.
*/
// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
function mul_mod_slow(int $a, int $b, int $mod): int
{
/*
Computes:
(b + b + b + ... a times) % mod
This avoids overflow because:
- result stays below mod
- b fits in 64‑bit
- 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
}
$result = 0;
for ($i = 0; $i < $a; $i++) {
$result = ($result + $b) % $mod;
}
return $result;
}
// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
function mul_mod_fast(int $a, int $b, int $mod): 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 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
// ---------------------------------------------------------------
$x = 798345;
$y = 20289473612815;
$mod = 100000000000003;
$slow = mul_mod_slow($x, $y, $mod);
$fast = mul_mod_fast($x, $y, $mod);
echo "Slow result: $slow\n";
echo "Fast result: $fast\n";
/*
run:
Slow result: 99811422305238
Fast result: 99811422305238
*/
