CODEWITHSUNDEEP
c++math
Gurpreet Singh
Gurpreet Singh

Reputation: 1366

Calculating (a^b)%MOD

I want to code for calculating the value of pow(a,b)%MOD. I use C++ to code.

But the problem is the value of b can be very large. I know the log(b) time complexity method. But, the value of b might not fit in the data type "long long" of C++. For example b can be 1000000000 th Fibonacci number. Exact calculation of such a big number is itself, not possible (in time limits).

P.S. :

Upvotes: 10

Views: 11871

Answers (7)

Rohit Singh
Rohit Singh

Reputation: 1

#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define ll long long

ll power(ll x, ll y)
{
    if ( y == 0)
        return 1;
    ll temp = power(x, y / 2);
    if (y % 2 == 0)
        return (temp * temp) % mod;
    else
        return (((temp * temp) % mod) * x) % mod;
}
ll dmod(ll x)
{  
    return ((x + mod) % mod);
}

ll modular_power(ll x, ll y)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)ans = dmod(ans * x);
        y /= 2;
        x = dmod(x * x);
    }
    return ans;
}

int main()
{ 
    ll a, b;
    cin >> a >> b;
    ll ans1 = modular_power(a, b);
    ll ans2 = power(a, b);
    //  both answers are same
    cout << ans1 << " " << ans2 ;
}

Upvotes: 0

user1084944
user1084944

Reputation:

But, the value of b might not fit in the data type "long long" of C++. For example b can be 1000000000 th Fibonacci number.

For things like this, there is a simple fix: recall

a^(b+c) == a^b * a^c mod d

You can compute the particular product you asked about with the same sort of recursion you use to compute Fibonacci numbers -- you don't need large numbers or modular exponentiation at all!

Another version that comes up sometimes is

a^(b*c) = (a^b)^c mod d

Upvotes: 0

Jefferson Rondan
Jefferson Rondan

Reputation: 103

I use this function to solve this problem

UVA 374 - Big Mod

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310

// a^b % T

// with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method)

// if a very large use
// R=(unsigned long long)(R*a)%T;

int restOfPot(long long a,int b,int T)
{
    a%=T;
    long long R=1;

    while(b)
    {
        if(b&1) R=(R*a)%T;
        a=(a*a)%T;
        b>>=1;
    }

    return int(R);
}

Upvotes: 3

WawaBrother
WawaBrother

Reputation: 2405

For dealing with very large numbers, take a look at boost's Multiprecision library. It has a powm() function that works for this purpose well.

From Generic Integer Operations ：

template <class Integer>
Integer powm(const Integer& b, const Integer& p, const Integer& m);

Returns bp % m.

Example:

#include <boost/multiprecision/cpp_int.hpp>

boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981");
boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029");
boost::multiprecision::cpp_int base(12345);

boost::multiprecision::cpp_int result = powm(base, pow, mod);

std::cout << "result is: " << result << std::endl;

prints:

result is: 5758534182572671080415167723795472693

Upvotes: 1

Viktor Latypov
Viktor Latypov

Reputation: 14467

That's a typical task. Please (or, really, PLEASE!) read about the Euler's totient function.

And then the Euler's theorem.

The thing is you can dramatically reduce a^b to a^(b % phi(MOD)). Yes, you will need some kind of an integer factorization method, but still, no crazy ideas about actually calculating the power needed.

We did such samples by hand in my youth :) Even when the numbers where far beyond 32/64 bit range.

EDIT: Well, you live and learn. In 2008 the result is obtained:

"The totient is the discrete Fourier transform of the gcd: (Schramm (2008))"

So to calculate phi(b) one does not need to know its factors.

EDIT(2):

And the Carmichael's function is what you need to calculate to get the correct answer for any a, b and MOD.

Upvotes: 15

Markus Mikkolainen
Markus Mikkolainen

Reputation: 3497

I suggest using a specialized math library. Also this looks like crypto, so i suggest using a crypto library. GNU is bound to have one which you can use. This is because in crypto in many cases the exponent might be selected to give efficient calculation using shortcuts which normal math libraries cannot assume.

Upvotes: 0

Mario
Mario

Reputation: 36477

First: ^ in C/C++ is not the operator for powers. In fact, there is no operator for this. ^ represents a bitwise XOR. You'll have to use pow(base, exp) which can be found in the header math.h or cmath.

For such huge numbers, using double or long double (exact lengths and and resulting datatypes might vary depending on your platform), but at some time you'll stumble upon precision issues, so depending on your use case, size of values your best bet might be using a custom datatype (edit: e.g. from one of the libraries found in one of the linked questions).

Upvotes: 0

Related Questions