10

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. :

  • pow(a,b) means a*a*a*a*... b times.
  • X % MOD means the remainder obtained on dividing X by MOD.
Gurpreet Singh
  • 1,326
  • 3
  • 15
  • 21
  • possible duplicate of [Handle arbitrary length integers in C++](http://stackoverflow.com/questions/8146938/handle-arbitrary-length-integers-in-c) – Jerry Coffin Jun 30 '12 at 07:52
  • just for clarifying, in C++ `^` is the XOR operator, not an exponent operator (you would end up with some pretty off results, first-hand experience there). I believe you have to use `Math.exp(a,b)` – nbrooks Jun 30 '12 at 07:54
  • @nbrooks: While you're certainly correct that C++ uses `^` to mean XOR, `Math.exp(a, b)` doesn't look like C++ (and based on the name, I'd expect it to compute the exponential, not raise a number to a power). – Jerry Coffin Jun 30 '12 at 07:56
  • @nbrooks I think you mean `pow()`. Your example is from the JS method. – Bojangles Jun 30 '12 at 07:57
  • @JamWaffles thanks for the correction. yep alas after a while they all start to blend together in your head. you're completely right `pow(a,b)` in math.h. – nbrooks Jun 30 '12 at 08:02
  • 3
    Guys, when it comes to number theoretical tasks, brute-force approaches are, to say the least, not the best way to solve the problem. A little NumberTheory 101 and you know about classical Euler's theorem. My answer has the appropriate link. I believe MOD is a usual integer which fits in a CPU's register and this makes the task a simple exercise in modular arithmetics. – Viktor Latypov Jun 30 '12 at 08:24
  • 1
    possible duplicate of [Calculating pow(a,b) mod n](http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n) – phuclv Sep 06 '15 at 05:18

7 Answers7

15

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.

Viktor Latypov
  • 14,289
  • 3
  • 40
  • 55
  • Thanks Viktor. I got what was desired. Thanks for the help... :-) BTW, I knew about the totient function, but not about that Euler's theorem... – Gurpreet Singh Jun 30 '12 at 08:24
  • 1
    "So to calculate phi(b) one does not need to know its factors." This hardly looks like a practical method for computing `phi(b)`, though. – Mark Dickinson Jun 30 '12 at 10:44
  • @MarkDickinson: Yes, that's why I added the remark about Schramm's paper. There's only a single discrete Fourier transform involved. – Viktor Latypov Jun 30 '12 at 10:45
  • Sorry; that's what I meant: computing via the Fourier transform isn't going to be any more efficient than computing via factoring. (BTW, I believe the result on wikipedia attributed to Schramm is actually much much older.) – Mark Dickinson Jun 30 '12 at 10:48
  • I also believe that Schramm's result might have been known for a long time. The thing with Fourier... Yes, I see the weakness of my answer. Not a number theorist, unfortunately. – Viktor Latypov Jun 30 '12 at 10:51
3

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);
}
Caramiriel
  • 7,029
  • 3
  • 30
  • 50
Jefferson Rondan
  • 103
  • 1
  • 10
1

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
WawaBrother
  • 2,195
  • 3
  • 14
  • 15
0

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).

Mario
  • 35,726
  • 5
  • 62
  • 78
  • It's a number-theoretic question, really. No need to brute-force here. The whole point of the task is to show the superiority of some simple classic theorems. See my answer. – Viktor Latypov Jun 30 '12 at 08:18
  • Interesting, guess you just stole my weekend's spare time, going to read up on that. :) – Mario Jun 30 '12 at 08:29
  • This book is nice: http://books.google.ru/books/about/Number_Theory.html?id=njgVUjjO-EAC Also the Ivan Vinogradov's books are good. The Jean-Pierre Serre's "Course d'arithmetique" opens even more possibilities. – Viktor Latypov Jun 30 '12 at 08:32
0

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.

Markus Mikkolainen
  • 3,397
  • 18
  • 21
0

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

0
#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 ;
}
Rohit Singh
  • 1