### NeverSayNever's blog

By NeverSayNever, 7 years ago,

Hello all ,

Hope you all are doing well .

I am looking for an efficient way to multiply two numbers A and B mod C where A,B,C can be in the range [1,1015] .

Here are the list of the solution which i think can think off but there must be some more fast methods .

Solution 1 : simplest and easiest solution is two switch language to jave,python or to use big int in c++ . I don't fill it is a good technique and would like to do it in c .

Solution 2 : Russian Peasant Multiplication


long long int mulmod(long long int a,long long int b) {
if (M <= 1000000009) return a * b % M;

long long int res = 0;
while (a > 0) {
if (a & 1) {
res += b;
if (res >= M) res -= M;
}
a >>= 1;
b <<= 1;
if (b >= M) b -= M;
}
return res;
}



which works in O(log(min(A,B))) time .

I heard of karatsuba algorithm which is very fast. Is it faster than the russian multiplication .. can anyone provide me some implementation stuff or some motivation ..

Any kind of help is appreciated :D :D

### EDIT1

: Is there any constant time algo exist .

### EDIT2

: I also find this .. but i think it is not correct for the values upto 10^18 ..

long long int mulmod(long long int val, long long int n,long long int mod)
{
long long int q=((double)val*(double)n/(double)mod);
long long int res=val*n-mod*q;
res=(res%mod+mod)%mod;
return res;
}



• +7

 » 7 years ago, # |   0 You can multiplying strings and after that you can divide result with string C (useing hand-multiplication and division).
•  » » 7 years ago, # ^ |   0 Will it be efficient than russian peasant multiplication ?
•  » » 7 years ago, # ^ |   0 Performance is the main concern . Can you provide some code for this if possible.
•  » » » 7 years ago, # ^ |   0 You have many problems where you should divide a large number with a number smaller than 10^18.You can multiply big number in complexity (n^2 where n is number of digits).After that you can divide string with number smaller than 10^18 easy,probably you can divide string with string (also n^2) but I don't do that so far.
•  » » » » 7 years ago, # ^ |   0 Too slow, and a constant is very big, I believe.
•  » » » » » 7 years ago, # ^ |   0 For case in blog that is very fast...I don't know how you can divide two big number better that n^2 .For case n=10^5 you can't calculate remain because number which you should divide has 10^10 digits.
•  » » » » » » 7 years ago, # ^ |   0 For case in blog you can do it in O(1) because numbers fit in long long type. O(1) is definetely better than .
 » 7 years ago, # |   0 Karatsuba multiplication is not OK in this case because it have a large constant. It is OK for really big numbers (like 1010000) and it works in . There is also way to multiply two big numbers in with FFT.
•  » » 7 years ago, # ^ |   -9 Thank you for the your answer. Can you suggest what should i do in this case which is fast than that of Russian Multiplication .
•  » » » 7 years ago, # ^ |   0 Your second code runs in O(1). I don't know how to make anything faster than it :)
•  » » » » 7 years ago, # ^ |   0 Second code is not working well .. don't know why is this happening ..
•  » » » » 7 years ago, # ^ |   0 http://msdn.microsoft.com/en-IN/library/s3f49ktz.aspxlook at this link which clearly states that double range can hold only 15 digits .. how this code can be correct although i have took it from some AC submission from codechef .. but how ? any thing that you would like to comment or any that you can provide to me ??
•  » » » » » 7 years ago, # ^ |   0 described here (in Russian, sorry :) )
 » 7 years ago, # |   +12 LL Mul(LL a, LL b, LL M) { LL res = 0; const int k = 14;// floor(64 - log2(MAX_VALUE)) while (a > 0) { int intA = a & ((1 << k) - 1); res = (res + b * intA) % M; a >>= k; b = (b << k) % M; } return res; } 
•  » » 7 years ago, # ^ |   0 I thought of doing this but this statement res = (res + b * intA) % M; requires another multiplication which many get overflow.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Size of b is at most 50 bits — log2(10^15). Size of intA is at most 14 bits. Result of multiplication is less than 64 bits. So for this multiplication enoug type unsigned long long. Use value 13 instead of 14 to make it possible using signed long long.
 » 7 years ago, # |   +13 I guess long double would be better in the third method. And it looks like it works OK for long long.By the way, why is the second method called "Russian Peasant Multiplication"?I'd call it binary multiplication as it's practically the same as binary exponentiation.