Modulo of multiplication of large numbers
This question already has an answer here:
Basic idea here is to first define a non-overflowing addmod
function which takes advantage of negative numbers in its arithmetic. Then define timesmod
in terms of it also using bit operations. The time complexity is O(N)
where N is the number of bits used (64 in this case).
#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 easily confirmed since A=-2
and B=-1
mod M
.
Note: this code is not optimized.
I don't have time to answer this right now, so I'll give a pointer and come back to edit this answer later. Look up "Schrage multiplication" in your favorite algorithms textbook (or search engine). The basic idea is to split both A and B into pieces, process the pieces separately, then combine the pieces to complete the calculation.
I think you can form the 128-bit product in two pieces (high 64 bits and low 64 bits) and reduce each piece modulo p. Supposing p
is around 4^k
, you can then figure out roughly how many p's are in this number by dividing hi64 / (p>>k)
; this should give you about k-1
bits of the right answer. Subtract off that many p
's from the whole thing and now hi64
has about k-1
fewer bits. Do this again, but compute (hi64 << k-1) / (p >> k)
. Then do it again, computing (hi64 << k+k-2) / (p >> k)
.
Schrage's trick, suggested by another poster, sounds like a better deal, but I don't understand it. Hopefully that poster returns and completes his answer!
链接地址: http://www.djcxy.com/p/18280.html上一篇: 在Windows 7中安装Memcache(XAMPP)
下一篇: 大数乘法的模