The module for multiplying large numbers

Question

Yes, I know that the question may seem naive, but I searched a lot on Google and on this site, but could not find a satisfactory answer to it. I just want to calculate (A * B)% MOD, assuming a is long long, as well as b and MOD. Suppose that MOD is greater than A and B, such that A% MOD = A and B% MOD = B, but A * B is greater than 64 bits. How can I fix the value (A * B)% MOD?

Answer 1

The basic idea here is to first define a non- addmod addmod function that takes advantage of negative numbers in its arithmetic. Then define timesmod in terms of this also using bitwise operations. The complexity of the time is O(N) , where N is the number of bits used (in this case, 64).

 #include <iostream> using namespace std; typedef long long BigInt; // must be signed, to detect overflow BigInt A = 0x7fffffffffffff01; BigInt B = 0x7fffffffffffff02; BigInt M = 0x7fffffffffffff03; // For simplicity it is assumed x, y, and m are all positive. BigInt addmod( BigInt x, BigInt y, BigInt m ) { x %= m; y %= m; BigInt sum = x-m+y; // -m <= sum < m-1 return sum < 0 ? sum + m : sum; } BigInt timesmod( BigInt x, BigInt y, BigInt m ) { x %= m; y %= m; BigInt a = x < y ? x : y; // min BigInt b = x < y ? y : x; // max BigInt product = 0; for (; a != 0; a >>= 1, b = addmod(b,b,m) ) if (a&1) product = addmod(product,b,m); return product; } int main() { cout << "A = " << A << endl; cout << "B = " << B << endl; cout << "M = " << M << endl; cout << "A*B mod M = " << timesmod(A,B,M) << endl; return 0; } 

Output:

 A = 9223372036854775553 B = 9223372036854775554 M = 9223372036854775555 A*B mod M = 2 

This is easy to confirm, since A=-2 and B=-1 mod M

Note: this code is not optimized.

Answer 2

I don’t have time to answer this right now, so I’ll give a pointer and come back to edit this answer later. See “literacy multiplication” in your favorite algorithm book (or search engine). The basic idea is to split both A and B into pieces, process the pieces individually, and then combine the pieces to complete the calculation.

Answer 3

I think that you can form a 128-bit product in two parts (high 64 bit and low 64 bit) and reduce each part modulo p. Assuming p is around 4^k , you can then figure out how much p is in that number by dividing hi64 / (p>>k) ; this should give you about k-1 bits of the correct answer. Subtract a lot of p from everything, and now hi64 has about k-1 fewer bits. Do it again, but calculate (hi64 << k-1) / (p >> k) . Then do it again, calculating (hi64 << k+k-2) / (p >> k) .

The Schrage trick suggested by another poster sounds better, but I don't get it. Hope the poster comes back and completes its answer!