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;
}
You just multiply the two numbers and then calculate the standard name. For example, say the modulus is 7. Let's look at some mod 15 examples. One thing to notice is that in modular arithmetic you can multiply two numbers that are both nonzero, and the result can be zero.
Congruences may be multiplied: if a ≡ b (mod m) and c ≡ d (mod m), then ab ≡ cd (mod m). Property 6. Both sides of a congruence may be divided by a number relatively prime to m: if ab ≡ ac (mod m) and (a, m) = 1, then b ≡ c (mod m).
Ideally the safest approach is to avoid signed integer overflow entirely. For example, instead of multiplying two signed integers, you can convert them to unsigned integers, multiply the unsigned values, then test whether the result is in signed range.
Hence, we have proved that multiplication modulo n is associative!
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.
Keith Randall's answer is good, but as he said, a caveat is that it works only if m
is 63 bits or less.
Here is a modification which has two advantages:
m
is 64 bits.(Note that the res -= m
and temp_b -= m
lines rely on 64-bit unsigned integer overflow in order to give the expected results. This should be fine since unsigned integer overflow is well-defined in C and C++. For this reason it's important to use unsigned integer types.)
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
uint64_t res = 0;
uint64_t temp_b;
/* Only needed if b may be >= m */
if (b >= m) {
if (m > UINT64_MAX / 2u)
b -= m;
else
b %= m;
}
while (a != 0) {
if (a & 1) {
/* Add b to res, modulo m, without overflow */
if (b >= m - res) /* Equiv to if (res + b >= m), without overflow */
res -= m;
res += b;
}
a >>= 1;
/* Double b, modulo m */
temp_b = b;
if (b >= m - b) /* Equiv to if (2 * b >= m), without overflow */
temp_b -= m;
b += temp_b;
}
return res;
}
Both methods work for me. The first one is the same as yours, but I changed your numbers to excplicit ULL. Second one uses assembler notation, which should work faster. There are also algorithms used in cryptography (RSA and RSA based cryptography mostly I guess), like already mentioned Montgomery reduction as well, but I think it will take time to implement them.
#include <algorithm>
#include <iostream>
__uint64_t mulmod1(__uint64_t a, __uint64_t b, __uint64_t m) {
if (b < a)
std::swap(a, b);
__uint64_t res = 0;
for (__uint64_t i = 0; i < a; i++) {
res += b;
res %= m;
}
return res;
}
__uint64_t mulmod2(__uint64_t a, __uint64_t b, __uint64_t m) {
__uint64_t r;
__asm__
( "mulq %2\n\t"
"divq %3"
: "=&d" (r), "+%a" (a)
: "rm" (b), "rm" (m)
: "cc"
);
return r;
}
int main() {
using namespace std;
__uint64_t a = 853467ULL;
__uint64_t b = 21660421200929ULL;
__uint64_t c = 100000000000007ULL;
cout << mulmod1(a, b, c) << endl;
cout << mulmod2(a, b, c) << endl;
return 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With