how to calculate the power of large numbers

[algmaster]

How to write a program in c++ to find the power of x ^ y, where y = 2 ^ k? To avoid overflow for large numbers (10^18 and larger) the program should give modulo 10^9+7 in return. I will be grateful for your help.

[jonnin]

Its ok to use more words. Can you elaborate?

[lastchance]

#include <iostream>
using namespace std;

unsigned long long pow2k( unsigned long long x, unsigned k, unsigned M )
{
   unsigned long long ans = x % M;
   for ( int i = 1; i <= k; i++ ) ans = ( ans * ans ) % M;
   return ans;
}

int main()
{
   const unsigned M = 1000000007;
   unsigned x = 3, k = 4;      // check case where modulo is irrelevant
   cout << x << "^(2^" << k << ") (mod " << M << ") = " << pow2k( x, k, M ) << '\n';

   x = 10;                     // check case where modulo is important
   cout << x << "^(2^" << k << ") (mod " << M << ") = " << pow2k( x, k, M ) << '\n';
   cout << 10000000000000000ull % M;
}

No fancy large-number library needed.

[zapshe]

If the numbers are huge, you'll need to use a mathematical C++ library or a different language that supports large numbers, like Python.

You can also program your own way to handle large numbers. This can be done by having an array of 1 byte numbers holding the number, or even just a regular string holding the values. Then you code a way to do operations on them.

[kigar64551]

Pretty much every C/C++ compiler supports 64-Bit integers these days.

In a portable way, you can get a 64-Bit (unsigned) integral type by using uint64_t from <stdint.h>.

uint64_t can handle numbers up to 2^64-1, i.e. two to the power of 64 (minus one).

...sufficient for 10^18, which has about ~60 digits (bits) in base 2.

If that still isn't sufficient, you can use the __int128 type on GCC, Clang/LLVM or Intel's C compiler.

(MSVC still doesn't have a 128-Bit integral type, to the best of my knowledge)


If you actually want "arbitrary precision arithmetic" in C/C++, you need an extra library, such as GMP:
https://gmplib.org/

[algmaster]

I greatly appreciate your help. Thank you so much!