NeverSayNever's blog

Fastest Way to multiply two Numbers
By NeverSayNever, 10 years ago, In English

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;
}
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can multiplying strings and after that you can divide result with string C (useing hand-multiplication and division).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will it be efficient than russian peasant multiplication ?

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Performance is the main concern . Can you provide some code for this if possible.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Too slow, and a constant is very big, I believe.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            For case in blog you can do it in O(1) because numbers fit in long long type. O(1) is definetely better than .

            → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Thank you for the your answer. Can you suggest what should i do in this case which is fast than that of Russian Multiplication .

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your second code runs in O(1). I don't know how to make anything faster than it :)

      → Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it 

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;
}
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of doing this but this statement res = (res + b * intA) % M; requires another multiplication which many get overflow.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply