How to multiply two integers of order 10^18

Question

I have a code that contains statements like

ans =((ans % mod)*(n % mod)) % mod;

and,

 inverse= findMMI_fermat(n,mod);
 ans =((ans % mod)*(inverse % mod)) % mod;

findMMI_fermat is defined as:

 ull fast_pow(ull base,ull n,ull M) //ull is unsigned long long
 {
     if(n==0)
        return 1;
     if(n==1)
        return base;
     ull halfn=fast_pow(base,n/2,M);
     if(n%2==0)
        return ( halfn * halfn ) % M;
     else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
 }

 ull findMMI_fermat(ull n,ull M)
 {
    return fast_pow(n,M-2,M);
 }

All the variables are declared unsigned long long. The program is running fine till size of ans,mod and n all grow to the order of 10^18. I know that I can't multiply such large numbers directly and I know an approach of converting the integers to string and then multiplying them. But is there any other easier way?

You can use a big integer library. – Banex Aug 02 '15 at 15:04 — Banex, Aug 02 '15 at 15:04

score 0 · Answer 1 · answered Aug 02 '15 at 15:05

No, there isn't. the other approach needs work too. but, does not use strings. it uses array of bytes or array of integers or long long.

But, it works exactly as the strings approach work.

Languages as Java have a built in library for big numbers. I don't recall such a library for c++.

How to multiply two integers of order 10^18

1 Answers1