#include <stdio.h>
#include <stdint.h>
/*
================================================================
Modulo Multiplication in C (Slow and Fast Versions)
================================================================
Purpose:
Compute (a * b) % mod safely for large 64‑bit values
without using big‑integer libraries.
Why two versions?
1. Slow version:
- Adds 'b' to the result 'a' times.
- Always correct.
- Very slow for large numbers.
- Useful as a correctness reference.
2. Fast version:
- Uses the "double‑and‑add" technique.
- Runs in O(log b).
- Uses unsigned __int128 internally to avoid overflow.
- Produces the same result as the slow version.
================================================================
*/
/* ---------------------------------------------------------------
SLOW VERSION (simple, correct, but extremely slow)
--------------------------------------------------------------- */
uint64_t mul_mod_slow(uint64_t a, uint64_t b, uint64_t mod) {
/*
Computes:
(b + b + b + ... a times) % mod
This avoids overflow because:
- result stays below mod
- b fits in uint64_t
- addition is safe
But it is O(a), which is too slow for large inputs.
*/
if (b < a)
{ uint64_t tmp = a; a = b; b = tmp; } // reduce loop count
uint64_t result = 0;
for (uint64_t i = 0; i < a; i++) {
result += b;
result %= mod;
}
return result;
}
/* ---------------------------------------------------------------
FAST VERSION (efficient and safe using __uint128_t)
--------------------------------------------------------------- */
uint64_t mul_mod_fast(uint64_t a, uint64_t b, uint64_t mod) {
/*
Uses the classic "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.
The key detail:
Use unsigned __int128 for intermediate values so that
doubling 'a' never overflows.
This makes the algorithm:
- Fast
- Safe
- Exact
*/
__uint128_t A = a;
__uint128_t B = b;
__uint128_t M = mod;
__uint128_t result = 0;
while (B > 0) {
if (B & 1)
result = (result + A) % M;
A = (A << 1) % M;
B >>= 1;
}
return (uint64_t)result;
}
/* ---------------------------------------------------------------
MAIN PROGRAM
--------------------------------------------------------------- */
int main(void) {
uint64_t x = 798345ULL;
uint64_t y = 20289473612815ULL;
uint64_t mod = 100000000000003ULL;
uint64_t slow_result = mul_mod_slow(x, y, mod);
uint64_t fast_result = mul_mod_fast(x, y, mod);
printf("Slow result: %llu\n", (unsigned long long)slow_result);
printf("Fast result: %llu\n", (unsigned long long)fast_result);
return 0;
}
/*
run:
Slow result: 99811422305238
Fast result: 99811422305238
*/
