Ways to do modulo multiplication with primitive types
algorithm, c++
Solution
You should use Russian Peasant multiplication. It uses repeated doubling to compute all the values `(b*2^i)%m`, and adds them in if the `i`th bit of `a` is set.
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
int64_t res = 0;
while (a != 0) {
if (a & 1) res = (res + b) % m;
a >>= 1;
b = (b << 1) % m;
}
return res;
}
It improves upon your algorithm because it takes `O(log(a))` time, not `O(a)` time.
Caveats: unsigned, and works only if `m` is 63 bits or less.
Problem
Is there a way to build e.g. `(853467 * 21660421200929) % 100000000000007` without BigInteger libraries (note that each number fits into a 64 bit integer but the multiplication result does not)? This solution seems inefficient: ``` int64_t mulmod(int64_t a, int64_t b, int64_t m) { if (b < a) std::swap(a, b); int64_t res = 0; for (int64_t i = 0; i < a; i++) { res += b; res %= m; } return res; } ```